信息学奥赛 1356：表达式求值 (calc) 从原理到 AC，5 步构建表达式树

信息学奥赛 1356表达式求值 (calc) 从原理到 AC5 步构建表达式树在信息学竞赛中表达式求值是一个经典问题。本文将深入解析《信息学奥赛一本通》1356题计算(calc)的第三种解法——表达式树。不同于直接求值或转换为后缀表达式的方法表达式树通过树形结构直观展现运算优先级为处理复杂表达式提供了清晰的解决方案。1. 表达式树基础概念表达式树是一种特殊的二叉树结构用于表示数学表达式。它具有以下特点叶子节点存储操作数数值内部节点存储运算符如、-、*、/子树关系每个运算符的左右子树代表其运算对象struct Node { char op; // 运算符内部节点 int val; // 数值叶子节点 int left, right;// 左右子节点索引 };表达式树的求值过程遵循后序遍历原则先计算左子树的值再计算右子树的值最后用当前节点的运算符对两个结果进行运算。这种结构与运算优先级天然契合特别适合处理带括号的复杂表达式。2. 双栈构建表达式树构建表达式树的核心算法使用双栈法一个操作数栈存储节点索引一个运算符栈处理运算优先级。以下是详细步骤2.1 初始化与预处理stackint numStack; // 操作数栈存储节点索引 stackchar opStack; // 运算符栈 string s; // 输入表达式 s ); // 添加哨兵运算符确保最终清空栈2.2 运算符优先级定义int priority(char op) { switch(op) { case (: return 0; // 最低优先级保证括号内运算符入栈 case : case -: return 1; case *: case /: return 2; default: return -1; // 非法运算符 } }2.3 核心算法流程遇到数字创建叶子节点并入操作数栈if(isdigit(s[i])) { int val 0; while(isdigit(s[i])) val val*10 (s[i]-0); nodes[idx] {\0, val, -1, -1}; numStack.push(idx); }遇到运算符比较优先级并处理栈顶高优先级运算符while(!opStack.empty() priority(opStack.top()) priority(s[i])) { char op opStack.top(); opStack.pop(); int right numStack.top(); numStack.pop(); int left numStack.top(); numStack.pop(); nodes[idx] {op, 0, left, right}; numStack.push(idx); } opStack.push(s[i]);遇到括号左括号直接入栈右括号处理到左括号为止if(s[i] () opStack.push((); else if(s[i] )) { while(opStack.top() ! () { // 同运算符处理逻辑 } opStack.pop(); // 弹出左括号 }3. 完整C实现与注释#include bits/stdc.h using namespace std; const int MAXN 1005; struct Node { char op; int val, left, right; } nodes[MAXN]; int idx 0; int priority(char op) { switch(op) { case (: return 0; case : case -: return 1; case *: case /: return 2; default: return -1; } } int calc(int a, int b, char op) { switch(op) { case : return a b; case -: return a - b; case *: return a * b; case /: return a / b; default: return 0; } } int main() { stackint numStack; stackchar opStack; string s; cin s; s ); // 哨兵 for(int i 0; i s.size(); ) { if(isdigit(s[i])) { int val 0; while(i s.size() isdigit(s[i])) val val*10 (s[i]-0); nodes[idx] {\0, val, -1, -1}; numStack.push(idx); } else { if(s[i] () { opStack.push((); i; } else if(s[i] )) { while(opStack.top() ! () { char op opStack.top(); opStack.pop(); int r numStack.top(); numStack.pop(); int l numStack.top(); numStack.pop(); nodes[idx] {op, 0, l, r}; numStack.push(idx); } opStack.pop(); i; } else { // 运算符 while(!opStack.empty() priority(opStack.top()) priority(s[i])) { char op opStack.top(); opStack.pop(); int r numStack.top(); numStack.pop(); int l numStack.top(); numStack.pop(); nodes[idx] {op, 0, l, r}; numStack.push(idx); } opStack.push(s[i]); i; } } } cout nodes[numStack.top()].val; return 0; }4. 表达式树的优势与应用相比其他解法表达式树具有独特优势方法时间复杂度空间复杂度可扩展性可视化程度直接求值O(n)O(n)中等低后缀表达式O(n)O(n)高中表达式树O(n)O(n)最高高典型应用场景需要多次求值的表达式构建一次多次计算表达式化简与优化数学公式的可视化展示编译器前端处理5. 常见问题与调试技巧5.1 易错点分析括号匹配忘记处理右括号后的栈操作运算符优先级比较时漏掉等号导致错误数字解析多位数字处理不完整边界条件空表达式或单数字表达式5.2 调试建议打印中间状态输出运算符栈和操作数栈的变化可视化表达式树通过DFS打印树结构void printTree(int root, int depth 0) { if(root -1) return; printTree(nodes[root].right, depth1); cout string(depth*4, ); if(nodes[root].op) cout nodes[root].op endl; else cout nodes[root].val endl; printTree(nodes[root].left, depth1); }表达式树不仅是竞赛中的高效工具更是理解编译器工作原理的重要桥梁。掌握这一数据结构对提升算法思维和工程能力都大有裨益。