首页 > 代码库 > 中缀表达式值
中缀表达式值
中缀表达式值(Expr.cpp)
【问题描述】
输入一个中缀表达式（由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“—”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。
注意：必须用栈操作，不能直接输出表达式的值。如果再考虑是实数运算呢？
【输入文件】Expr.in
输入文件的第一行为一个以@结束的字符串。
【输出文件】Expr.out
如果表达式不合法，请输出“NO”，要求大写。
如果表达式合法，请输出计算结果。
【输入样例】
1＋2×8―9
【输出样例】
8
‘
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 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<strlen(s)) 79 { 80 while (s[i]==‘(‘) //左括号处理,压入左括号,有了左括号才能进行与右括号的匹配 while (symbol[p]!=‘(‘) 81 { 82 push(); 83 i++; 84 } 85 int x=0; 86 while (s[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<strlen(s)&&s[i-1]==‘)‘);//当检测到右括号时，可以运算括号内的内容 105 }106 printf("Result=%d", number[0]);//因为所有的运算全部是建立在括号之内的，所以随着运算符的减少（运算符减少同时标志着需要操作的数减少）和最后的p--，结果一定保存在number[0]内 107 return 0;108 }
中缀表达式值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。