AcWing 3302. 表达式求值
原题链接
中等
作者:
南川嘉子
,
2024-09-12 09:56:07
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
#include<unordered_map>
/*
一个关联容器,它存储了键值对(key-value pairs),
其中每个键(key)都是唯一的。unordered_map使用哈希表来存储
元素的存储顺序是无序的,
但查找、插入和删除的时间复杂度在平均情况下是常数时间O(1)
*/
using namespace std;
const int N=100010;
stack<int> num;//运算数栈
stack<int> op;//操作符栈
void eval(){
auto b=num.top(); num.pop();
auto a=num.top(); num.pop();
auto c=op.top(); op.pop();
int x;
if(c=='+') x=a+b;
else if(c=='-') x=a-b;
else if(c=='*') x=a*b;
else x=a/b;
num.push(x);
}
unordered_map<char,int> pri{ {'+',1},{'-',1},{'*',2},{'/',2} };//运算符优先级表
int main(){
string str;
cin>>str;
for(int i=0;i<str.size();i++){//for循环只是把字符走完了
auto c=str[i];
if(isdigit(c)){
int x=0,j=i;
while(j<str.size()&&isdigit(str[j])){
x=x*10+str[j++]-'0';
}//j出while循环的那个是不满足的位置 下次for要从这个位置开始
i=j-1;//for循环第三段会让i++成为j那个不满足while循环的位置
num.push(x);
}else if(c=='('){//左括号无优先级,直接入栈
op.push(c);
}else if(c==')'){//比如+(4+5*3) (先入栈
//运算数栈 4 5 3 运算符栈 ( + * 之后到)发现栈顶不是(所以先做弹栈运算
while(op.top()!='(') eval();//运算到知道栈顶是(
op.pop();//终于运算到栈顶是(冒出来了 (出栈
}else{
while(op.size()&&pri[op.top()]>=pri[str[i]]){//栈顶优先级>=新来的
eval();//栈顶先算 相等也是
}
op.push(str[i]); //算完了或者本来栈顶优先级<新来的
}
}
while(op.size()) eval();//for走完时候 可能运算栈还有剩余的进行运算
cout<<num.top()<<endl;
return 0;
}