表达式求值

对于给定表达式，如5+10*(6-4)-10/5，求出表达式的值。

表达式求值这类的题目非常常见，本文也没有提出什么新的方法，只是在看书之余练练手。

方法一：

对于一个给定的表达式，如何求它所对应的值。首先如果能够确定整个表达式中最后被执行的运算符，那么根据运算符的位置可以把整个表达式分成两部分，对这两部分再分别求解，然后将求得的值合并。

输入：5+10*(6-4)-10/5

输出：23

注意，由于通常获得的求值表达式都是字符串，对于操作数不能直接操作，需要进行转化

囧：发现一个bug，由于运算数都是整数，而'+','-','*','/'四个操作符也都是整数，最后如果出现一个整数的值刚好等于运算符就会出错，表达式转化的时候可以用一个符号来标志是运算数还是运算符，暂时未修改

  1 #include <iostream>
  2 #include <string.h>
  3 #include <cassert>
  4 #include <fstream>
  5 using namespace std;
  6 
  7 /** 
  8  * 对表示式进行求值
  9  *
 10  * @param num 
 11  * @param x 表达式的开始位置
 12  * @param y 表达式最后位置的下一个位置
 13  *
 14  * @return 结果值
 15  */
 16 int calculate(int * num, int x, int y)
 17 {
 18     assert(num != NULL);
 19     if(y-x==1)          //如果只有一个元素肯定是值节点
 20         return num[x];
 21     int c1=-1;
 22     int c2=-1;
 23     int p=0;          //p的作用是用来标识表达式是处于括号内还是括号外
 24     for(int i=x;i<y;i++)
 25     {
 26         switch(num[i])
 27         {
 28         case '+':
 29         case '-':
 30             if(!p) c1=i;break;
 31         case '*':
 32         case '/':
 33             if(!p) c2=i;break;
 34         case '(':
 35             p++;break;
 36         case ')':
 37             p--;break;
 38         }
 39     }
 40     //每次标识最后一个运算的运算符,如果不存在，表明整个表达式被括号包
 41     //围着
 42     if(c1<0) c1=c2;
 43     if(c1<0)
 44         return calculate(num,x+1,y-1);
 45     switch(num[c1])
 46     {
 47     case '+':
 48         return calculate(num,x,c1) + calculate(num,c1+1,y);
 49     case '-':
 50         return calculate(num,x,c1) - calculate(num,c1+1,y);
 51 
 52     case '*':
 53         return calculate(num,x,c1) *  calculate(num,c1+1,y);
 54 
 55     case '/':
 56         return calculate(num,x,c1) / calculate(num,c1+1,y);
 57     }
 58 }
 59 
 60 /**
 61  * 将字符串的表达式转化成数组表示形式
 62  *
 63  * @param s 原表达式
 64  * @param num 存放转化表达式的数组
 65  *
 66  * @return 返回转化成数组形式表达式的长度
 67  */
 68 int convert(char * s, int * num)
 69 {
 70     assert(s!=NULL && num != NULL);
 71     int len = strlen(s);
 72     int c=0;
 73     for(int i=0;i<len;)
 74     {
 75         if(s[i]<'0' || s[i]>'9')
 76         {
 77             num[c++]=s[i];
 78             i++;
 79         }
 80         else
 81         {
 82             int tmp=0;
 83             while(i<len && s[i]>='0' && s[i]<='9')
 84             {
 85                 tmp=tmp * 10 + s[i]-'0';
 86                 i++;
 87             }
 88             num[c++]=tmp;
 89         }
 90     }
 91     return c;
 92 }
 93 
 94 int main()
 95 {
 96     char s[100];
 97     int num[100];
 98     cin>>s;
 99     //将原字符串形式表示式进行转化
100     int n = convert(s,num);
101     cout<<calculate(num,0,13)<<endl;
102     return 0;
103 }