P1300 表达式求值：双栈模拟
用两个栈，按运算符优先级和括号规则计算中缀表达式
模拟栈表达式解析运算符优先级1. 题目要做什么？
输入一个不含空格的算术表达式，例如 2+3*(2+2*3-2)/(5-3)，其中含有非负整数、+ - * / 和圆括号，输出它的计算结果。
核心难点：不能从左到右直接计算。乘除法优先于加减法，括号内必须先算，而且减法、除法还要保证从左到右的结合顺序。
2. 为什么使用两个栈？
数字栈 numbers
暂存读到的数字，以及每次归约后得到的中间结果。
例如读到 12、34，就依次压栈。
运算符栈 operators
暂存尚未执行的运算符和左括号 (。
它帮助我们延后低优先级运算，并在恰当时机执行计算。
把每个运算符看成“等待执行的指令”。遇到更低或相同优先级的后续运算符时，栈顶指令就不能再等，应先执行。
3. 四条扫描规则
- 读到数字：连续读取所有数字字符，组成一个完整整数，压入数字栈。
- 读到左括号 (：直接压入运算符栈，作为边界。
- 读到右括号 )：右括号不入栈。不断计算，直到栈顶是匹配的左括号；再弹出左括号。
- 读到普通运算符：只要栈顶不是左括号，且栈顶运算符优先级大于或等于当前运算符，就先计算栈顶运算符；最后将当前运算符压栈。
为什么是“大于或等于”？保证同级运算从左到右。例如 8-3-2 必须算成 (8-3)-2=3，而不是 8-(3-2)=7。
4. 归约一次：evaluate()
当需要执行栈顶运算符时，从数字栈弹出两个数：
right = 栈顶，再取 left = 新的栈顶，计算 left 运算符 right，将结果压回数字栈。
顺序不能反：若表达式为 10-3，先弹出的 3 是右操作数，结果应为 10-3，而不是 3-10。
5. 示例推演：2+3*(2+2*3-2)/(5-3)
| 读入字符 | 处理 | 数字栈（底 → 顶） | 运算符栈（底 → 顶） |
|---|---|---|---|
| 2 | 数字入栈 | 2 | 空 |
| + | 运算符入栈 | 2 | + |
| 3、* | 3 入数字栈；* 优先级更高，直接入运算符栈 | 2, 3 | + * |
| ( | 左括号入栈，形成边界 | 2, 3 | + * ( |
| 2、+ | 2 入数字栈；栈顶为左括号，+ 直接入栈 | 2, 3, 2 | + * ( + |
| 2、* | 2 入数字栈；* 优先级更高，直接入栈 | 2, 3, 2, 2 | + * ( + * |
| 3、- | 3 入栈；读到 - 时依次算 2*3=6、2+6=8，再将 - 入栈 | 2, 3, 8 | + * ( - |
| 2、) | 2 入栈；计算 8-2=6，弹出左括号 | 2, 3, 6 | + * |
| / | 栈顶 * 与 / 同级，先算 3*6=18，再将 / 入栈 | 2, 18 | + / |
| (、5、-、3 | 括号内依次入栈 | 2, 24, 5, 3 | + / ( - |
| ) | 计算 5-3=2，弹出左括号 | 2, 24, 2 | + / |
| 结束 | 依次算 18/2=9、2+9=11 | 11 | 空 |
6. 点击查看运行过程
下面按 2+3*(2+2*3-2)/(5-3) 的关键步骤展示两个栈的变化。
第 0 / 19 步
数字栈（底 → 顶）
空
运算符栈（底 → 顶）
空
点击“下一步”开始。
7. 对应代码
下面是 P1300 的核心实现。注意优先级比较中的 >=，它正是保证左结合的关键。
- #include <cctype>
- #include <iostream>
- #include <stack>
- #include <string>
- using namespace std;
- stack<int> numbers; // 操作数和中间结果
- stack<char> operators; // 尚未执行的运算符和左括号
- int priority(char op) {
- if (op == '+' || op == '-') return 1;
- if (op == '*' || op == '/') return 2;
- return 0;
- }
- void evaluate() {
- int right = numbers.top(); numbers.pop(); // 先弹出右操作数
- int left = numbers.top(); numbers.pop(); // 再弹出左操作数
- char op = operators.top(); operators.pop();
- if (op == '+') numbers.push(left + right);
- else if (op == '-') numbers.push(left - right);
- else if (op == '*') numbers.push(left * right);
- else numbers.push(left / right);
- }
- int main() {
- string expression;
- cin >> expression;
- for (int i = 0; i < expression.size(); ++i) {
- char ch = expression[i];
- if (isdigit(ch)) {
- int value = 0;
- // 连续读取数字，支持多位整数
- while (i < expression.size() && isdigit(expression[i])) {
- value = value * 10 + (expression[i] - '0');
- ++i;
- }
- --i; // 抵消外层 for 的 ++i
- numbers.push(value);
- } else if (ch == '(') {
- operators.push(ch); // 左括号直接入栈，作为边界
- } else if (ch == ')') {
- // 右括号不入栈，计算到左括号为止
- while (operators.top() != '(') evaluate();
- operators.pop(); // 弹出左括号
- } else {
- while (!operators.empty() && operators.top() != '(' &&
- priority(operators.top()) >= priority(ch)) evaluate(); // 先归约高或同级运算
- operators.push(ch); // 当前运算符等待执行
- }
- }
- while (!operators.empty()) evaluate(); // 处理剩余运算符
- cout << numbers.top() << '\n';
- }
8. 复杂度与易错点
时间复杂度 O(n)每个数字、运算符最多入栈和出栈一次。
空间复杂度 O(n)两个栈在最坏情况下都可能保存 O(n) 个元素。
常见错误
- 把 right 与 left 的弹出顺序写反，导致减法和除法错误。
- 比较优先级时只写 >，导致连续减法、连续除法错误。
- 处理右括号时忘记弹出左括号。
- 只读一个数字字符，忽略多位数。