AcWing 3302. 表达式求值
原题链接
中等
//中缀表达式求值 转换为表达式树 所有内部节点都是运算符 所有根节点都是数
//中缀表达式:整个表达式树的中序遍历 中序遍历涉及到优先级问题
//本题如果直接写中序遍历:2+2*1+1 发现运算符的优先级和题目定义不一样
//所以必须加括号 可以用递归做 也可以借助栈 达到递归的效果
//后缀表达式不用加括号
/*
当一个节点的左子树已经遍历完了,则左子树的值可以算出,再遍历这个跟节点(一个运算符)
但是它的右子树还没有被遍历,接着遍历右子树的左儿子、跟、右儿子,,,,,,
问题:如何判断某棵子树被遍历完,当遍历完了就可以把整颗子树的值计算出
答:当节点往树的上方走时,说明子树被遍历完了,对应运算符
上面运算符的优先级比下面运算符的优先及低
则:当前运算符优先级<=上一个(节点往上走)的运算符的优先级 就把上一个运算符操作一下 就表示刚刚子树已经被遍历完了
如果遇到括号,遇到左括号不受影响,遇到右括号,把括号里的所有运算符全部操作
如果遇到右括号,不管三七二十一,从右往左操作一遍
*/
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map> //哈希表
using namespace std;
stack<char> op; // 声明一个字符类型的操作符栈,用于存储运算符
stack<int> num; // 声明一个整数类型的操作数栈,用于存储操作数
unordered_map<char, int> pr = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; // 创建一个unordered_map,存储每个运算符对应的优先级
void eval()
{
// 定义一个函数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()
{
string s;
cin >> s; // 从标准输入读取一个字符串,这个字符串包含待求值的表达式
for(int i = 0; i < s.size(); i++)
{
char c = s[i];
if(isdigit(c))
{
// 如果当前字符是数字,构建完整的整数并压入操作数栈
int x = 0, j = i;
while(j < s.size() && isdigit(s[j])) x = 10 * x + s[j++] - '0';
i = j - 1; // 更新i的值,使其指向数字串的最后一个字符
num.push(x); // 将构建好的整数压入操作数栈
}
else if(c == '(')
{
op.push(c); // 如果当前字符是左括号'(',将其压入操作符栈
}
else if(c == ')')
{
// 如果当前字符是右括号')',执行操作符栈中的操作,直到遇到左括号'('
while(op.size() && op.top() != '(') eval(); // 反复执行eval函数,直到操作符栈为空或者遇到左括号
op.pop(); // 弹出左括号,将其丢弃
}
else
{
// 如果当前字符是运算符,执行操作符栈中的操作,直到遇到优先级低于或等于当前运算符的运算符
while(op.size() && pr[op.top()] >= pr[c]) eval(); // 反复执行eval函数,直到操作符栈为空或者栈顶运算符优先级小于当前运算符
op.push(c); // 将当前运算符压入操作符栈
}
}
// 处理完输入字符串中的所有字符后,执行操作符栈中剩余的操作
while(op.size()) eval(); // 反复执行eval函数,直到操作符栈为空
cout << num.top() << endl; // 输出操作数栈顶的值,即为表达式的最终求值结果
return 0; // 返回0,表示程序正常结束
}