中缀表达式值栈中缀表达式值

98 阅读 0 评论 65 点赞

我是靠谱客的博主眼睛大小丸子，这篇文章主要介绍中缀表达式值栈中缀表达式值，现在分享给大家，希望可以做个参考。

中缀表达式值

时间限制: 1 Sec 内存限制: 128 MB

题目描述

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

输入

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

输出

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

样例输入

1+2*8-9@

样例输出

正解：栈+后缀表达式

我们用两个栈分别记录数值和符号，然后化为后缀表达式求值即可，记得还要开一个数组记录符号优先级

AC代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
using namespace std;
int t1,t2,n,m,flag,r[205],s1[1010];
char a[1010],s2[1010];
inline void out(char c) {
if(c=='+') s1[--t1]+=s1[t1+1];
else if(c=='-') s1[--t1]-=s1[t1+1];
else if(c=='*') s1[--t1]*=s1[t1+1];
else if(c=='/') s1[--t1]/=s1[t1+1];
}
int main() {
cin>>a;
r['+']=1,r['-']=1;
r['*']=2,r['/']=2;
if(r[a[0]]) flag=1;
int i=0;
while(a[i]!='') {
if(a[i]>='0'&&a[i]<='9') {
int x=0;
while(a[i]>='0'&&a[i]<='9') {
x=x*10+a[i]-'0';
i++;
}
s1[++t1]=x;
}
if(a[i]=='(') {
s2[++t2]='(';
m++;
}
if(a[i]==')') {
n++;
while(s2[t2]!='(') {
out(s2[t2]);
t2--;
}
t2--;
}
if(r[a[i]]&&r[a[i+1]]) flag=1;
if(r[a[i]]) {
while(r[a[i]]<=r[s2[t2]]) {
out(s2[t2]);
t2--;
}
t2++;
s2[t2]=a[i];
}
i++;
if(flag) {
printf("NO");
return 0;
}
}
while(t2!=0) {
out(s2[t2]);
t2--;
}
if(m!=n) {
printf("NO");
return 0;
}
printf("%d",s1[t1]);
return 0;
}