信息学奥赛一本通 1356：计算(calc) —— 从表达式求值到表达式树的构建与遍历

1. 表达式求值基础：从数学到计算机

第一次接触表达式求值问题时，我正参加信息学奥赛的培训。老师写下一个简单的算式"3+5*2"，然后问我们："计算机该如何理解这个表达式？"当时我下意识地回答"先乘除后加减"，但真正动手实现时才发现，这背后藏着精妙的数据结构和算法思想。

表达式求值问题的核心在于运算优先级和括号处理。在数学中，我们天然遵循"先乘除后加减"、"括号内优先"的规则，但计算机需要明确的指令。这就引出了两种经典解法：中缀表达式直接求值和中缀转后缀再求值。

中缀表达式就是我们日常写的算式，比如"(3+5)*2"。它的特点是操作符在操作数中间。直接求值需要同时维护两个栈：

• 操作数栈：存放待计算的数字
• 运算符栈：存放运算符和括号

// 操作符优先级映射示例 int priority(char op) { if(op == '*' || op == '/') return 2; if(op == '+' || op == '-') return 1; return 0; // 括号的特殊处理 }

2. 中缀表达式直接求值：双栈的经典应用

让我们以信息学奥赛一本通1356题为例，详细拆解中缀表达式直接求值的过程。假设输入表达式为"(3+5*2)+3"，下面是逐步分析：

1. 初始化阶段：准备数字栈numStack和运算符栈opStack
2. 扫描字符'('：左括号直接入运算符栈
   • opStack: ['(']
3. 扫描数字3：完整读取数字后压入数字栈
   • numStack: [3]
4. 扫描字符'+'：与栈顶'('比较，优先级更高，入栈
   • opStack: ['(', '+']
5. 扫描数字5：压入数字栈
   • numStack: [3, 5]
6. 扫描字符'*'：优先级高于栈顶'+'，入栈
   • opStack: ['(', '+', '*']
7. 扫描数字2：压入数字栈
   • numStack: [3, 5, 2]
8. 扫描字符')'：开始弹出运算符直到'('
   • 弹出''，计算52=10，10入栈
   • 弹出'+'，计算3+10=13，13入栈
   • 弹出'('，括号处理结束
   • numStack: [13]
9. 扫描字符'+'：栈空直接入栈
   • opStack: ['+']
10. 扫描数字3：压入数字栈
    • numStack: [13, 3]
11. 表达式结束：弹出剩余运算符
    • 弹出'+'，计算13+3=16

实际编程中，我们通常在表达式末尾添加一个优先级最低的')'，确保栈内所有运算符都能被处理。这个小技巧能简化代码逻辑。

3. 中缀转后缀表达式：另一种解题思路

有些情况下，先将中缀表达式转为后缀表达式（逆波兰表示法）会更方便计算。后缀表达式的特点是操作符在操作数之后，比如"3 5 2 * +"对应中缀的"3+5*2"。

转换过程同样使用栈结构：

1. 遇到操作数直接输出
2. 遇到操作符与栈顶比较优先级，弹出更高或相等的操作符
3. 左括号入栈，右括号弹出直到左括号

// 中缀转后缀示例代码片段 while(!opStack.empty() && priority(opStack.top()) >= priority(currentOp)){ suffixExpr.push_back(opStack.top()); opStack.pop(); } opStack.push(currentOp);

后缀表达式的求值过程更简单：

• 遇到数字就入栈
• 遇到操作符就弹出栈顶两个数运算
• 最后栈中剩下的就是结果

我在实际测试中发现，对于复杂表达式，先转后缀再求值的方法代码更清晰，特别是处理带括号的多重嵌套表达式时。

4. 表达式树：结构化思维的体现

前两种方法虽然高效，但缺乏对表达式结构的直观表示。这就引出了更优雅的解决方案——表达式树。这种二叉树结构中：

• 叶子节点都是操作数
• 内部节点都是运算符
• 子树表示子表达式

构建表达式树的过程融合了前两种方法的优点：

1. 使用运算符栈管理优先级
2. 用节点栈构建树结构
3. 遇到运算符时，弹出高优先级运算符作为父节点
4. 从节点栈弹出两个子节点连接

struct Node { int val; char op; // 操作符或'\0'表示数字 Node *left, *right; Node(int v) : val(v), op('\0'), left(nullptr), right(nullptr) {} Node(char c) : op(c), left(nullptr), right(nullptr) {} };

后序遍历这棵树就能优雅地求得表达式值。我第一次实现时犯了个错误——忘记处理运算符的左右操作数顺序，导致减法和除法结果完全错误。这个bug让我深刻理解了树遍历顺序的重要性。

5. 优先级与括号处理的艺术

在实际编码中，优先级定义是核心难点。我建议采用查表法：

unordered_map<char, int> pri = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}, // 幂运算优先级最高 {'(', 0} // 特殊处理左括号 };

括号处理则需要特别注意：

• 左括号直接入栈，作为优先级最低的边界
• 遇到右括号时不断弹出直到左括号
• 括号内的运算符优先级独立于外部

在信息学奥赛的测试案例中，常常会有多层嵌套括号的极端情况。我的经验是：在本地测试时一定要构造像"((((1+2)*3)-4)/5)"这样的深度嵌套用例。

6. 表达式树的构建细节

构建表达式树时，我推荐使用节点池技术优化内存管理：

Node* createNode(int val) { static Node pool[1000]; // 预分配节点池 static int idx = 0; pool[idx].val = val; pool[idx].op = '\0'; return &pool[idx++]; }

构建过程示例：

1. 扫描"3+5*2"时，先创建数字节点3、5、2
2. 遇到''时，创建操作符节点''，右孩子为5，左孩子为2
3. 遇到'+'时，创建'+'节点，右孩子为'*'子树，左孩子为3

后序遍历计算过程：

int evaluate(Node* root) { if(!root->op) return root->val; int l = evaluate(root->left); int r = evaluate(root->right); switch(root->op) { case '+': return l + r; case '-': return l - r; case '*': return l * r; case '/': return l / r; } return 0; }

7. 实战中的常见陷阱与优化

在多次比赛中，我总结了几个关键注意事项：

1. 数字多位数处理：不能逐个字符处理数字

   while(isdigit(s[i])) { num = num * 10 + (s[i++] - '0'); } i--; // 回退一个字符

2. 负号处理：区分减号和负号

   if (s[i] == '-' && (i == 0 || s[i-1] == '(')) { // 处理负号情况 }

3. 错误处理：检查括号匹配、非法字符
4. 性能优化：预分配栈空间避免动态扩容

在NOIP2017的某道表达式题目中，就因为没处理好多位数字导致丢了30分。这个教训让我养成了在代码中加入详细注释的习惯：

// 注意：这里必须用while处理连续数字 // 测试用例"123+456"中的123和456需要完整读取

8. 从表达式求值到编译原理

表达式求值问题其实是编译原理的微型缩影。当我们构建表达式树时，实际上实现了一个简单的语法分析器（Parser）。这为我们理解更复杂的编程语言处理打下了基础。

在更高级的应用中，表达式树可以：

• 支持变量替换
• 进行表达式化简
• 生成中间代码
• 实现符号微分

// 表达式树求导示例（仅处理+-*） Node* derivative(Node* root, char var) { if(!root->op) return new Node(0); // 常数导数为0 if(root->op == var) return new Node(1); // dx/dx=1 Node *dl = derivative(root->left, var); Node *dr = derivative(root->right, var); switch(root->op) { case '+': case '-': return new Node(root->op, dl, dr); case '*': // 乘法法则 return new Node('+', new Node('*', dl, root->right), new Node('*', root->left, dr)); } return nullptr; }

这个看似简单的题目，打开了我对计算机科学认知的新大门。从最初的栈操作到树结构，再到后来的编译器设计，每一步都让我惊叹算法设计的精妙。在信息学竞赛的道路上，正是这些基础问题的深入理解，构筑了我们解决更复杂问题的能力框架。