当前位置:网站首页>栈 AcWing 3302. 表达式求值
栈 AcWing 3302. 表达式求值
2022-07-05 06:16:00 【T_Y_F666】
栈 AcWing 3302. 表达式求值
原题链接
算法标签
栈 表达式求值
思路
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
stack<int> num;
stack<int> op;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
void eval(){
int b=num.top();
num.pop();
int a=num.top();
num.pop();
char 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);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 定义运算符优先级
unordered_map<char, int> ump={
{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
string s;
cin>>s;
rep(i, 0, s.size()){
// 提取字符串中数字
if(isdigit(s[i])){
int j=i, x=0;
while(j<s.size()&&isdigit(s[j])){
x=x*10+s[j++]-'0';
}
i=j-1;
num.push(x);
}else if(s[i]=='('){ // ( 入栈
op.push(s[i]);
}else if(s[i]==')'){ // ) 与 ( 之间数字进行运算
while(op.top()!='('){
eval();
}
// ) 出栈
op.pop();
}else{ // + - * / 运算 待入栈运算符优先级低,则先计算 后将计算结果入栈
while(op.size()&&op.top()!='('&&ump[op.top()]>=ump[s[i]]){
eval();
}
// 否则 先入栈 后计算
op.push(s[i]);
}
}
// 将所有未操作运算符 从前至后操作
while(op.size()){
eval();
}
printf("%lld", num.top());
return 0;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
猜你喜欢
随机推荐
Redis publish subscribe command line implementation
C Primer Plus Chapter 15 (bit operation)
【Rust 笔记】13-迭代器(中)
MySQL advanced part 1: triggers
Leetcode-6111: spiral matrix IV
Navicat连接Oracle数据库报错ORA-28547或ORA-03135
【Rust 笔记】13-迭代器(下)
LaMDA 不可能觉醒吗?
[BMZCTF-pwn] ectf-2014 seddit
leetcode-22:括号生成
JS quickly converts JSON data into URL parameters
Sqlmap tutorial (II) practical skills I
Binary search template
Spark中groupByKey() 和 reduceByKey() 和combineByKey()
[rust notes] 16 input and output (Part 2)
Leetcode array operation
MySQL advanced part 1: index
Records of some tools 2022
Règlement sur la sécurité des réseaux dans les écoles professionnelles secondaires du concours de compétences des écoles professionnelles de la province de Guizhou en 2022
1039 Course List for Student