中缀表达式值(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 }