3302. 表达式求值
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：
数据保证给定的表达式合法。 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。 题目保证表达式中所有数字均为正整数。 题目保证表达式在中间计算过程以及结果中，均不超过 231−1。 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。 C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval（)函数中的整除也是向下取整，在本题中不能直接使用。 输入格式 共一行，为给定表达式。
输出格式 共一行，为表达式的结果。
数据范围 表达式的长度不超过 10^5^。
输入样例： (2+2)*(1+1) 输出样例： 8
表达式求值【正常数学计算表达式书写顺序】
简记 ： eval计算函数 , op，num栈 ， 定义优先级hash表，'('与')'特判 ：重点优先级分支处理 最后处理剩余运算符,最终结果存在num栈顶
易错eval（)第二个操作数b先出栈，第一个操作数a后出栈
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>//三个参数key,value,类(一般省略)
#include <stack>
using namespace std;
stack<char> op;//运算符栈
stack<int> num;//数值栈
void eval（)//计算函数 【弹栈op一个c,num两个a,b: 操作数a 运算符c 操作数b 根据运算符判断运算方式 计算结果x存回数值栈 】
{
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);//计算结果存回数值栈
}
int main()
{
string s;//字符串
cin >> s;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};//运算符优先级 (key,value)，key唯一标识,value值代表运算优先级大小
for (int i = 0; i < s.size(); i ++ )
{
if (isdigit(s[i]))//判断是否为数字
{
int j = i, x = 0;//j指针记录读取位置 ,x辅助存数值
while (j < s.size() && isdigit(s[j]))
x = x * 10 + s[j ++ ] - '0';//字符串转数字
num.push(x);//计算完放入num数字栈
i = j - 1;//i移动到j : i先移动到j-1, 最后执行i++ == j
} //括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
else if (s[i] == '(') op.push(s[i]);//读到左括号无优先级 ，直接放入操作栈op
else if (s[i] == ')')//读到右括号，运算调用eval函数计算 ， 不断弹栈直到左括号结束 ，再弹出左括号
{
while (op.top() != '(') eval（);
op.pop();
}
else
{
while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]]) //op栈还有操作符且不是左括号 && op运算符优先级 >= 读到的操作符
eval（);//弹一个op栈操作符 ,计算 //待入栈运算符优先级低，则先计算
op.push(s[i]);//操作符入栈
}
}
while (op.size()) eval（);//最后运算到没有操作符，得出表达式运算结果由eval存回num栈顶
cout << num.top() << endl;//调用栈顶
return 0;
}