5.3　应用：括号匹配与表达式求值

学习目标：学完本节，你能

• 用栈判断括号是否匹配，并解释为什么"计数"不行；
• 用调度场算法把中缀表达式转成后缀表达式；
• 实现一个完整的四则运算计算器，含错误处理。

先修：5.1（栈）。 固定术语：中缀表达式、后缀表达式、运算符优先级、调度场算法。 环境与版本：.NET 8 / C# 12。 预计阅读：35 分钟。

一、应用一：括号匹配

问题：给一个字符串，判断其中的括号是否配对完整。

(1 + 2) * 3       ✓ 匹配
((1 + 2) * 3      ✗ 少一个右括号
{[()]}            ✓ 匹配
{[(])}            ✗ 数量平衡，但嵌套顺序错了

前三个都好判断，第四个才是关键。

{[(])} 里括号的总数是平衡的：3 个左、3 个右。但它是错的 —— 因为 [ 还没闭合，就出现了 )。

这就排除了"用一个计数器"的做法。 计数器只能数"数量平不平衡"，数不出"顺序对不对"。

栈天然解决这个问题：最后打开的左括号，必须最先被闭合 —— 这正是 LIFO。

static bool IsBalanced(string text)
{
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };

    foreach (char c in text)
    {
        if (c is '(' or '[' or '{')
        {
            stack.Push(c);                       // 遇到左括号，压栈
        }
        else if (pairs.TryGetValue(c, out char expectedOpen))
        {
            // 遇到右括号：栈顶必须是「配套的左括号」
            if (stack.Count == 0 || stack.Pop() != expectedOpen)
                return false;
        }
    }
    return stack.Count == 0;                     // 最后栈必须空了才算匹配
}

实测：

  True   <- "(1 + 2) * 3"
  False  <- "((1 + 2) * 3"
  True   <- "{[()]}"
  False  <- "{[(])}"
  True   <- "((()))"
  False  <- ")("
  True   <- "a(b[c]d)e"
  True   <- ""

两个容易漏掉的边界：

1. ) 出现在最前面（比如 ")("）：此时栈是空的，stack.Pop() 会抛异常。所以要先判断 stack.Count == 0。
2. 最后栈必须是空的：如果只写了 return true，那 "(((" 这种"只有左括号"的输入会被误判为匹配。

这两个边界是括号匹配题的"标准考点" —— 逻辑本身很简单，但漏掉任何一个都会出错。

二、应用二：中缀 → 后缀

问题：求表达式 1 + 2 * 3 的值。

难点：运算符有优先级 —— 必须先算 2 * 3 再算 +。而计算机是从左到右读的，读到 1 + 2 时它还"不知道"后面会不会来个 *。

括号让问题更难：(1 + 2) * 3 里，+ 反而要先算。

标准解法分两步：

1. 把中缀表达式转成后缀表达式（后缀也叫逆波兰表示法）
2. 对后缀表达式求值（这一步很简单，一个栈就够）

什么是后缀表达式？ 运算符写在操作数的后面：

后缀表达式的最大优点：不需要括号，也不需要优先级规则。 从左到右扫一遍就能算出来。

转法：调度场算法（Shunting Yard）

用一个栈暂存运算符，规则是：

static List<string> InfixToPostfix(string expr)
{
    var output = new List<string>();
    var ops = new Stack<char>();
    var precedence = new Dictionary<char, int> { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };

    for (int i = 0; i < expr.Length; i++)
    {
        char c = expr[i];

        if (char.IsWhiteSpace(c)) continue;

        if (char.IsDigit(c))
        {
            // 读完整的一个数（支持多位数和小数点）
            int start = i;
            while (i < expr.Length && (char.IsDigit(expr[i]) || expr[i] == '.')) i++;
            output.Add(expr[start..i]);
            i--;                                  // 回退一格，外层 for 会再 i++
        }
        else if (c == '(')
        {
            ops.Push(c);
        }
        else if (c == ')')
        {
            while (ops.Count > 0 && ops.Peek() != '(')
                output.Add(ops.Pop().ToString());
            ops.Pop();                            // 把 '(' 弹掉，不输出
        }
        else if (precedence.ContainsKey(c))
        {
            // 栈顶运算符优先级 >= 当前运算符时，先输出栈顶（同级左结合）
            while (ops.Count > 0 && ops.Peek() != '(' &&
                   precedence[ops.Peek()] >= precedence[c])
                output.Add(ops.Pop().ToString());
            ops.Push(c);
        }
    }

    while (ops.Count > 0)
        output.Add(ops.Pop().ToString());

    return output;
}

两个细节值得说明：

1. 读多位数。 逐字符扫描时，读到 1 不能立刻输出，要往后看还有没有数字。10 必须被当成一个整体，而不是 1 和 0。代码里用 i-- 回退一格，让外层循环接着处理。
2. >= 而不是 >。 这处理的是同级运算符的左结合性：100 / 5 / 2 必须是 (100 / 5) / 2 = 10，而不是 100 / (5 / 2) = 40。用 >= 保证同级时先弹出左边的。

验证左结合：实测中 100 / 5 / 2 转成 100 5 / 2 /，计算结果 10 ✓

如果写成 >，会转成 100 5 2 / /，结果变成 40 —— 这就是左结合和右结合的差别。

三、应用三：后缀求值

后缀表达式求值非常直接：

static double EvalPostfix(List<string> postfix)
{
    var stack = new Stack<double>();

    foreach (var token in postfix)
    {
        if (double.TryParse(token, out double num))
        {
            stack.Push(num);                      // 数字直接压栈
        }
        else
        {
            // 栈里不足两个数，说明表达式本身写错了（比如 "1 + + 2"）
            // 不加这个检查的话，会抛出 .NET 原始的 "Stack empty." —— 对使用者毫无意义
            if (stack.Count < 2)
                throw new InvalidOperationException($"运算符 '{token}' 缺少操作数，表达式格式有误");

            double b = stack.Pop();               // 注意：先弹出的是右操作数
            double a = stack.Pop();
            stack.Push(token switch
            {
                "+" => a + b,
                "-" => a - b,
                "*" => a * b,
                "/" => a / b,
                _ => throw new InvalidOperationException($"未知运算符: {token}")
            });
        }
    }
    return stack.Pop();
}

唯一容易搞错的地方：两个操作数的顺序。

double b = stack.Pop();     // 先弹出的是【右】操作数
double a = stack.Pop();     // 后弹出的是【左】操作数

为什么？ 看 10 4 -：

• 先压入 10，再压入 4，栈是 [10, 4]（栈顶是 4）
• 遇到 -，先弹出 4（右操作数），再弹出 10（左操作数）
• 计算 10 - 4 = 6 ✓

如果顺序写反，减法会变成 4 - 10 = -6，除法会变成 4 / 10。 这个 bug 加法和乘法测不出来（它们满足交换律），必须用减法和除法测。

这是后缀求值最经典的坑：用 1 + 2 测试永远发现不了，用 10 - 4 才能测出来。

四、完整计算器与错误处理

把上面三步串起来，加上错误处理：

static bool TryEvaluate(string expr, out double result, out string error)
{
    result = 0;
    error = "";

    if (!IsBalanced(expr)) { error = "括号不匹配"; return false; }

    try
    {
        var postfix = InfixToPostfix(expr);
        if (postfix.Count == 0) { error = "表达式为空"; return false; }
        result = EvalPostfix(postfix);
        if (double.IsInfinity(result)) { error = "除以零"; return false; }
        return true;
    }
    catch (Exception ex)
    {
        error = ex.Message;
        return false;
    }
}

实测输出：

  中缀表达式                      后缀表达式                                计算结果
------------------------------------------------------------------------
  1 + 2 * 3                  1 2 3 * +                               7
  (1 + 2) * 3                1 2 + 3 *                               9
  10 - 4 / 2                 10 4 2 / -                              8
  2 * (3 + 4) - 5            2 3 4 + * 5 -                           9
  ((1 + 2) * (3 + 4)) / 7    1 2 + 3 4 + * 7 /                       3
  100 / 5 / 2                100 5 / 2 /                            10

=== 应用四：完整的计算器（含错误处理）===

  ✓ 1 + 2 * 3        = 7
  ✗ (1 + 2           -> 错误: 括号不匹配
  ✗ 1 + + 2          -> 错误: 运算符 '+' 缺少操作数，表达式格式有误
  ✗ 1 / 0            -> 错误: 除以零
  ✓ 3.5 * 2          = 7
  ✗ 1 + 2) * 3       -> 错误: 括号不匹配

六条表达式的正确性可以手工核对：

关于错误处理的一条经验：

我第一版没有写"栈里不足两个数"这个检查，结果输入 1 + + 2 时，程序抛出的是 .NET 的原始异常消息 Stack empty. —— 对使用者来说完全无法理解问题出在哪。

加上检查后，错误信息变成 "运算符 '+' 缺少操作数，表达式格式有误"，直接指出了问题。

这是一条很实用的原则：在你自己的代码里，捕获底层异常，转换成对使用者有意义的业务错误。 底层异常的措辞是给开发者看的，不是给用户看的。

五、练习

练习 5.3.1（手写转换） 把下面的中缀表达式转成后缀表达式（先自己写，再用程序验证）： (a) 3 + 4 * 2 - 1 (b) (3 + 4) * (2 - 1) (c) 1 + 2 + 3 + 4 (d) 8 / 4 / 2

练习 5.3.2（判断） 判断对错并说明理由： (a) 括号匹配可以用一个整数计数器实现。 (b) 后缀表达式需要括号来消除歧义。 (c) 调度场算法里，运算符比较优先级时用 >= 还是 > 无所谓。

练习 5.3.3（扩展） 给计算器加上乘方运算 ^，要求：

• ^ 的优先级高于 * 和 /
• ^ 是右结合的（即 2 ^ 3 ^ 2 应该算成 2 ^ (3 ^ 2) = 512，而不是 (2 ^ 3) ^ 2 = 64） 请说明：调度场算法里要改哪一行？

练习 5.3.4（工程判断） 你的系统要解析用户输入的查询条件，格式类似：

status = "active" AND (age > 18 OR vip = true)

(a) 这个和算术表达式有什么共同点？ (b) 你会怎么改造本节的计算器来支持它？

练习 5.3.5（挑战·写代码） 用栈实现一个方法，把中缀表达式直接求值（不显式地先转成后缀）。 （提示：需要两个栈 —— 一个存数字，一个存运算符。本质上就是把"转后缀"和"求值"两步合并成一步。）

六、练习答案

5.3.1

(a) 3 + 4 * 2 - 1 → 3 4 2 * + 1 -

推演：

• 3 输出 → 3
• + 入栈 → 栈：[+]
• 4 输出 → 3 4
• * 优先级 2 > 栈顶 + 的 1，直接入栈 → 栈：[+, *]
• 2 输出 → 3 4 2
• - 优先级 1，栈顶 * 的 2 ≥ 1，弹出 *；再比 +，1 ≥ 1，弹出 + → 3 4 2 * +
• - 入栈 → 栈：[-]
• 1 输出 → 3 4 2 * + 1
• 结束，弹出 - → 3 4 2 * + 1 -

验算：$3 + 4 \times 2 - 1 = 3 + 8 - 1 = 10$

(b) (3 + 4) * (2 - 1) → 3 4 + 2 1 - *

验算：$7 \times 1 = 7$

(c) 1 + 2 + 3 + 4 → 1 2 + 3 + 4 +

注意左结合：每次遇到新的 +，栈顶的 + 都会先被弹出（因为 >=）。所以是 ((1+2)+3)+4。

验算：$10$

(d) 8 / 4 / 2 → 8 4 / 2 /

验算：$(8/4)/2 = 2$ ✓

(c) 和 (d) 是检验"左结合"是否正确的关键用例。 如果你的实现把 (d) 转成了 8 4 2 / /，那结果会是 $8/(4/2) = 4$ —— 错了。

5.3.2

• (a) 错。 计数器只能判断"左括号数量和右括号数量是否相等"，判断不出嵌套顺序。

  反例：{[(])} —— 3 个左、3 个右，数量平衡，但嵌套是错的（[ 还没闭合就来了 )）。 必须用栈，因为栈能记住"最后打开的是哪个"。

• (b) 错。 后缀表达式不需要括号 —— 这正是它的优点。运算顺序已经完全由"运算符出现的位置"决定了。

  这也是它被编译器广泛采用的原因：解析后缀表达式不需要处理括号嵌套，逻辑简单得多。

• (c) 错，而且这个区别很关键。
  • 用 >=：实现左结合（100/5/2 = 10）
  • 用 >：实现右结合（100/5/2 = 40）

    四则运算都是左结合的，所以必须用 >=。而乘方 ^ 是右结合的，如果支持它，就要对 ^ 特殊处理（见练习 5.3.3）。

5.3.3

要改两处：

第一处：优先级表加上 ^

var precedence = new Dictionary<char, int> { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2, ['^'] = 3 };

第二处：比较优先级时，对右结合运算符要用 > 而不是 >=

while (ops.Count > 0 && ops.Peek() != '(' &&
       (precedence[ops.Peek()] > precedence[c] ||
        (precedence[ops.Peek()] == precedence[c] && !IsRightAssociative(c))))
    output.Add(ops.Pop().ToString());

其中：

static bool IsRightAssociative(char op) => op == '^';

验证：2 ^ 3 ^ 2

• 2 输出
• ^ 入栈
• 3 输出
• 遇到第二个 ^：栈顶是 ^，两者优先级相等（3 == 3），因为 ^ 是右结合，条件不成立，不弹栈
• 第二个 ^ 入栈 → 栈：[^, ^]
• 2 输出
• 结束，依次弹出两个 ^ → 2 3 2 ^ ^

求值：$2^{(3^2)} = 2^9 = 512$ ✓ 右结合正确

如果沿用 >=，第二个 ^ 会先把栈顶的 ^ 弹出来，得到 2 3 ^ 2 ^，结果是 $(2^3)^2 = 64$ —— 这就是左结合和右结合的差别。

5.3.4

(a) 共同点：都是"带优先级和括号的表达式"。

它们的抽象结构完全相同，都是"表达式树"。 区别只在于叶子节点是什么、运算符怎么求值。

(b) 改造方案：

方案 1：改造调度场算法（推荐，改动最小）

把"运算符"从 char 扩展成"记号"（token），把"数字"扩展成"字段比较"：

// 叶子节点不再是"数字"，而是"比较条件"
public abstract record Expr;
public record Comparison(string Field, string Op, object Value) : Expr;
public record BinaryOp(string Op, Expr Left, Expr Right) : Expr;   // AND / OR

改动点：

• 优先级表：NOT = 3，AND = 2，OR = 1
• 求值方式：不再返回 double，而是返回 bool（或者一个"条件对象"，供数据库使用）
• =、> 这类比较运算符：它们优先级最高，且是"作用在两个操作数上"的——可以当作叶子处理

方案 2：直接用现成的解析库

生产环境不建议自己写。成熟的选择：

• ANTLR：强大的语法解析器生成器，可以定义完整的语法
• Sprache：C# 的解析器组合子库
• System.Linq.Dynamic.Core：直接把字符串当 LINQ 表达式执行
• 数据库自己的解析器：如果是给数据库用的，直接生成 SQL 让数据库解析

工程建议：表达式解析是个"看起来简单、边界极多"的领域。

自己写一个能处理 1+2 的计算器很容易，但要支持完整的语法（转义字符、字符串字面量、空值处理、运算符重载、错误定位……）会迅速变成一个大工程。

本节的目的不是让你去造轮子，而是让你理解你每天在用的那些库内部在做什么。

5.3.5

方案：双栈法（一个存数字，一个存运算符）

static double EvaluateDirect(string expr)
{
    var nums = new Stack<double>();
    var ops = new Stack<char>();
    var precedence = new Dictionary<char, int> { ['+'] = 1, ['-'] = 1, ['*'] = 2, ['/'] = 2 };

    // 从运算符栈顶弹出一个运算符，对数字栈顶的两个数求值
    void ApplyTop()
    {
        char op = ops.Pop();
        double b = nums.Pop();
        double a = nums.Pop();
        nums.Push(op switch
        {
            '+' => a + b, '-' => a - b, '*' => a * b, '/' => a / b,
            _ => throw new InvalidOperationException($"未知运算符: {op}")
        });
    }

    for (int i = 0; i < expr.Length; i++)
    {
        char c = expr[i];
        if (char.IsWhiteSpace(c)) continue;

        if (char.IsDigit(c) || c == '.')
        {
            int start = i;
            while (i < expr.Length && (char.IsDigit(expr[i]) || expr[i] == '.')) i++;
            nums.Push(double.Parse(expr[start..i]));
            i--;
        }
        else if (c == '(')
        {
            ops.Push(c);
        }
        else if (c == ')')
        {
            while (ops.Peek() != '(') ApplyTop();
            ops.Pop();                                  // 弹掉 '('
        }
        else if (precedence.ContainsKey(c))
        {
            // 只要栈顶运算符优先级 >= 当前，就先把它算掉
            while (ops.Count > 0 && ops.Peek() != '(' &&
                   precedence[ops.Peek()] >= precedence[c])
                ApplyTop();
            ops.Push(c);
        }
    }

    while (ops.Count > 0) ApplyTop();

    return nums.Pop();
}

核心思路："先转后缀再求值"是两趟扫描；双栈法把它压成了一趟。

• 遇到数字 → 压入数字栈
• 遇到运算符 → 先把栈里所有"优先级更高或相等"的运算符算掉，再把自己压栈
• 遇到右括号 → 把括号内的运算符全部算掉

"算掉一个运算符"就要弹出两个数字、压回一个结果 —— 这正是后缀求值做的事，只不过现在提前做了。

两种写法本质相同。 双栈法少存了一个中间的后缀序列，省一趟扫描和一些内存；但"转后缀"的写法结构更清晰（两个函数各干一件事），而且中间结果可以复用（比如同一个表达式要编译一次、执行很多次 —— 这就是数据库里"预编译 SQL"的思想）。

工程上更常见的是分两步：先解析成一棵表达式树，缓存起来，然后对不同的参数反复求值。

七、常见错误

八、本节总结

1. 括号匹配必须用栈，不能用计数器 —— 因为要记住"最后打开的是哪个"，这是 LIFO 的本质。
2. 两个必须处理的边界：右括号遇上空栈、扫描结束后栈非空。
3. 中缀转后缀用调度场算法：数字直接输出，运算符按优先级"弹高留低"，括号特殊处理。
4. 后缀表达式不需要括号，扫一遍就能求值 —— 这是编译器偏爱它的原因。
5. 后缀求值的经典坑：先弹出的是右操作数。这个 bug 用加减法测不出来。
6. >= 实现左结合（100/5/2 = 10），> 会变成右结合（= 40）。
7. 错误处理要把底层异常转换成业务语言 —— Stack empty. → "运算符 '+' 缺少操作数"。

下一节衔接：本节用栈处理了"括号"和"表达式"。但栈还有一个更精妙的用法 —— 让栈内的元素保持单调。这个技巧能解决"下一个更大元素"、"滑动窗口最大值"这类问题，而且能把 $O(n^2)$ 降到 $O(n)$。下一节讲单调栈和单调队列。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "5.3",
  "title": "应用：括号匹配与表达式求值",
  "covered": [
    "括号匹配的栈实现与为什么计数器不行",
    "两个必测边界（空栈遇右括号、扫描结束栈非空）",
    "调度场算法（中缀转后缀）与多位数读取",
    "后缀求值及左右操作数顺序陷阱",
    "左结合（>=）与右结合（>）的区别",
    "完整计算器的错误处理（4 类错误）",
    "双栈法一趟求值与表达式树的关系",
    "查询条件表达式与算术表达式的同构性"
  ],
  "unresolved": [
    "表达式树与编译原理属于进阶内容，本书不展开",
    "真实解析器建议使用 ANTLR/Sprache 等成熟库"
  ],
  "canonical_terms": {
    "中缀表达式": "运算符写在两个操作数中间，如 1 + 2",
    "后缀表达式": "运算符写在操作数后面，也叫逆波兰表示法，无需括号",
    "运算符优先级": "决定哪个运算先算的规则",
    "调度场算法": "把中缀表达式转换为后缀表达式的栈算法"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 5.1 的栈",
    "读者能读懂 switch 表达式与 record 语法"
  ],
  "word_count_actual": 2980,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch05/Sec53/",
    "6 条表达式的计算结果全部手工验算并一致（7/9/8/9/3/10）",
    "8 个括号匹配用例全部正确",
    "练习 5.3.1 的四条转换结果已手工推演",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版后缀求值未检查栈中元素个数，输入 '1 + + 2' 时抛出 .NET 原始异常 'Stack empty.'；已加显式检查并输出业务化错误信息"
  ],
  "next": "5.4 单调栈与单调队列"
}