【题目来源】
AcWing：3302. 表达式求值 - AcWing题库
【题目描述】
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
【输入】
共一行，为给定表达式。
【输出】
共一行，为表达式的结果。
【输入样例】
(2+2)*(1+1)
【输出样例】
8
【解题思路】
【算法标签】
《AcWing 3302 表达式求值》 #栈# #表达式求值#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义两个栈：操作数栈和运算符栈
stack<int> num; // 存储操作数的栈（整数类型）
stack<char> op; // 存储运算符的栈（字符类型）/*** 执行栈顶运算：从栈中弹出两个操作数和一个运算符，计算结果后压回栈中* 注意：先弹出的是第二个操作数，后弹出的是第一个操作数*/
void eval()
{// 从操作数栈中弹出第二个操作数（栈顶元素）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()
{// 定义运算符优先级映射表// 优先级数值越大，优先级越高unordered_map<char, int> pr = {{'+', 1}, // 加法优先级为1{'-', 1}, // 减法优先级为1 {'*', 2}, // 乘法优先级为2{'/', 2} // 除法优先级为2};string str; // 存储输入的中缀表达式字符串cin >> str; // 读取表达式// 遍历表达式中的每个字符for (int i = 0; i < str.size(); i++) {auto c = str[i]; // 当前字符// 处理数字字符if (isdigit(c)) {int x = 0; // 当前数字的值int j = i; // 用于扫描连续数字的指针// 提取连续的数字字符，处理多位数while (j < str.size() && isdigit(str[j])){// 将字符转换为数字并累加x = x * 10 + (str[j] - '0');j++;}i = j - 1; // 更新主循环索引，跳过已处理的数字num.push(x); // 将数字压入操作数栈} // 处理左括号：直接压入运算符栈else if (c == '(') {op.push(c);}// 处理右括号：计算括号内的所有表达式else if (c == ')') {// 不断计算直到遇到左括号while (op.top() != '(') {eval(); // 执行计算}op.pop(); // 弹出左括号}// 处理运算符：+ - * /else {// 当栈不为空，且栈顶不是左括号，且栈顶运算符优先级不低于当前运算符时while (op.size() > 0 && op.top() != '(' && pr[op.top()] >= pr[c]) {eval(); // 先计算优先级高的运算}op.push(c); // 当前运算符压栈}}// 处理运算符栈中剩余的所有运算while (op.size() > 0) {eval();}// 输出最终结果（操作数栈中唯一的元素）cout << num.top() << endl;return 0;
}
【运行结果】
(2+2)*(1+1)
8