算法刷题系列（八）：表达式计算——从符号串到运算结果

算法刷题系列（八）：表达式计算——从符号串到运算结果

表达式计算看起来像“把字符串算出结果”，实际需要先解决两个问题：

1. 字符串遵循什么语法？哪些输入是合法表达式？
2. 运算符优先级、括号和一元正负号如何决定计算顺序？

本篇是基础工具阶段的最后一篇：前面的栈提供了处理后进先出结构的工具，接下来的线性结构模块会再次用到它。这里实现一个有限但完整的小型整数表达式解析器，支持加法、减法、乘法、括号、空白字符和一元正负号。例子与代码均为原创，分别使用 Java 和 Python。为避免不同语言的整除规则差异，本文暂不支持除法。

一、先定义语法

如果不先定义合法输入，代码就很难判断某个符号应该如何处理。本篇使用下面这套语法：

expression := term (("+" | "-") term)*
term       := unary ("*" unary)*
unary      := ("+" | "-") unary | primary
primary    := integer | "(" expression ")"
integer    := digit+

它允许以下表达式：

18 + 4 * 3
-(12 + 3) * 2 + 5
7 * --2

它不允许除法、变量、小数、函数调用或隐式乘法（例如 2(3 + 4)）。

语法中 expression 处理加减，term 处理乘法。因为 expression 的每一项都是完整的 term，乘法自然会先于加减完成。括号通过递归调用 expression 处理。

二、运算优先级与结合性

乘法优先于加减，因此：

18 + 4 * 3
= 18 + 12
= 30

加减和乘法在本篇中都是左结合：

20 - 6 - 3
= (20 - 6) - 3
= 11

一元正负号优先作用于它后面的表达式单元；例如：

-(2 + 5) = -7

若把所有符号都当成从左向右执行的字符，运算优先级和括号就会被破坏。

三、递归下降解析的结构

我们为每一层语法规则写一个解析函数：

• parseExpression：读取加减表达式；
• parseTerm：读取乘法项；
• parseUnary：处理连续的一元正负号；
• parsePrimary：读取整数或括号表达式。

每个函数从当前字符开始读取自己负责的部分，并返回数值，同时推进字符位置。函数之间的调用结构与语法规则一一对应。

解析示意

解析 18 + 4 * 3：

1. parseExpression 先调用 parseTerm，得到 18。
2. 看到 + 后，再读取下一个 parseTerm。
3. 这个 parseTerm 读取 4 * 3，在本层完成乘法得到 12。
4. 最外层完成 18 + 12，返回 30。

由于运算符集合只有固定几类，每个字符只会被解析和消费一次，所以时间复杂度为 O(n)，其中 n 是表达式长度。递归栈空间为 O(d)，d 是括号和一元符号嵌套的最大深度；极深的输入可能超过语言的递归栈限制。

四、Java 实现

import java.math.BigInteger;

public class ExpressionEvaluator {
    private final String input;
    private int index;

    private ExpressionEvaluator(String input) {
        this.input = input;
    }

    public static BigInteger evaluate(String input) {
        if (input == null) {
            throw new IllegalArgumentException("Expression must not be null");
        }

        ExpressionEvaluator parser = new ExpressionEvaluator(input);
        parser.skipWhitespace();
        if (parser.index == input.length()) {
            throw new IllegalArgumentException("Expression must not be empty");
        }

        BigInteger result = parser.parseExpression();
        parser.skipWhitespace();
        if (parser.index != input.length()) {
            throw parser.error("Unexpected character");
        }
        return result;
    }

    private BigInteger parseExpression() {
        BigInteger value = parseTerm();

        while (true) {
            skipWhitespace();
            if (consume('+')) {
                value = value.add(parseTerm());
            } else if (consume('-')) {
                value = value.subtract(parseTerm());
            } else {
                return value;
            }
        }
    }

    private BigInteger parseTerm() {
        BigInteger value = parseUnary();

        while (true) {
            skipWhitespace();
            if (consume('*')) {
                value = value.multiply(parseUnary());
            } else {
                return value;
            }
        }
    }

    private BigInteger parseUnary() {
        skipWhitespace();
        if (consume('+')) {
            return parseUnary();
        }
        if (consume('-')) {
            return parseUnary().negate();
        }
        return parsePrimary();
    }

    private BigInteger parsePrimary() {
        skipWhitespace();

        if (consume('(')) {
            BigInteger value = parseExpression();
            skipWhitespace();
            if (!consume(')')) {
                throw error("Missing closing parenthesis");
            }
            return value;
        }

        if (index >= input.length() || !isAsciiDigit(input.charAt(index))) {
            throw error("Expected an integer or parenthesized expression");
        }

        BigInteger value = BigInteger.ZERO;
        while (index < input.length()
                && isAsciiDigit(input.charAt(index))) {
            int digit = input.charAt(index) - '0';
            value = value.multiply(BigInteger.TEN)
                    .add(BigInteger.valueOf(digit));
            index++;
        }
        return value;
    }

    private boolean isAsciiDigit(char value) {
        return value >= '0' && value <= '9';
    }

    private void skipWhitespace() {
        while (index < input.length()
                && Character.isWhitespace(input.charAt(index))) {
            index++;
        }
    }

    private boolean consume(char expected) {
        if (index < input.length() && input.charAt(index) == expected) {
            index++;
            return true;
        }
        return false;
    }

    private IllegalArgumentException error(String message) {
        return new IllegalArgumentException(
            message + " at position " + index
        );
    }

    public static void main(String[] args) {
        System.out.println(evaluate("-(12 + 3) * 2 + 5")); // -25
    }
}

使用 BigInteger 是为了让示例聚焦于解析过程，不受 long 溢出影响。如果题目保证所有中间结果都在 32 位或 64 位范围内，可以改用 int 或 long，但要按题目约束检查乘法和加法的溢出。

解析结束后必须确认已经消费完整个输入。否则 2 + 3 abc 可能只返回前半段结果，把尾部非法字符忽略掉。

五、Python 实现

class ExpressionParser:
    def __init__(self, text: str) -> None:
        self.text = text
        self.index = 0

    def parse(self) -> int:
        self.skip_whitespace()
        if self.index == len(self.text):
            raise ValueError("expression must not be empty")

        value = self.parse_expression()
        self.skip_whitespace()
        if self.index != len(self.text):
            raise ValueError(f"unexpected character at position {self.index}")
        return value

    def parse_expression(self) -> int:
        value = self.parse_term()

        while True:
            self.skip_whitespace()
            if self.consume("+"):
                value += self.parse_term()
            elif self.consume("-"):
                value -= self.parse_term()
            else:
                return value

    def parse_term(self) -> int:
        value = self.parse_unary()

        while True:
            self.skip_whitespace()
            if self.consume("*"):
                value *= self.parse_unary()
            else:
                return value

    def parse_unary(self) -> int:
        self.skip_whitespace()
        if self.consume("+"):
            return self.parse_unary()
        if self.consume("-"):
            return -self.parse_unary()
        return self.parse_primary()

    def parse_primary(self) -> int:
        self.skip_whitespace()

        if self.consume("("):
            value = self.parse_expression()
            self.skip_whitespace()
            if not self.consume(")"):
                raise ValueError(
                    f"missing closing parenthesis at position {self.index}"
                )
            return value

        if (
            self.index >= len(self.text)
            or not ("0" <= self.text[self.index] <= "9")
        ):
            raise ValueError(
                f"expected an integer or parenthesized expression "
                f"at position {self.index}"
            )

        value = 0
        while (
            self.index < len(self.text)
            and "0" <= self.text[self.index] <= "9"
        ):
            value = value * 10 + int(self.text[self.index])
            self.index += 1
        return value

    def skip_whitespace(self) -> None:
        while self.index < len(self.text) and self.text[self.index].isspace():
            self.index += 1

    def consume(self, expected: str) -> bool:
        if self.index < len(self.text) and self.text[self.index] == expected:
            self.index += 1
            return True
        return False

def evaluate(text: str) -> int:
    return ExpressionParser(text).parse()

assert evaluate("18 + 4 * 3") == 30
assert evaluate("20 - 6 - 3") == 11
assert evaluate("-(12 + 3) * 2 + 5") == -25

Python 整数与 Java BigInteger 都支持任意精度整数，因此两份实现对超出固定宽度的数值也保持一致。

六、错误输入如何处理？

解析器不应在表达式非法时返回一个看似正常的部分结果。上面的实现会拒绝以下输入：

输入	错误原因
空字符串	没有表达式
2 +	加号后缺少操作数
(2 + 3	缺少右括号
2 + 3)	多余的右括号
2 ** 3	不支持连续乘号
2 + 3 abc	解析完成后仍有未消费字符
()	括号内缺少表达式

竞赛题通常保证表达式合法，但仍要严格按题目定义支持的字符和运算符编写。若输入来自外部用户，错误信息还可以包含字符位置，帮助定位问题。

七、递归解析与栈的关系

递归下降使用程序调用栈保存尚未完成的括号表达式。例如处理 2 * (3 + 4) 时，外层乘法暂时等待括号内的表达式返回。

也可以用显式栈实现表达式解析，把“尚未完成的运算符或括号”存进自己的栈结构。递归下降与显式栈解决的是相同的语法嵌套问题：

• 递归写法更贴近语法规则，适合运算符层级清楚的小语言；
• 显式栈便于控制深度，也适合用运算符栈和值栈实现的方案；
• 两者都需要先定义语法、优先级、结合性和错误行为。

八、常见错误

1. 把表达式当成从左到右的普通字符串：会破坏优先级和括号语义。
2. 没有拆分语法层级：加减、乘法和一元符号混在一个循环里容易出错。
3. 把一元负号当成二元减号：-3 和 5 - 3 的语法位置不同。
4. 不跳过空白：在每层解析开始和识别运算符前都要统一处理空格。
5. 漏掉完整消费检查：解析器可能接受有效前缀并忽略尾部垃圾。
6. 把非法输入静默转换成 0：错误应显式报出，而不是制造成功形状的结果。
7. 忽略递归深度：极深括号输入可能触发栈溢出；约束较大时可改用显式栈。
8. 直接使用宿主语言的 eval：这会执行语言表达式而非受限语法，输入边界难以控制；算法练习应实现题目定义的解析器。

九、与后续主题的连接

表达式计算同时用到了本系列中的几条主线：

• 数字和运算符是输入字符，需要逐个模拟解析状态；
• 括号嵌套可以由递归或栈维护；
• 一元运算与优先级需要清晰定义状态转移；
• 语法规则本身就是一种分层结构。

完成基础表达式解析后，可以在后续练习中增加除法、取模、幂运算、变量或函数调用，但每增加一种语法，都要明确优先级、结合性、数值范围和错误处理。

小结

表达式求值的核心是先定义语法，再按优先级分层解析。递归下降让每个函数对应一种语法规则，括号通过递归处理；解析完成后还要确认输入已经被完整消费。本篇支持整数、空白、加减乘、括号和一元符号，为更复杂的语法扩展打下基础。