上海计算机学会2022年10月月赛C++乙组T2算式求值（二）
发布时间
阅读量：
阅读量
算式求值（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
表达式的定义如下：
- 正整数是表达式；
- 如果 e 是表达式，则 (e) 也是表达式
- 如果 e1 与 e2 是表达式，则 e1+e2 与 e1−e2 也都是表达式
给定一个表达式，请计算表达式的值。
输入格式
一个字符序列，表示给定的算式。
输出格式
单个整数：表示表达式的值。
数据范围
数据保证
- 输入的字符序列长度不超过 100,000，
- 其中出现的每个整数均为正整数且不超过 10000。
样例数据
输入:
12-(2+5)
输出:
5
输入:
12-((5+2)-(4-2))
输出:
7
输入:
2+(3-4-5)
输出:
-4
解析：可以使用两个栈来求表达式的值，一个栈存符号，另一个栈存数值，详见代码：
#include<bits/stdc++.h>
using namespace std;
stack <int> su;
stack <char> fu;
string s;
int y[256];
void jisuan(){//计算
int a,b;//数字栈内后两个数
b=su.top();
su.pop();
a=su.top();
su.pop();
char f;//符号栈内最后一个符号
f=fu.top();
fu.pop();
if (f=='-'){
su.push(a-b);
}else if (f=='+'){
su.push(a+b);
}
return;
}
int main() {
cin>>s;
y['(']=0;//符号级别
y['+']=1;
y['-']=1;
int t=0;
bool f=0;
for (int i=0;i<s.size();i++){
if (s[i]>='0'&&s[i]<='9'){//遇到数字
t=t*10+s[i]-'0';
f=1;
}else {//符号
if (f==1){//数字压栈
su.push(t);
f=0;
t=0;
}
if (s[i]=='('){//左括号，直接压栈
fu.push(s[i]);
}else if (s[i]==')'){//右括号
while (fu.top()!='('){//计算直到遇到左括号
jisuan();
}
fu.pop();//弹出左括号
}else if (fu.empty()||y[s[i]]>y[fu.top()]){//栈空或优先级别低于栈内运算符
fu.push(s[i]);//压栈
}else {//否则
//计算，直到栈空或者优先级小于等于栈内符号
while (!fu.empty()&&y[s[i]]<=y[fu.top()]){
jisuan();
}
fu.push(s[i]);//符号压栈
}
}
}
if (f==1){//还有数字
su.push(t);//压栈
f=0;
t=0;
}
while (!fu.empty()){//栈非空，计算到空
jisuan();
}
cout<<su.top()<<endl;//输出结果
return 0;
}
全部评论 (0)
还没有任何评论哟~