算法刷题系列（六十五）：中缀、前缀与后缀表达式——转换和求值

算法刷题系列（六十五）：中缀、前缀与后缀表达式——转换和求值

目录里的早期笔记记录了前缀、中缀和后缀表达式。本篇把三种表示连接起来：中缀把运算符写在操作数之间，依靠优先级和括号表达顺序；前缀、后缀则把运算符放到操作数前面或后面，使运算次序不再依赖括号。

例如：

中缀：(12 + 3) * 4
前缀：* + 12 3 4
后缀：12 3 + 4 *

本文代码支持非负整数、+ - * 和圆括号，不支持一元负号；完整整数解析器见第八篇表达式计算。

一、为什么后缀表达式适合栈？

从左向右扫描后缀表达式：

• 读到操作数就压栈；
• 读到二元运算符，弹出右操作数和左操作数，计算后再压回；
• 扫描结束时栈中应恰有一个结果。

操作数出栈顺序不能颠倒。对减法 9 4 -，先弹出的是右操作数 4，后弹出的是左操作数 9，结果是 9 - 4。

二、中缀转后缀：运算符栈

Shunting-yard 思路维护输出序列和运算符栈：

1. 数字直接输出；
2. 左括号入栈；
3. 右括号到来时，弹出运算符直到左括号；
4. 新运算符入栈前，先弹出栈顶优先级不低于它的运算符；
5. 输入结束后弹出剩余运算符。

+、-、* 在本例中都是左结合，所以相同优先级时也要先弹栈。括号只改变局部弹栈边界。

三、Java 实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class ExpressionNotations {
    public static List<String> toPostfix(String expression) {
        if (expression == null) {
            throw new IllegalArgumentException("expression must not be null");
        }
        List<String> output = new ArrayList<>();
        Deque<Character> operators = new ArrayDeque<>();
        for (int i = 0; i < expression.length();) {
            char current = expression.charAt(i);
            if (Character.isWhitespace(current)) {
                i++;
            } else if (Character.isDigit(current)) {
                int start = i++;
                while (i < expression.length()
                        && Character.isDigit(expression.charAt(i))) {
                    i++;
                }
                output.add(expression.substring(start, i));
            } else if (current == '(') {
                operators.push(current);
                i++;
            } else if (current == ')') {
                while (!operators.isEmpty() && operators.peek() != '(') {
                    output.add(Character.toString(operators.pop()));
                }
                if (operators.isEmpty()) {
                    throw new IllegalArgumentException("unmatched closing parenthesis");
                }
                operators.pop();
                i++;
            } else if (isOperator(current)) {
                while (!operators.isEmpty() && isOperator(operators.peek())
                        && precedence(operators.peek()) >= precedence(current)) {
                    output.add(Character.toString(operators.pop()));
                }
                operators.push(current);
                i++;
            } else {
                throw new IllegalArgumentException("unexpected character: " + current);
            }
        }
        while (!operators.isEmpty()) {
            char operator = operators.pop();
            if (operator == '(') {
                throw new IllegalArgumentException("unmatched opening parenthesis");
            }
            output.add(Character.toString(operator));
        }
        return output;
    }

    public static long evaluatePostfix(List<String> tokens) {
        Deque<Long> values = new ArrayDeque<>();
        for (String token : tokens) {
            if (token.length() == 1 && isOperator(token.charAt(0))) {
                if (values.size() < 2) {
                    throw new IllegalArgumentException("not enough operands");
                }
                long right = values.pop();
                long left = values.pop();
                switch (token.charAt(0)) {
                    case '+': values.push(left + right); break;
                    case '-': values.push(left - right); break;
                    case '*': values.push(left * right); break;
                    default: throw new IllegalArgumentException("unsupported operator");
                }
            } else {
                values.push(Long.parseLong(token));
            }
        }
        if (values.size() != 1) {
            throw new IllegalArgumentException("malformed postfix expression");
        }
        return values.pop();
    }

    private static boolean isOperator(char value) {
        return value == '+' || value == '-' || value == '*';
    }

    private static int precedence(char operator) {
        return operator == '*' ? 2 : 1;
    }

    public static void main(String[] args) {
        List<String> postfix = toPostfix("(12 + 3) * 4");
        if (!postfix.equals(List.of("12", "3", "+", "4", "*"))
                || evaluatePostfix(postfix) != 60) {
            throw new AssertionError("expression conversion failed");
        }
    }
}

四、Python 实现

def to_postfix(expression: str) -> list[str]:
    if expression is None:
        raise ValueError("expression must not be None")
    output: list[str] = []
    operators: list[str] = []
    precedence = {"+": 1, "-": 1, "*": 2}
    index = 0
    while index < len(expression):
        char = expression[index]
        if char.isspace():
            index += 1
        elif char.isdigit():
            start = index
            while index < len(expression) and expression[index].isdigit():
                index += 1
            output.append(expression[start:index])
        elif char == "(":
            operators.append(char)
            index += 1
        elif char == ")":
            while operators and operators[-1] != "(":
                output.append(operators.pop())
            if not operators:
                raise ValueError("unmatched closing parenthesis")
            operators.pop()
            index += 1
        elif char in precedence:
            while (
                operators
                and operators[-1] in precedence
                and precedence[operators[-1]] >= precedence[char]
            ):
                output.append(operators.pop())
            operators.append(char)
            index += 1
        else:
            raise ValueError(f"unexpected character: {char}")

    while operators:
        operator = operators.pop()
        if operator == "(":
            raise ValueError("unmatched opening parenthesis")
        output.append(operator)
    return output

def evaluate_postfix(tokens: list[str]) -> int:
    stack: list[int] = []
    for token in tokens:
        if token in {"+", "-", "*"}:
            if len(stack) < 2:
                raise ValueError("not enough operands")
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            else:
                stack.append(left * right)
        else:
            stack.append(int(token))
    if len(stack) != 1:
        raise ValueError("malformed postfix expression")
    return stack[0]

postfix = to_postfix("(12 + 3) * 4")
assert postfix == ["12", "3", "+", "4", "*"]
assert evaluate_postfix(postfix) == 60
assert evaluate_postfix(to_postfix("20 - 6 - 3")) == 11

五、前缀表达式与表达式树

表达式也可以先构造成二叉表达式树，再按不同顺序输出：

• 前序遍历：根、左、右，得到前缀表达式；
• 中序遍历：左、根、右，通常需要括号恢复优先级；
• 后序遍历：左、右、根，得到后缀表达式。

这解释了为什么前缀和后缀不需要括号：运算符在遍历序列中的位置已经编码了树的结构。若要从中缀构造树，可以先转后缀，再用栈把操作数和运算符组装成节点。

六、边界与错误处理

• 空表达式、相邻运算符、缺少操作数和括号不匹配都应拒绝。
• 本例要求二元运算符两侧都有非负整数；负数需额外设计一元运算符规则。
• long 乘法可能溢出；若输入规模不受限，应使用大整数或检查边界。
• 中缀到后缀的时间为 O(n)，运算符栈和输出空间为 O(n)。

小结

中缀表达式依赖优先级和括号，后缀表达式依靠操作数栈求值，前缀/后缀顺序则对应表达式树的不同遍历。统一 token、优先级和左右操作数顺序后，转换与计算都能在一次线性扫描内完成。