表达式求值 (栈) 用C++实现

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <stack>

 #include <cstring>

 using namespace std;

 char Precede(char a, char b) { //判断运算符优先级

     int i, j;

     char Table[][] = {

         {' ','+','-','*','/','(',')','='},

         {'+','>','>','<','<','<','>','>'},

         {'-','>','>','<','<','<','>','>'},

         {'*','>','>','>','>','<','>','>'},

         {'/','>','>','>','>','<','>','>'},

         {'(','<','<','<','<','<','=',' '},

         {')','>','>','>','>',' ','>','>'},

         {'=','<','<','<','<','<',' ','='}

     };  //优先级表格

     for(i=; i<; i++)

         if(Table[][i]==a)  //寻找运算符a

             break;

     for(j=; j<; j++) //寻找运算符b

         if(Table[j][]==b)

             break;

     return Table[j][i];

 }

 bool Calcu_temp(double a, char theta, double b, double &r) { //计算二元表达式的值

     if(theta=='+')

         r = a + b;

     else if(theta=='-')

         r = a - b;

     else if(theta=='*')

         r = a * b;

     else {

         if(fabs(b-0.0)<1e-)  //如果除数为0,返回错误信息

             return false;

         else

             r = a / b;

     }

     return true;

 }

 bool IsOper(char ch) { //判断字符ch是否为运算符

     char ptr[] = {'+', '-', '*', '/', '(', ')', '='};

     int i;

     for(i=; i<; i++) {

         if(ch==ptr[i])

             return true;

     }

     return false;

 }

 bool Calculate(char s[], double &result) { //计算表达式的结果

     char theta;

     int i = , j, point = ;

     double a, b, r, num = ;

     stack<double> num_stack;  //数字栈

     stack<char> oper_stack;  //运算符栈

     oper_stack.push('=');

     while(s[i]!='=' || oper_stack.top()!='=') { //对表达式a进行计算

         if((s[i]>='' && s[i]<='') || s[i]=='.') { //字符是数字或者小数点

             num = ;  //初始化数字为0

             point = ;  //point用来标记是否出现小数点以及当前处于小数点后第x位,point==10^x

             if(s[i]=='.')

                 point = ;

             else

                 num = s[i] - ;

             j = i + ;

             while(!IsOper(s[j])) { //继续往后查找并记录该数字,直到该数字结束遇到运算符为止

                 if(s[j]=='.') {

                     point = ;

                     j++;

                     continue;

                 }

                 if(!point)  //整数部分

                     num = num *  + ( s[j] -  );

                 else {

                     num = num + 1.0 * ( s[j] -  ) / point;  //小数部分

                     point *= ;  //小数位数后移一位

                 }

                 j++;

             }

             i = j;

             num_stack.push(num);  //将该数字压入栈中

         }

         else if(IsOper(s[i])) { //字符是运算符

             switch(Precede(s[i],oper_stack.top())) { //该运算符和栈顶运算符进行优先级比较并做相关处理

             case '<':

                 oper_stack.push(s[i++]);

                 break;

             case '=':

                 oper_stack.pop();

                 i++;

                 break;

             case '>':

                 theta = oper_stack.top();  //从栈中弹出一个运算符进行计算

                 oper_stack.pop();

                 b = num_stack.top();  //弹出两个数字,注意顺序,先弹出的数是第二个操作数

                 num_stack.pop();

                 a = num_stack.top();

                 num_stack.pop();

                 if ( Calcu_temp(a, theta, b, r) )  //计算并判断是否有除数等于0的情况

                     num_stack.push(r);  //若正常,则将结果压入栈中

                 else

                     return false;  //出现除数为0的情况,返回错误信息

                 break;

             }

         }

     }

     result = num_stack.top();  //最后数字栈中的数即为表达式的最终结果

     return true;

 }

 bool Check(char s[]) { //检查表达式括号是否匹配

     int flag=, i;

     for(i=; s[i]!=; i++) {

         if(s[i]=='(')

             flag++;

         if(s[i]==')')

             flag--;

     }

     if(flag)

         return false;

     else

         return true;

 }

 int main() {

 //    freopen("in.txt", "r", stdin);

     int i, j;

     char s1[], s2[];

     double result;
printf("\t\t表达式求值(栈)\n");
printf("******************************************************************\n");
printf("请输入表达式,等号不用输入:\n"); while(gets(s1)!=NULL) { //输入表达式 if(strlen(s1)== && s1[]=='') break; for(i=,j=; s1[i]!=; i++) { //将表达式转换为规格化的表达式,并在末尾加上“=”,保存在s2中 if(s1[i]==' ') continue; s2[j++] = s1[i]; } s2[j++] = '='; s2[j] = '\0'; if(Check(s2)) { //检查括号是否匹配 if(Calculate(s2, result)) //计算并检查表达式中是否出现除数为0的情况 printf("%lf\n",result); else printf("除数不能为0\n"); } else printf("括号不匹配\n"); } return ; }
上一篇:JQUERY知识总结


下一篇:BestCoder #47 1001&&1002