跳转至

表达式求值

刷题的时候遇到了逆波兰表达式的求值，如果掌握了栈的用法的话这题本身其实并不难。

然而表达式求值本身却是一个更加通用、比更加困难并且更加有趣的算法。它也让我充分认识到树这个结构的精妙，原来前序后序中序遍历不是瞎搞的，确实有用！

因此特此写下此文。

计算树

更一般的也可以叫做：抽象语法树（AST）

一个典型四则运算的数学表达式形如：(2 + 1) * 3 - 8 / 2

这里我们暂时先不考虑单目运算符，例如取负-2、取反~2等等

我们把算符放在父节点、把数字放在子节点，它就可以表示为一个计算树：

graph TD
    A[减法 -] --> B[乘法 *]
    A --> C[除法 /]
    B --> D[加法 +]
    B --> E[3]
    D --> F[2]
    D --> G[1]
    C --> H[8]
    C --> I[2]

实际上，正常的表达式就是这棵树的中序遍历。

而它的后序遍历就是所谓的逆波兰表达式：2 1 + 3 * 8 2 / -

前序遍历自然就是波兰表达式：- * + 2 1 3 / 8 2

我们来验证一下：

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

    def dfs(self, order="in"):#(1)!
        if order == "pre":
            yield self.val
        if self.left:
            yield from self.left.dfs(order)
        if order == "in":
            yield self.val
        if self.right:
            yield from self.right.dfs(order)
        if order == "post":
            yield self.val


t = Node("-")
t.left = Node(
    "*",
    Node("+", Node("2"), Node("1")),
    Node("3"),
)
t.right = Node("/", Node("8"), Node("2"))
print(*t.dfs("pre"))
print(*t.dfs("in"))
print(*t.dfs("post"))
  1. 这是经典的dfs三种顺序写法，利用了递归生成器比较简洁

我快速写了一个demo，它的输出就是：

- * + 2 1 3 / 8 2
2 + 1 * 3 - 8 / 2
2 1 + 3 * 8 2 / -

不难发现，中序遍历必须依赖括号来表达运算的优先级。也就是(2+1)*3-8/2其中的括号不可以忽略。然而后面我们会看到，波兰表达式和逆波兰表达式都不依赖括号来表达运算优先级。这是他们在计算机中广泛使用的重要原因。

逆波兰表达式求值

如果表达式已经被写成了逆波兰表达式，那么求值是一件比较简单的事情。这其实是逆波兰表达式为什么如此另外一个重要的原因。

但是如何得到逆波兰表达式并不那么容易，这一点我们下一节再说。先来看看逆波兰表达式如何求值：

代码

只需要用到一个栈即可。我们遍历表达式的每个元素，如果是数字就压栈，如果遇到运算符就从栈顶拿出两个数字进行运算。运算结果继续压栈。

重复上述过程就可以在O(N)时间内解决表达式求值的问题：

from math import trunc

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        num = []
        op = "+-*/"
        while tokens:
            token = tokens.pop(0)
            if token not in op:
                # 压栈
                num.append(int(token))
            else:
                # 出栈，注意先出栈的是b
                b = num.pop()
                a = num.pop()
                match token:
                    case "+":
                        res = a+b
                    case '-':
                        res = a-b
                    case '*':
                        res = a*b
                    case '/':
                        res = trunc(a/b)
                num.append(res)
        return num[0]

中序表达式转后序表达式

也就是普通表达式转换为逆波兰表达式

这是一个经典的算法：调度场算法。并且他的发明人也是大名鼎鼎：Dijkstra。

下面这张图基本完全解释了这个算法的精髓（以及它为什么叫调度场）：

代码

调度场算法 
def to_rpn(expression: str) -> list[str]:
    """使用调度场算法将中序表达式转换为逆波兰表达式。"""
    operators = []
    output = []
    # 需要预先定义运算优先级
    # 我们这里只处理双目运算符
    priority = {"+": 1, "-": 1, "*": 2, "/": 2}
    i = 0

    # 从前到后扫描整个表达式
    while i < len(expression):
        char = expression[i]
        if char.isspace():
            i += 1
            continue

        # 遇到数字直接进入输出队列
        if char.isdigit():
            j = i
            while j < len(expression) and expression[j].isdigit():
                j += 1
            output.append(expression[i:j])
            i = j
            continue

        # 遇到左括号需要压栈
        if char == "(":
            operators.append(char)
        # 遇到右括号开始出栈
        elif char == ")":
            while operators and operators[-1] != "(":
                output.append(operators.pop())
            if not operators:
                raise ValueError("括号不匹配")
            operators.pop() # 应该还剩一个左括号，丢掉
        # 遇到运算符，需要进行判断
        elif char in priority:
            # 如果当前运算优先级不高，就把栈内的运算都弹出来
            while (
                operators
                and operators[-1] != "("
                and priority[operators[-1]] >= priority[char]
            ):
                output.append(operators.pop())
            # 如果当前运算优先级高，就压栈
            operators.append(char)
        else:
            raise ValueError(f"无法识别的字符: {char}")
        i += 1

    # 扫描完成后剩下的所有运算符都进入输出队列
    while operators:
        # 如果还有左括号，就是表达式错了
        if operators[-1] == "(":
            raise ValueError("括号不匹配")
        output.append(operators.pop())
    return output


print(to_rpn("(2 + 1) * 3 - 8 / 2"))
# ['2', '1', '+', '3', '*', '8', '2', '/', '-']

下面是代码的可视化运行，可以清晰地看到我们压栈、出栈的过程：

计算树的构造：双栈

最开始我们说过，表达式可以转化成一个二叉树。这一节我们就来亲手构造出这个树。

构造的过程需要使用双栈：

这是可视化输出树的一个好写法

树的定义
class Node:
    """计算树节点。"""
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def __repr__(self):
        """输出中序遍历表达式"""
        if self.left is None and self.right is None:
            return str(self.val)
        return f"({self.left} {self.val} {self.right})"
        # 这里看起来非常简洁，实际上隐含调用了self.left.__repr__()
    def RPN(self):
        """输出后缀表达式"""
        if self.left is None and self.right is None:
            return str(self.val)
        return f"{self.left.RPN()} {self.right.RPN()} {self.val}"
    def PN(self):
        """输出前缀表达式"""
        if self.left is None and self.right is None:
            return str(self.val)
        return f"{self.val} {self.left.PN()} {self.right.PN()}"
AST的构造算法：双栈
def build_ast(expression: str) -> Node:
    """使用双栈将中序表达式构造为抽象语法树。"""
    operators = []
    operands = []
    priority = {"+": 1, "-": 1, "*": 2, "/": 2}

    def reduce_once():
        if not operators or operators[-1] == "(":
            raise ValueError("缺少运算符")
        operator = operators.pop()
        if len(operands) < 2:
            raise ValueError("缺少操作数")
        right = operands.pop()
        left = operands.pop()
        operands.append(Node(operator, left, right))

    i = 0
    while i < len(expression):
        char = expression[i]
        if char.isspace():
            i += 1
            continue
        if char.isdigit():
            j = i
            while j < len(expression) and expression[j].isdigit():
                j += 1
            operands.append(Node(expression[i:j]))
            i = j
            continue
        if char == "(":
            operators.append(char)
        elif char == ")":
            while operators and operators[-1] != "(":
                reduce_once()
            if not operators:
                raise ValueError("括号不匹配")
            operators.pop()
        elif char in priority:
            while (
                operators
                and operators[-1] != "("
                and priority[operators[-1]] >= priority[char]
            ):
                reduce_once()
            operators.append(char)
        else:
            raise ValueError(f"无法识别的字符: {char}")
        i += 1

    while operators:
        if operators[-1] == "(":
            raise ValueError("括号不匹配")
        reduce_once()

    if len(operands) != 1:
        raise ValueError("表达式不合法")
    return operands[0]


tree = build_ast("(2 + 1) * 3 - 8 / 2")
print(tree)
print(tree.RPN())
print(tree.PN())

计算树的构造：三栈

AI写的代码太规范了，而且不是最好理解的。我自己也写了一个三栈的版本：

AST构造算法：三栈
def three_stack_build_ast(expression):
    op = []
    num = []
    stack = []
    priority = {"+": 1, "-": 1, "*": 2, "/": 2}

    # 定义一个函数来处理运算符栈和操作数栈的归约操作
    def reduce_ops():
        while op:
            operator = op.pop()
            right = num.pop()
            left = num.pop()
            num.append(Node(operator, left, right))

    i = 0
    while i < len(expression):
        char = expression[i]
        if char.isspace():
            i += 1
        elif char.isdigit():
            j = i
            while j < len(expression) and expression[j].isdigit():
                j += 1
            num.append(Node(expression[i:j]))
            i = j
        elif char == "(":
            # 保存当前层的运算符和操作数，括号内使用新的队列。
            stack.append((op, num))
            op = []
            num = []
            i += 1
        elif char == ")":
            # 计算括号内的表达式，并将结果压入上层的操作数栈
            reduce_ops()
            prev_op, prev_num = stack.pop()
            prev_num.append(num[0])
            op = prev_op
            num = prev_num
            i += 1
        elif char in priority:
            while op and priority[op[-1]] >= priority[char]:
                reduce_ops()
            op.append(char)
            i += 1
    reduce_ops()
    return num[0]

tree = three_stack_build_ast("(2 + 1) * 3 - 8 / 2")
print(tree)
print(tree.RPN())
print(tree.PN())

变种Leetcode题

再往下刷还有更难的😭

我就不刷了，各位大手子刷吧！

最后更新: 2026-09-23 00:42:28
创建日期: 2026-09-23 00:42:28

广告

人要恰饭的嘛🤑🤑

评论