中缀表达式值

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

题目描述

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

输入

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

输出

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

样例输入

1+2*8-9@

样例输出

8

正解：栈+后缀表达式

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

AC代码

#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;
}

最后

以上就是眼睛大小丸子为你收集整理的中缀表达式值 栈中缀表达式值的全部内容，希望文章能够帮你解决中缀表达式值 栈中缀表达式值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。