表达式求值的递归算法
表达式求值,一般采用逆波兰算法,即转化为后缀表达式再进行计算。这当然很好。可是这个算法逻辑上不那么直观，如果是笔试或机考的话，除非你最近恰好看过该算法，或者你就是研究这些算法的，一般估计很难在限定的时间内理清头绪并写出代码。
如果直接采用中缀表达式求值，就更复杂了。如果不是准备充分，相信很难在笔试/机考的情况下完成代码。本人早几天去笔试就碰到这个题目,两小时,机考.当时看到这个题目，想了一个小时，也没想起逆波兰算法。在学校学的东西基本都忘的差不多了。最后只好直接对中缀表达式求值。结果当然是没搞定。还好该职位并不是很有吸引力的，不然就亏大了。
事后想想，这个问题应该用递归的方法解决。这才是逻辑简单的，适合应试的算法。不废话，先贴代码。
(下面的代码支持 加减乘除，乘方，括号。没有进行错误检查。)
#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错误等等。
