1. 表达式求值问题概述
表达式求值是计算机科学中一个经典的基础算法问题，它要求我们编写程序来计算包含加减乘除和括号的数学表达式。这个问题看似简单，但实际处理起来需要考虑运算符优先级、括号嵌套、运算顺序等诸多细节。
我第一次接触这个问题是在学习数据结构与算法时，当时参考了acwing平台yxc老师的讲解。yxc老师采用的双栈解法给我留下了深刻印象——它思路清晰、实现简洁，完美展现了算法设计的精妙之处。这种解法通过维护两个栈（操作数栈和运算符栈）来模拟运算过程，能够高效处理各种复杂表达式。
2. 双栈算法原理详解
2.1 算法核心思想
双栈算法的核心在于利用栈的先进后出特性来处理运算符优先级和括号嵌套。具体来说：
- 操作数栈：存储所有待计算的数字
- 运算符栈：存储运算符和括号，用于控制计算顺序
算法的执行过程可以概括为：逐个读取表达式字符，根据字符类型分别处理：
- 数字：完整读取后压入操作数栈
- 运算符：与栈顶运算符比较优先级，决定是否先计算栈顶运算
- 括号：左括号直接入栈，右括号触发括号内计算
2.2 运算符优先级处理
运算符优先级是算法中最关键的部分。我们定义以下优先级规则：
- 加减法：优先级1
- 乘除法：优先级2
- 左括号：特殊处理，优先级最低
当遇到新运算符时，我们需要不断弹出栈顶运算符进行计算，直到栈顶运算符优先级低于当前运算符。这样可以确保高优先级运算先执行。
注意：右括号不是运算符，它只是触发计算的信号。遇到右括号时，我们需要一直计算到遇到左括号为止。
3. 完整算法实现步骤
3.1 初始化与预处理
首先我们需要做一些准备工作：
- 定义运算符优先级映射表
- 初始化两个空栈
- 为表达式添加边界标记（通常可以在首尾添加括号）
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; stack<int> num; stack<char> op; string s = "(" + input + ")"; // 输入表达式3.2 主循环处理流程
算法主循环逐个处理表达式字符：
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 = x * 10 + (s[j++] - '0'); num.push(x); i = j - 1; } else if (c == '(') { // 左括号直接入栈 op.push(c); } else if (c == ')') { // 右括号触发计算 while (op.top() != '(') eval(); op.pop(); // 弹出左括号 } else { // 处理运算符 while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval(); op.push(c); } }3.3 计算函数实现
eval()函数负责执行一次运算：
void 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); }4. 算法细节与优化技巧
4.1 处理负数和小数
基础版本只支持正整数，实际应用中我们可能需要：
- 负数处理：识别一元负号，可以修改数字读取逻辑
- 小数支持：修改数字读取部分，加入小数点处理
// 改进的数字读取逻辑 if (c == '-' && (i == 0 || s[i-1] == '(')) { // 处理负号 is_negative = true; continue; } if (c == '.') { // 处理小数部分 double fraction = 0.1; while (isdigit(s[++i])) { x += (s[i] - '0') * fraction; fraction *= 0.1; } i--; }4.2 错误处理机制
健壮的表达式求值应该包含错误检测：
- 括号不匹配检查
- 非法字符检测
- 除零错误处理
- 空表达式处理
可以在算法中加入相应的检查点：
// 在eval函数中加入除零检查 if (c == '/' && b == 0) { throw runtime_error("Division by zero"); }5. 性能分析与优化
5.1 时间复杂度分析
双栈算法的时间复杂度是O(n)，其中n是表达式长度。每个字符最多入栈出栈一次，eval()函数每次执行常数时间操作。
5.2 空间复杂度分析
空间复杂度也是O(n)，最坏情况下所有字符都是运算符或括号，需要全部入栈。
5.3 实际优化建议
- 使用数组模拟栈可以获得更好的性能
- 预处理阶段可以去除所有空格
- 对于常量表达式，可以预先计算部分结果
6. 常见问题与调试技巧
6.1 典型错误案例
- 运算符优先级处理错误：忘记比较栈顶运算符优先级
- 括号匹配问题：没有正确处理嵌套括号
- 数字读取错误：多位数字读取不完整
- 栈操作顺序错误：操作数弹出顺序影响减法除法结果
6.2 调试方法
- 打印中间状态：在每次eval()后打印两个栈的内容
- 单步跟踪：使用调试器逐步执行观察变量变化
- 测试用例设计：构造各种边界情况测试
// 调试打印函数 void print_stacks() { cout << "Numbers: "; stack<int> tmp = num; while (tmp.size()) { cout << tmp.top() << " "; tmp.pop(); } cout << "\nOperators: "; stack<char> tmp_op = op; while (tmp_op.size()) { cout << tmp_op.top() << " "; tmp_op.pop(); } cout << endl; }7. 扩展应用与变种问题
7.1 支持更多运算符
可以扩展算法支持：
- 幂运算（^）
- 模运算（%）
- 位运算（&, |, ^）
只需要在优先级映射表中添加相应的条目即可。
7.2 表达式转换
基于同样的算法思想，我们可以实现：
- 中缀表达式转后缀表达式（逆波兰表示法）
- 中缀表达式转前缀表达式
- 表达式树构建
7.3 实际工程应用
- 计算器程序开发
- 公式解析引擎
- 数据库查询条件解析
- 编程语言解释器
我在实际项目中曾用类似的方法实现过一个财务公式计算引擎，处理包含数十个变量的复杂计算公式。关键是要确保算法的健壮性和错误处理能力，因为用户输入的表达式可能千奇百怪。
8. 与其他解法的比较
8.1 递归下降法
递归下降是另一种常见的表达式解析方法：
- 优点：结构清晰，易于扩展
- 缺点：递归调用有栈深度限制，性能略低
8.2 调度场算法
调度场算法专门用于中缀转后缀：
- 优点：生成的表达式易于计算
- 缺点：需要额外步骤转换
8.3 双栈法优势
相比之下，双栈法：
- 实现简洁，只需约50行代码
- 一次遍历完成计算
- 易于理解和调试
- 性能优异
9. 实现中的注意事项
- 数字读取要完整：多位数字需要连续读取
- 运算符优先级比较要准确：特别是括号的处理
- 操作数顺序要正确：减法和除法对顺序敏感
- 边界条件要测试：空表达式、单个数字等情况
我在最初实现时曾犯过一个典型错误：在eval()函数中先弹出b再弹出a，导致减法和除法结果完全相反。这个bug花了我不少时间才发现，现在回想起来，在弹出操作数时添加注释说明是个好习惯：
int b = num.top(); num.pop(); // 右操作数 int a = num.top(); num.pop(); // 左操作数10. 学习资源与进阶方向
对于想深入学习的开发者，我推荐：
- 《算法导论》中的表达式树相关内容
- 编译原理中的语法分析技术
- leetcode相关题目练习（如224.基本计算器）
- 尝试实现一个完整的科学计算器
yxc老师在acwing上的讲解视频是很好的入门材料，特别是他对双栈算法每一步的细致分析，让我真正理解了算法的精髓。建议初学者可以多看几遍，跟着视频一步步实现代码。
