数据结构实战：用二叉树和双栈搞定表达式求值，面试官都爱问的经典题

表达式求值问题在技术面试中频繁出现，尤其在后端开发和算法岗位的考察中占据重要地位。这道题目不仅考察候选人对基础数据结构的掌握程度，更能体现其算法设计能力和工程思维。本文将深入探讨两种主流解法——双栈法和二叉树法，从原理分析到代码实现，再到面试中的表达技巧，为你全面解析这道经典题目。

1. 表达式求值问题解析

表达式求值问题的核心在于如何正确解析和计算包含多种运算符的数学表达式。以表达式"2*(3+4)-5"为例，我们需要考虑运算符优先级（乘除优先于加减）、括号的嵌套以及运算顺序等问题。

在计算机科学中，表达式通常有三种表示形式：

• 中缀表达式：运算符位于操作数之间，如"A+B"
• 前缀表达式（波兰式）：运算符位于操作数之前，如"+AB"
• 后缀表达式（逆波兰式）：运算符位于操作数之后，如"AB+"

中缀表达式最符合人类阅读习惯，但计算机处理起来较为复杂，需要借助特定数据结构进行转换和计算。

提示：面试中常要求处理的中缀表达式特点包括：支持加减乘除四则运算、包含括号、操作数为正整数或小数。

2. 双栈解法：直观高效的标准解法

双栈法是表达式求值最经典的解法之一，其核心思想是使用两个栈分别存储操作数和运算符，通过比较运算符优先级来决定计算顺序。

2.1 算法步骤详解

1. 初始化两个空栈：操作数栈和运算符栈
2. 从左到右扫描表达式：
   • 遇到数字：压入操作数栈
   • 遇到左括号：压入运算符栈
   • 遇到右括号：弹出运算符栈顶元素并计算，直到遇到左括号
   • 遇到运算符：
     • 当栈顶运算符优先级≥当前运算符时，弹出栈顶运算符并计算
     • 将当前运算符压入栈
3. 表达式扫描完毕后，依次弹出运算符栈中的元素并计算
4. 最终操作数栈中剩下的唯一元素即为结果

def evaluate_expression(expression):
    operand_stack = []
    operator_stack = []
    precedence = {'+':1, '-':1, '*':2, '/':2}
    
    i = 0
    while i < len(expression):
        if expression[i].isdigit():
            num = 0
            while i < len(expression) and expression[i].isdigit():
                num = num * 10 + int(expression[i])
                i += 1
            operand_stack.append(num)
            continue
        elif expression[i] == '(':
            operator_stack.append(expression[i])
        elif expression[i] == ')':
            while operator_stack[-1] != '(':
                compute(operand_stack, operator_stack)
            operator_stack.pop()
        else:
            while (operator_stack and operator_stack[-1] != '(' and
                   precedence[operator_stack[-1]] >= precedence[expression[i]]):
                compute(operand_stack, operator_stack)
            operator_stack.append(expression[i])
        i += 1
    
    while operator_stack:
        compute(operand_stack, operator_stack)
    
    return operand_stack[0]

def compute(operand_stack, operator_stack):
    b = operand_stack.pop()
    a = operand_stack.pop()
    op = operator_stack.pop()
    if op == '+': operand_stack.append(a + b)
    elif op == '-': operand_stack.append(a - b)
    elif op == '*': operand_stack.append(a * b)
    elif op == '/': operand_stack.append(a // b)

2.2 时间复杂度与空间复杂度分析

双栈解法的时间复杂度为O(n)，其中n是表达式长度，因为每个字符只需处理一次。空间复杂度也是O(n)，最坏情况下所有操作数都需要入栈。

在面试中，面试官可能会要求你分析不同情况下的复杂度：

情况	时间复杂度	空间复杂度
最优情况	O(n)	O(1)
最坏情况	O(n)	O(n)
平均情况	O(n)	O(n/2)

3. 二叉树解法：体现递归思维的优雅方案

二叉树解法将表达式转换为表达式树，通过树遍历来完成求值。这种方法虽然实现稍复杂，但能更好地展示递归思维和对树结构的理解。

3.1 表达式树的构建原理

表达式树是一种特殊的二叉树，其中：

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

构建表达式树的关键在于找到"最后计算"的运算符作为根节点，然后递归构建左右子树。

构建步骤 ：

1. 初始化运算符栈和操作数栈
2. 扫描表达式：
   • 遇到数字：创建叶子节点并入栈
   • 遇到运算符：与栈顶运算符比较优先级
     • 如果栈顶优先级高：弹出栈顶运算符构建子树
     • 否则：当前运算符入栈
3. 处理完所有字符后，弹出剩余运算符构建完整树

3.2 递归求值的实现

表达式树构建完成后，通过后序遍历可以方便地计算表达式值：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def evaluate_expression_tree(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return int(root.val)
    
    left_val = evaluate_expression_tree(root.left)
    right_val = evaluate_expression_tree(root.right)
    
    if root.val == '+': return left_val + right_val
    if root.val == '-': return left_val - right_val
    if root.val == '*': return left_val * right_val
    if root.val == '/': return left_val // right_val

3.3 二叉树解法的优势与局限

优势 ：

• 直观展示表达式结构
• 便于扩展支持更多运算符
• 可以轻松实现表达式的前缀、中缀、后缀表示转换
• 在编译器设计中应用广泛

局限 ：

• 构建过程较复杂
• 需要额外空间存储树结构
• 对于简单表达式略显重量级

4. 面试中的实战技巧与扩展思考

4.1 如何清晰阐述解题思路

在面试中，表达能力和解题思路同样重要。建议采用以下结构：

1. 问题分析 ：明确题目要求和边界条件
2. 解法选择 ：对比不同解法的优劣
3. 详细步骤 ：分步解释算法流程
4. 复杂度分析 ：时间和空间复杂度
5. 测试用例 ：举例验证算法正确性

4.2 常见变体问题

面试官可能会基于基础问题提出各种变体，例如：

• 支持浮点数运算
• 增加模运算(%)、指数运算(^)等新运算符
• 处理表达式中的空格和非法输入
• 优化算法减少栈操作次数

4.3 工程实践中的应用

表达式求值算法在实际工程中有广泛应用：

1. 计算器应用 ：处理用户输入的数学表达式
2. 数据库查询优化 ：解析SQL中的条件表达式
3. 编译器设计 ：语法分析和中间代码生成
4. 规则引擎 ：评估业务规则和条件

5. 代码优化与边界情况处理

无论采用哪种解法，健壮的代码实现都需要考虑各种边界情况：

• 空表达式或无效输入处理
• 除零错误的预防
• 括号不匹配的检测
• 超大数字的溢出处理
• 连续运算符的处理

def safe_compute(a, b, op):
    if op == '/' and b == 0:
        raise ValueError("Division by zero")
    # 其他运算...

在实际项目中，我们还需要考虑添加日志记录、性能监控等工程化特性，使代码更具生产环境适用性。