表达式求值的递归算法

#include "stdafx.h"

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>

//去括号,当整个表达式被一个括号包围时,可直接去掉.
void DelBracket(char *expre)// 比如: (3+4* (2-1)+5 )
{
        if(expre[0]=='(')
        {
                int  level = 0;
                char *pos;

                for(pos=expre;*pos;++pos)
                {
                        if(*pos=='(')      ++level;
                        else if(*pos==')') --level;

                        if(level==0)//找到匹配的括号.
                                break;
                }
       
                if(*(pos+1)==0)//下一个字符是结尾
                {
                        *pos = 0;
                        memmove(expre,expre+1,pos-expre);
                }
        }
}

bool IsNum(const char *str,double & v)
{
        char *end;
        double temp = strtod(str,&end);
       
        if(end==str+strlen(str))
        {
                v = temp;
                return true;
        }
       
        return false;
}

int FindOp(const char *expre)//找出最后一个优先级最低的运算符.
{
        const char *pos;
        int  level = 0;//当前位置的括号层数
       
        int  pos1 = -1; //最后一个 + - 出现的位置.
        int  pos2 = -1; //最后一个 * / 出现的位置.
        int  pos3 = -1; //最后一个 ^   出现的位置.
       
        for(pos=expre; *pos; ++pos)
        {
                if(*pos=='(')      ++level;
                else if(*pos==')') --level;
               
                if(level==0)//不在括号中.
                {
                        if(*pos=='+'||*pos=='-')
                        {
                                pos1 = pos - expre;
                        }
                        else if(*pos=='*'||*pos=='/')
                        {
                                pos2 = pos - expre;
                        }
                        else if(*pos=='^')
                        {
                                pos3 = pos - expre;
                        }
                }
        }
       
        int op_pos = -1;

        if(pos1!=-1)      op_pos = pos1;
        else if(pos2!=-1) op_pos = pos2;
        else if(pos3!=-1) op_pos = pos3;
        else {} //找不到运算符.

        return op_pos;
}

//把表达式拆成 a op b 的形式,并计算其值.
double DivExpression(const char *expre)
{
        double result = 999999999999;

        char buf[300];
        strcpy(buf,expre);

        DelBracket(buf);//去括号,当整个表达式被一个括号包围时,可直接去掉.

        int pos = FindOp(buf);//找到最右边的最低优先级的运算符.

        if(pos!=-1)//能拆成 a op b 的形式
        {
                char a[300];
                char b[300];

                strncpy(a,buf,pos);
                a[pos] = 0;

                char op = buf[pos];

                ++pos;
                strcpy(b,buf+pos);

                double a_v,b_v;

                if(strlen(a)==0) a_v = 0.0; //a是空字符串.
                else if(!IsNum(a,a_v))
                         a_v = DivExpression(a);

                if(!IsNum(b,b_v))
                        b_v =DivExpression(b); 

                switch(op)
                {
                case  '+':  result = a_v+b_v;       break;
                case  '-':  result = a_v-b_v;       break;
                case  '*':  result = a_v*b_v;       break;
                case  '/':  result = a_v/b_v;       break;
                case  '^':  result = pow(a_v,b_v);  break;
                default:    assert(0);              break;
                }
        }
    else//找不到二元操作符.可能是一元/三元操作符表达式.
        {
                IsNum(buf,result);//这里只支持表达式就是一个数.
        }

        return result;
}

int main(int argc, char* argv[])
{
        typedef struct
        {
                char * expre;
                double result;
        }Item;

        Item test[] = {
                {"1",       1},
                {"1+2",     3},
                {"1-2+4",   3},
                {"1+2-4",  -1},
                {"1+2*4",   9},
                {"1+4/2",   3},
                {"3*2-4/1", 2},
                {"3^2-4*2", 1},
                {"5-(3+1)", 1},
                {"5-(3+1)/2", 3},
                {"5^2*3-(4+12/(3-1))/2", 70},
                {"3^3*((6+3)-5)",108},
                {"-(3+8)", -11},
                {"-11+(-3)",-14},
                {"-(-5)*3",15},
                {"(-5)^2",25},
                {"-5^2",-25},
                {"-5^(-2)",-0.04},
                {"5*(3+1)/2^2", 5},
        };

        for(int i=0;i<sizeof(test)/sizeof(Item);++i)
        {
                double re = DivExpression(test[i].expre);
                double diff = re-test[i].result;

                printf("%s = %.2f \t\t\t\t\t",test[i].expre,test[i].result);

                if(diff<0.0001 && diff>-0.0001)
                {
                        printf("ok\n");
                }
                else
                {
                        printf("error: %.2f\n",re);
                }
        }

        return 0;
}