AcWing 3302. 表达式求值
原题链接
中等
作者:
云_580
,
2024-09-08 16:03:08
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
//定义两个栈,一个数栈,一个符号栈;
int tt1,tt2;
int num[N];
// '/'的ascii码最大为48;
int pri[50];
char op[N];
void cal(){
//注意a和b的顺序
int b = num[tt1--];
int a = num[tt1--];
char ch = op[tt2--];
int res = 0;
if(ch=='+')res=a+b;
if(ch=='-')res=a-b;
if(ch=='*')res=a*b;
if(ch=='/')res=a/b;
num[++tt1]=res;
}
int main(){
string s;
//读入字符串
cin>>s;
//定义优先级,利用Ascii码做映射
pri['+']=1;pri['-']=1;pri['*']=2;pri['/']=2;
for(int i = 0;i<s.size();i++){
if(isdigit(s[i])){
int val=0;
while(i<s.size()&&isdigit(s[i])){
val=val*10+s[i]-'0';
i++;
}
//这里注意i需要减去1,因为for循环的最后i会自增1
//此时i指向的是数字后的第一个不是数字的字符,需要减去1
//和for循环的i自增1相互抵消
i--;
//数入栈
num[++tt1]=val;
}else if(s[i]=='(')op[++tt2]='(';//直接入栈,括号单独处理即可,不用优先级
else if(s[i]==')'){//括号单独处理
while(op[tt2]!='(')cal();
//直到op[tt2]=='(',再将'('弹出即可
tt2--;
}else{
//当符号栈不为空且当前未入栈符号优先级小于等于符号栈顶符号优先级
//原则:优先计算优先级高的运算式
while(tt2&&pri[op[tt2]]>=pri[s[i]])cal();
//压入符号栈
op[++tt2]=s[i];
}
}
//需要处理剩下的符号,直到符号栈为空
while(tt2)cal();
//输出答案即可
cout<<num[tt1];
return 0;
}