表达式求值的递归算法 - lhf 的窝
自定义的打包文件
OpenCv MPR.DLL WNetRestoreConnectionA

表达式求值的递归算法

LiHengFeng posted @ 2009年7月30日 17:53 in 算法 with tags 表达式求值 递归算法 , 3809 阅读
本blog所有文章,除声明了作者外,均为原创。欢迎转载,转载请注明作者。

表达式求值,一般采用逆波兰算法,即转化为后缀表达式再进行计算。这当然很好。可是这个算法逻辑上不那么直观,如果是笔试或机考的话,除非你最近恰好看过该算法,或者你就是研究这些算法的,一般估计很难在限定的时间内理清头绪并写出代码。

如果直接采用中缀表达式求值,就更复杂了。如果不是准备充分,相信很难在笔试/机考的情况下完成代码。本人早几天去笔试就碰到这个题目,两小时,机考.当时看到这个题目,想了一个小时,也没想起逆波兰算法。在学校学的东西基本都忘的差不多了。最后只好直接对中缀表达式求值。结果当然是没搞定。还好该职位并不是很有吸引力的,不然就亏大了。

 事后想想,这个问题应该用递归的方法解决。这才是逻辑简单的,适合应试的算法。不废话,先贴代码。

(下面的代码支持 加减乘除,乘方,括号。没有进行错误检查。) 

#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;
}

 

 

 基本思路是这样的:一个表达式,可视为 a op b的形式,其中op是运算符。如果a,b都是操作数,就可以直接求值了。如果a,b是表达式,则还需再分解为 a op b 的形式,直到分解为全部是数为止。

 这其中有几点要注意的:

1、分解的时候,不能拆括号。即不能把一个括号的内容分解到运算符的两边。

2、只能先从低优先级运算符开始。比如:2*3+4/5,只能从+号开始分解。

3、同一运算符,从最右边的开始分解。比如:2-3+4,只能从 + 号开始分解。

4、如果一个表达式整个被括号包围,该括号可去掉。

5、对于(-5)这样的表达式,有一个小技巧,看成是 (0-5),即如果 a为空的话,则对于的值视为0。这就避免了还要考虑一元运算符。

上面的原则,1,2,3都好理解,都对应到运算规则:a,先算括号内的。 b,先乘方,再乘除,最后加减。c,同优先级,从左到右。

这3条规则保证拆分后的运算顺序和原来的是一样的。

第4条规则,是程序上的需要。因为不能拆开括号,如果一个表达式整个是一个括号,就没办法往下拆分了。所以必须去括号。

规则5是为了统一为二元运算符,这样实现起来简单。

上面的代码没有考虑非法的表达式。如果要考虑,就复杂了。包括括号不匹配,非法字符,多个运算符串联,除0错误等等。

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter