给定一个表达式,其中运算符仅包含 +,-,,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)(-(1+1)+2) 之类表达式均不会出现。题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中,均不超过 231?1。
题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1?4)=?1。
C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
输入格式
共一行,为给定表达式。
输出格式
共一行,为表达式的结果。
数据范围
表达式的长度不超过 105。
输入样例:
(2+2)*(1+1)
输出样例:
8
计算匹配的核心在于两个栈:运算符栈op,操作数栈num
计算规则为:
- 定义运算符优先级表,并在计算中保证同级别运算符左侧先算
- 一般定义{‘+’, 1}, {‘-‘, 1}, {‘*’, 2}, {‘/’, 2}
- 遍历输入子串,取字符
- 为数字则计算数字,存入num
- 为左括号入op
- 为右括号则一直计算到左括号出现,顺便把左括号弹掉
- 其他符号则调用eval计算@
- eval函数需要输入操作符,每次取num栈的头两个数进行运算,注意栈内数字和计算顺序相反
- @处eval会先计算op栈内的元素,触发eval计算的条件是:当前符号运算优先级低于op栈顶的优先级
- 当前运算符为+,对于22+3,当输入+时不能先算2+3而应该先算22
详细代码
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
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);
}
int main() {
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
string str;
cin >> str;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
if (isdigit(c)) {
int x = 0, j = i;
while (j < str.size() && isdigit(str[j])) { //j边界条件判断
x = x * 10 + str[j++] - '0';
}
i = j - 1;
num.push(x);
} else if (c == '(') {
op.push(c);
} else if (c == ')') {
while (op.top() != '(') eval(); //@eval操作不需要和push搭配 因为eval会弹出计算中的符号
// printf("%c %d\n",op.top(),num.top());
op.pop(); //弹出左括号,别写成top
} else {
//!op.size()要先判断
while (op.size() && pr[op.top()] >= pr[c]) { //当栈内元素优先级大于等于运算符优先级的计算栈内,相同就是左边先算
eval();
}
op.push(c); //push没进入的操作符
}
}
while (op.size()) eval(); //最后一次要特判
//例如(2+2)*(1+1),计算出来4和2之后循环就结束了,最后还要计算乘法
cout << num.top() << endl;
return 0;
}