表达式求值,一般采用逆波兰算法,即转化为后缀表达式再进行计算。这当然很好。可是这个算法逻辑上不那么直观,如果是笔试或机考的话,除非你最近恰好看过该算法,或者你就是研究这些算法的,一般估计很难在限定的时间内理清头绪并写出代码。 事后想想,这个问题应该用递归的方法解决。这才是逻辑简单的,适合应试的算法。不废话,先贴代码。 (下面的代码支持 加减乘除,乘方,括号。没有进行错误检查。) #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错误等等。
|
|