中缀表达式值

(Expr.cpp)

【问题描述】

       输入一个中缀表达式（由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“—”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。

      注意：必须用栈操作，不能直接输出表达式的值。如果再考虑是实数运算呢？

【输入文件】

Expr.in

      输入文件的第一行为一个以@结束的字符串。

【输出文件】

Expr.

out

      如果表达式不合法，请输出“NO”，要求大写。

      如果表达式合法，请输出计算结果。

【输入样例】

1＋2×8―9

【输出样例】

8

 ‘

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 using namespace std;  6 int  number[101],i=0, p=1;  7 char symbol[101],s[256],t[256];  8 void push()      //算符入栈运算  9 { 10   symbol[++p]=s[i]; 11 } 12 void pop()       //运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算 13 { 14    switch (symbol[p--])//运算完成之后扔掉运算符,也标志着需要运算的数已经运算完成  15    { 16       case '+': 17       { 18           number[p]+=number[p + 1]; 19           break;  20       } 21       case '-': 22       { 23           number[p]-=number[p + 1]; 24           break;     25       } 26          case '*': 27       { 28           number[p]*=number[p + 1]; 29          break; 30         } 31       case '/': 32       { 33           number[p]/=number[p + 1]; 34           break; 35       } 36       case '^': 37       { 38         number[p]=pow(number[p],number[p + 1]); 39       } 40    } 41 } 42 bool can()            //判断运算符的优先级别,建立标志函数,能否进行运算  43 { 44   if ((s[i]=='+'||s[i]=='-')&&symbol[p]!='(') //在括号之内  45   return 1; 46   if ((s[i]=='*'||s[i]=='/')&&(symbol[p]=='*'||symbol[p]=='/')) 47   //若遇到乘除且p对应的恰好是乘除  48   return 1; 49   return 0; 50 } 51 bool judge(char s[256]) 52 {  53     int top=0,i=0; 54     while (s[i]!='@')  55     { 56         if (s[i]=='(') top++; 57         if (s[i]==')')  58         { 59            if (top>0) top--; 60              else return 0; 61         } 62         i++; 63     } 64     if (top!=0) return 0;          //检测栈是否为空。不空则说明有未匹配的括号 65     else return 1; 66 } 67 int main() 68 { 69     gets(s); 70     if(judge(s)==0) 71     { 72         cout<<"NO"; 73         return 0; 74     } 75      76     s[strlen(s)]=')'; 77   symbol[p]='('; 78   while (i
           
            ='0'&&s[i]<='9')  //取数入操作数栈 87          x=x*10+s[i++]-'0'; 88       number[p]=x; 89       do 90       {   91           if (s[i]==')')            //当右括号后面还有右括号时处理 92           { 93             while (symbol[p]!='(')  94             pop();//当括号内还有算式没有算完时进行运算  95             number[--p]=number[p + 1];//当运算完成以后左括号已经没有意义，所以将指针p移向前一个运算符，并复制所得的结果  96           } 97           else 98           {                   //根据标志函数值作运算符入栈或出栈运算处理 99             while (can()) 100             pop();// 当可以进行运算时运算，然后压入一个运算符 101             push();102           }103         i++;104       }while (i