Lesson 72: ANSI 终端计算器

练习任务

难度：中

实现一个终端四则运算计算器，使用双栈算法（Two-Stack Algorithm）对固定表达式求值，并用 ANSI 转义序列美化彩色输出。

子任务：

parse_number(s, pos) — 从字符串位置 *pos 提取整数，支持多位数
precedence(op) — 返回运算符优先级（*/ 为 2，+- 为 1）
apply_op(a, b, op) — 对两个操作数执行四则运算，含除零保护
evaluate(s) — 双栈算法核心：操作数栈 + 运算符栈协同求值
print_colored(color, text) — 用 ANSI 颜色打印文本
main() — 驱动两个测试表达式 "3+4*2" 和 "(5+3)*2"，打印彩色结果

本课测试表达式：

"3+4*2"   → 11    (运算符优先级：先乘后加)
"(5+3)*2" → 16    (括号改变优先级)

验证方式：make test 将程序输出与 expected_output.txt 逐字节对比（包含 ANSI 转义序列）。

提示：双栈算法的精髓在于"一个操作数栈 + 一个运算符栈"协同工作。思考：当遇到一个运算符时，什么时候可以直接压栈？什么时候需要先弹栈计算栈中已有的运算符？两条规则——( 是"屏障"不参与比较，同优先级用 >= 保证左结合。

核心知识点

双栈算法（Dijkstra） — 操作数栈 nums[] + 运算符栈 ops[] 一遍扫描求值，无需构建显式语法树
运算符优先级编码 — precedence() 函数将 */ 映射为 2、+- 映射为 1、( 映射为 0
括号边界处理 — 遇到 ( 直接压入 ops 栈作为"屏障"；遇到 ) 弹栈计算直到弹出 (
左结合性保证 — 弹栈条件使用 >=（而非 >），确保 a-b-c 解析为 (a-b)-c
parse_number 多位数解析 — while 循环累积 val*10 + digit，不能用 if 只读一位
apply_op 除零保护 — 除法需检查 b != 0，除零时返回 0
isdigit 的类型安全 — 参数必须转换为 unsigned char，否则负数 char 导致未定义行为
ANSI 转义序列结构 — \033[<code>m 控制终端颜色与样式，是一段"带内信令"
颜色泄漏与 RESET — 每次彩色输出后必须跟 \033[0m 重置，否则后续显示均被染色
输出精确匹配 — make test 用 diff 逐字节比较含 ANSI 序列的输出流

代码框架

terminal_calc.c

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ─── ANSI 颜色宏 ─── */
#define COLOR_GREEN  "\033[32m"
#define COLOR_RED    "\033[31m"
#define COLOR_CYAN   "\033[36m"
#define COLOR_YELLOW "\033[33m"
#define COLOR_BOLD   "\033[1m"
#define COLOR_RESET  "\033[0m"

/* TODO 1: parse_number — 从 s[*pos] 提取整数 */
static int parse_number(const char *s, int *pos) {
    // ① val = 0
    // ② while (isdigit((unsigned char)s[*pos]))
    //      val = val*10 + (s[*pos] - '0'); (*pos)++;
    // ③ return val
}

/* TODO 2: precedence — 返回运算符优先级 */
static int precedence(char op) {
    // ④ */ 返回 2; +- 返回 1; 其他(含 '(') 返回 0
}

/* TODO 3: apply_op — 对 a 和 b 执行运算 op */
static int apply_op(int a, int b, char op) {
    // ⑤ switch(op): case '+': return a+b; case '-': return a-b;
    //               case '*': return a*b; case '/': return b!=0 ? a/b : 0;
}

/* TODO 4: evaluate — 双栈算法核心 */
static int evaluate(const char *s) {
    // ⑥ int nums[64], ntop=0; char ops[64], otop=0;
    // ⑦ while (i < len):
    //      - 空格: i++, continue
    //      - 数字: nums[ntop++]=parse_number(s,&i); 打印 "  parse_number: %d\n"
    //      - '(':  打印 "  enter paren: (\n"; ops[otop++]='('; i++
    //      - ')':  打印 "  exit paren: )\n"; while(ops[otop-1]!='(') 弹栈计算;
    //              弹出 '(' (otop--)
    //      - 运算符: 打印 "  operator: %c (precedence=%d)\n", s[i], prec;
    //               while(otop>0 && ops[otop-1]!='(' && precedence(ops[otop-1])>=prec)
    //                 弹栈计算; ops[otop++]=s[i]; i++
    // ⑧ while (otop>0) 弹栈计算剩余运算符
    // ⑨ return nums[0]
}

/* TODO 5: print_colored — 用 ANSI 颜色打印 */
static void print_colored(const char *color, const char *text) {
    // ⑩ printf("%s%s" COLOR_RESET, color, text);
}

/* TODO 6: main — 驱动测试表达式并打印彩色结果 */
int main(void) {
    // ⑪ const char *expressions[] = {"3+4*2", "(5+3)*2"};
    //    int expected[] = {11, 16};
    // ⑫ 打印加粗黄色标题 "=== ANSI Terminal Calculator ==="
    // ⑬ for 循环: 打印青色解析头 → evaluate(expr) → 打印结果
    //    正确: COLOR_GREEN  "  OK: %s = %d"
    //    错误: COLOR_RED    "  FAIL: %s = %d (expected %d)"
    // ⑭ 打印加粗黄色汇总 "=== Summary ===", correct/errors 统计
    // ⑮ return 0
}

骨架中标注了 ① ~ ⑮ 共 15 个关键位置。先尝试自己填充。

核心挑战在于：evaluate 的四种字符分支如何分流？precedence('(') 为什么返回 0？弹栈计算时为什么先取 b 再取 a？COLOR_RESET 为什么必须放在 print_colored 末尾？

TIP

先不要往下翻看参考解答。用纸笔追踪 "3+4*2" 的双栈执行过程。每一步记录 nums[]、ops[]、ntop、otop 的状态变化。理解透彻后，"(5+3)*2" 的括号处理就会水到渠成。

深度讲解

1. 表达式求值的三种经典方法与双栈算法原理

1.1 表达式求值——计算器核心问题

"3+4*2" 对人类来说一目了然，但对计算机来说，它只是 5 个字符的序列。计算机需要：解析（识别数字和运算符）、排序（决定计算顺序）、求值（执行计算）。这三种需求催生了三种经典方法。

表达式求值的三种经典方法：

方法一：双栈算法 (Dijkstra, 1960)
  操作数栈 nums[]  +  运算符栈 ops[]
  顺序扫描，根据优先级弹栈计算
  特点：简单直观，一遍 O(n)，适合教学 ✓

方法二：递归下降解析 (Recursive Descent)
  函数调用层次编码优先级: expr() → term() → factor()
  递归调用替代显式栈
  特点：结构化好，易于扩展语法，适合编译器前端

方法三：逆波兰表达式 (RPN / Postfix)
  中缀 → 后缀（Shunting-yard 算法）→ 求值（栈式求值）
  两遍扫描，或一步到位
  特点：适：适合栈式计算机（如 Forth 语言、HP 计算器）

本题选择方法一——双栈算法。

1.2 双栈数据结构设计

双栈算法的核心是两个并行的栈数组：

操作数栈 nums[]                 运算符栈 ops[]
┌───┬───┬───┬───┬───┐          ┌───┬───┬───┬───┬───┐
│ 3 │ 4 │ 2 │   │   │          │ + │ * │   │   │   │
└────┴───┴───┴───┴───┘          └───┴───┴───┴───┴───┘
  ↑ ntop = 3                     ↑ otop = 2

栈顶指针语义：ntop/otop 始终指向下一个空位。
  压栈: nums[ntop++] = value     ops[otop++] = ch
  弹栈: value = nums[--ntop]     ch = ops[--otop]

NOTE

为什么用数组而非链表模拟栈？本题表达式长度有限（< 64 个 token），固定大小数组最简单高效。ntop 从 0 开始累加——这恰好是数组模拟栈的标准手法（与 Lesson 34 括号匹配中的用法一脉相承）。

1.3 双栈算法的四条核心规则

规则 1: 遇到数字 → 直接压入 nums 栈
规则 2: 遇到 '('   → 直接压入 ops 栈（作为屏障）
规则 3: 遇到 ')'   → 不断弹栈计算，直到弹出 '('
规则 4: 遇到运算符 → 先弹出 ops 栈中所有优先级 ≥ 当前运算符的运算符进行
                    计算，再将当前运算符压栈

遍历结束后，弹出 ops 栈中所有剩余运算符进行计算。
最终 nums[0] 即为结果。

这四条规则看似简单，但每条背后都有精妙设计：

规则 1：数字不需要"等待"，压栈即可
规则 2：( 是屏障——它内部的表达式需要被下一条规则显式处理
规则 3：) 负责清理括号内的所有待处理运算
规则 4：>= 条件同时满足"先乘除后加减"和"左结合"两种需求

1.4 运算符优先级表

┌─────────────────┬──────────┬──────────┐
│ 运算符           │ 优先级    │ 结合性    │
├─────────────────┼──────────┼──────────┤
│ (               │ 0 (特殊)  │ —        │
│ +  -            │ 1 (低)    │ 左结合    │
│ *  /            │ 2 (高)    │ 左结合    │
└─────────────────┴──────────┴──────────┘

左结合意味着 a - b - c 被解析为 (a - b) - c。在双栈算法中通过弹栈条件的 >= 实现。

IMPORTANT

( 的优先级为 0 是精心设计的。这确保了 precedence('(') >= prec 对任何 prec >= 1 都不成立，( 永远不会被弹栈条件触发。只有当显式匹配的 ) 到来时，括号内的运算才会被处理。

2. parse_number——多位数解析与 isdigit 安全

2.1 从字符到数字的累积过程

parse_number.c

static int parse_number(const char *s, int *pos) {
    int val = 0;
    while (isdigit((unsigned char)s[*pos])) {
        val = val * 10 + (s[*pos] - '0');
        (*pos)++;
    }
    return val;
}

以 s = "42+8", *pos = 0 为例：

迭代 1: s[0]='4' → isdigit ✓ → val = 0*10 + ('4'-'0') = 0 + 4 = 4, pos → 1
迭代 2: s[1]='2' → isdigit ✓ → val = 4*10 + ('2'-'0') = 40 + 2 = 42, pos → 2
迭代 3: s[2]='+' → isdigit ✗ → 循环结束

返回值 42, *pos = 2（指向 '+'）

关键细节：*pos 通过指针传递，使得调用方 evaluate 中的循环索引 i 被自动推进。函数返回后，i 正好指向数字之后的下一个字符。

2.2 while 而非 if：多位数是刚需

错误示例（仅读一位）:
  if (isdigit(s[*pos])) {
      val = s[*pos] - '0';
      (*pos)++;
  }

  "42" 被解析为 4，丢失了 2！

正确做法:
  while (isdigit(...)) {  // 循环直到非数字
      val = val * 10 + (s[*pos] - '0');
      (*pos)++;
  }

2.3 isdigit 的 unsigned char 强制转换

/* 错误: char 为负值时未定义行为 */
isdigit(s[*pos]);                         // 危险!

/* 正确: 先转为 unsigned char */
isdigit((unsigned char)s[*pos]);          // 安全 ✓

为什么需要？ C 标准规定 isdigit 的参数必须是 unsigned char 或 EOF（-1）。如果字符串中包含中文 UTF-8 字节（如 "3+好"），该字节的 char 值可能是负数（如 0xE5 → -27），传 | isdigit 是未定义行为。虽然本题表达式不含中文，但这是防御性编程的好习惯。

char 类型与 isdigit:
  char 可能是有符号或无符号，取决于编译器实现（x86 通常为有符号）。
  
  有符号 char: 范围 -128 ~ 127
  (unsigned char): 范围 0 ~ 255
  
  isdigit 内部查表(通常用数组索引): table[ch]
  如果 ch=-27 → 负索引访问 → 未定义行为！

3. precedence——优先级编码

3.1 最简单的函数，最核心的设计

precedence.c

static int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;  /* '(' 或任何其他字符 */
}

三行代码，但含义深远。返回值 0/1/2 的三级划分是双栈算法"先乘除后加减"的数学基础。

3.2 为什么 '(' 返回 0？

假设 precedence('(') = 3（试图把它当"最高优先级运算符"）:

| 表达式 "(5+3)*2", 读到 '+' 时:
  ops = [(, +]
  ops 栈顶 '(' 优先级 3, '+' 优先级 1
  3 >= 1 → 触发弹栈! → 把 '(' 当成运算符做 apply_op → 灾难!

正确的做法: precedence('(') = 0
  0 >= 1 为 false → 不弹栈 → '(' 安全地留在栈中作为屏障 ✓

( 不是真正的运算符，它在栈中的角色是"标记屏障"。优先级 0 确保它永远不会被弹栈条件触发，只能被显式的 ) 处理移除。

precedence_validation.c

/* 验证 precedence 的边界情况 */
#include <stdio.h>

int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

int main(void) {
    printf("* : %d\n", precedence('*'));   // 2
    printf("+ : %d\n", precedence('+'));   // 1
    printf("( : %d\n", precedence('('));   // 0
    printf("x : %d\n", precedence('x'));   // 0 (未知字符)
    return 0;
}

4. apply_op——四则运算与除零保护

4.1 switch 分发四种运算

apply_op.c

static int apply_op(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return (b != 0) ? a / b : 0;
        default:  return 0;
    }
}

参数顺序至关重要：a 是左操作数，b 是右右操作数 b，后弹出的是左操作数 a。

/* 弹栈计算的标准模式——顺序不能颠倒！ */
int b = nums[--ntop];    // 先弹 = 右操作数（后入的）
int a = nums[--ntop];    // 后弹 = 左操作数（先入的）
char op = ops[--otop];
nums[ntop++] = apply_op(a, b, op);

CAUTION

如果交换 a 和 b 的弹出顺序（先取 a 再取 b），apply_op(a, b, '-') 将变为 b - a——减法结果符号反转。对于 "3-1"，正确结果是 2，错误结果是 -2。这是一个极易疏忽的陷阱。

4.2 除零保护

case '/': return (b != 0) ? a / b : 0;

C 语言中整数除以 0 会导致未定义行为（通常触发 SIGFPE 信号导致程序崩溃）。虽然本题的测试表达式 "3+4*2" 和 "(5+3)*2" 不会触发除零，但防御性地添加检查是好习惯。返回 0 是一个合理的安全回退值。

5. evaluate——双栈算法完整实现与逐步跟踪

5.1 完整算法伪代码

function evaluate(s):
    nums[64], ntop=0; ops[64], otop=0; i=0

    while i < strlen(s):
        if s[i] is space:      i++, continue
        if s[i] is digit:      val = parse_number(s, &i)
                                printf("  parse_number: %d\n", val)
                                nums[ntop++] = val
        else if s[i] is '(':   printf("  enter paren: (\n")
                                ops[otop++] = '('; i++
        else if s[i] is ')':   printf("  exit paren: )\n")
                                while otop>0 && ops[otop-1]!='(':
                                    b=nums[--ntop], a=nums[--ntop]
                                    op=ops[--otop]
                                    nums[ntop++] = apply_op(a,b,op)
                                    printf("  apply_op: %d %c %d = %d\n", a,op,b,...)
                                otop--     // pop '('
                                i++
        else (operator):       prec = precedence(s[i])
                                printf("  operator: %c (precedence=%d)\n", s[i], prec)
                                while otop>0 && ops[otop-1]!='('
                                      && precedence(ops[otop-1]) >= prec:
                                    b=nums[--ntop], a=nums[--ntop]
                                    op=ops[--otop]
                                    nums[ntop++] = apply_op(a,b,op)
                                    printf("  apply_op: ...")
                                ops[otop++] = s[i]; i++

    while otop > 0:           // 处理剩余运算符
        b=nums[--ntop], a=nums[--ntop], op=ops[--otop]
        nums[ntop++] = apply_op(a,b,op)
        printf("  apply_op: ...")

    return nums[0]

5.2 跟踪 "3+4*2" → 11

初始化:             nums=[ ], ntop=0     ops=[ ], otop=0

步骤 1: 读取 '3' → 数字
  parse_number → 3, 打印 "  parse_number: 3"
  nums=[3]           ops=[ ]

步骤 2: 读取 '+' → 运算符, prec=1
  打印 "  operator: + (precedence=1)"
  otop=0, ops 栈空, 直接压栈
  nums=[3]           ops=[+]

步骤 3: 读取 '4' → 数字
  parse_number → 4, 打印 "  parse_number: 4"
  nums=[3,4]         ops=[+]

步骤 4: 读取 '*' → 运算符, prec=2
  栈顶 '+' precedence=1, 1 < 2 → 不弹栈！（乘法优先级更高，需等待）
  打印 "  operator: * (precedence=2)"
  压入 '*'
  nums=[3,4]         ops=[+,*]

步骤 5: 读取 '2' → 数字
  parse_number → 2, 打印 "  parse_number: 2"
  nums=[3,4,2]       ops=[+,*]

步骤 6: 遍历结束, otop=2
  弹出 '*': b=2, a=4, 4*2=8
    打印 "  apply_op: 4 * 2 = 8"
    nums=[3,8]       ops=[+]
  弹出 '+': b=8, a=3, 3+8=11
    打印 "  apply_op: 3 + 8 = 11"
    nums=[11]        ops=[ ]

返回 nums[0] = 11 ✓

5.3 跟踪 "(5+3)*2" → 16

初始化:             nums=[ ], ntop=0     ops=[ ], otop=0

步骤 1: 读取 '(' → 左括号
  打印 "  enter paren: ("
  ops=[(]

步骤 2: 读取 '5' → 数字
  parse_number → 5, 打印 "  parse_number: 5"
  nums=[5]           ops=[(]

步骤 3: 读取 '+' → 运算符, prec=1
  栈顶 '(' → 不弹栈（括号是屏障）
  打印 "  operator: + (precedence=1)"
  nums=[5]           ops=[(,+]

步骤 4: 读取 '3' → 数字
  parse_number → 3, 打印 "  parse_number: 3"
  nums=[5,3]         ops=[(,+]

步骤 5: 读取 ')' → 右括号
  打印 "  exit paren: )"
  弹栈直到 '(':
    弹出 '+': b=3, a=5, 5+3=8
      打印 "  apply_op: 5 + 3 = 8"
      nums=[8]       ops=[(]
  弹出 '('
  nums=[8]           ops=[ ]

步骤 6: 读取 '*' → 运算符, prec=2
  栈空, 直接压栈
  打印 "  operator: * (precedence=2)"
  nums=[8]           ops=[*]

步骤 7: 读取 '2' → 数字
  parse_number → 2, 打印 "  parse_number: 2"
  nums=[8,2]         ops=[*]

步骤 8: 遍历结束, otop=1
  弹出 '*': b=2, a=8, 8*2=16
    打印 "  apply_op: 8 * 2 = 16"
    nums=[16]        ops=[ ]

返回 nums[0] = 16 ✓

5.4 弹栈条件 `>=` 的深层含义

这是双栈算法中最容易被写错的地方。用 > 还是 >= 决定了结合性。

表达式 "3-2-1"（预期: 0）

| 条件 | 行为                             | 结果 | 正确? |
|------|----------------------------------|------|-------|
| >=   | 读到第二个'-', 弹出第一个'-'      | 0    | ✓     |
| >    | 读到第二个'-', 不弹(1 > 1 false) | 2    | ✗     |

用 > 的执行过程:
  nums=[3], ops=[]
  '+'→ nums=[3], ops=[-]
  2  → nums=[3,2], ops=[-]
  '-'→ prec=1, 栈顶'-' prec=1, 1 > 1 为 false → 不弹栈!
       nums=[3,2], ops=[-,-]
  1  → nums=[3,2,1], ops=[-,-]
  END→ 弹出'-': 2-1=1 → nums=[3,1], ops=[-]
       弹出'-': 3-1=2 → nums=[2]  ← 错误!

用 >= 的执行过程:
  2  → nums=[3,2], ops=[-]
  '-'→ prec=1, 栈顶'-' prec=1, 1 >= 1 为 true → 弹栈!
       3-2=1 → nums=[1], ops=[ ]
       压入'-' → nums=[1], ops=[-]
  1  → nums=[1,1], ops=[-]
  END→ 1-1=0 → 正确! ✓

>= 保证左结合：同优先级运算符从左到右依次计算。如果使用 >（只弹更高优先级），则同优先级运算符会"堆积"在栈中，等价于右结合。

IMPORTANT

记忆口诀：>= = Left-associative（左结合），> = Right-associative（右结合，错误）。

5.5 遍历结束后的收尾工作

/* ⚠ 容易遗漏的关键步骤！ */
while (otop > 0) {
    int b = nums[--ntop];
    int a = nums[--ntop];
    char op = ops[--otop];
    nums[ntop++] = apply_op(a, b, op);
    printf("  apply_op: %d %c %d = %d\n", a, op, b, nums[ntop-1]);
}

遍历完字符串后，ops 栈中可能还有未处理的运算符。例如 "3+4" 遍历结束后，ops = [+]——必须执行这个 + 才能得到最终答案。忘记这一步是初学者最常见的 BUG 之一。

6. ANSI 转义序列——终端彩色输出

6.1 转义序列的结构

ANSI 转义序列结构:
  ESC [ 参数 m

  ESC = \033 (八进制) = 0x1B (十六进制) = ^[ (控制字符)

示例: \033[32m → 设置前景色为绿色
       \033[0m  → 重置所有属性

6.2 颜色代码速查

┌──────────────┬──────────┬──────────────────┐
│ 序列          │ 效果      │ 本题宏定义        │
├──────────────┼──────────┼──────────────────┤
│ \033[31m     │ 红色前景  │ COLOR_RED        │
│ \033[32m     │ 绿色前景  │ COLOR_GREEN      │
│ \033[33m     │ 黄色前景  │ COLOR_YELLOW     │
│ \033[36m     │ 青色前景  │ COLOR_CYAN       │
│ \033[1m      │ 加粗/高亮 │ COLOR_BOLD       │
│ \033[0m      │ 重置所有  │ COLOR_RESET      │
└──────────────┴──────────┴──────────────────┘

NOTE

ANSI 转义序列是带内信令（in-band signaling）——控制信息与显示数据共享同一字节流。这既是优势（diff 可直接比较），也是陷阱（忘记 RESET 会污染后续输出）。

6.3 COLOR_RESET 的必要性

错误示例（忘记 COLOR_RESET）:

  printf(COLOR_GREEN "OK\n");    // "OK" 绿色
  printf("Next line\n");          // 仍然是绿色！（泄漏了）
  printf("Another line\n");       // 还是绿色！

正确示例:

  printf(COLOR_GREEN "OK" COLOR_RESET "\n");  // "OK" 绿色
  printf("Next line\n");                        // 恢复正常颜色 ✓

ANSI 转义序列非常像状态机：\033[32m 把终端切换到"绿色模式"，后续所有字符都以绿色显示，直到遇到 \033[0m 重置状态。忘记 COLOR_RESET 不只是"下次输出还是绿色"——它可能一直影响到终端提示符。

6.4 颜色宏的字符串拼接技巧

color_concatenation.c

/*
 * C 语言编译时，相邻的字符串字面量自动拼接。
 * 利用这一特性，颜色宏可以"选择性着色":
 */

/* 常规用法: */
printf(COLOR_GREEN "OK" COLOR_RESET "\n");
// 编译器视角: "\033[32m" "OK" "\033[0m" "\n"
//   拼接结果: "\033[32mOK\033[0m\n"

/* 组合用法: 加粗 + 颜色 */
printf(COLOR_BOLD COLOR_YELLOW "=== Title ===" COLOR_RESET "\n");
//   拼接结果: "\033[1m\033[33m=== Title ===\033[0m\n"

/* 注意顺序: 先样式后颜色 */
printf(COLOR_YELLOW COLOR_BOLD "text" COLOR_RESET "\n");
//   结果: 先设置黄色前景, 再设置加粗 — 两者都生效

这个技巧让代码既简洁又易读——不需要用 strcat 或 sprintf 拼接包含转义序列的字符串。

7. print_colored 与 main——组装全部组件

7.1 print_colored 封装

print_colored.c

static void print_colored(const char *color, const char *text) {
    printf("%s%s" COLOR_RESET, color, text);
}

虽然这个函数只有一行，但它的价值在于封装了 ANSI 着色 + 重置的模式，避免在全代码中重复 COLOR_RESET。调用方只需传入颜色和文本，不必担心忘记重置。

调用示例:

  print_colored(COLOR_GREEN, "OK: 3+4*2 = 11");
  // 等价于: printf("\033[32mOK: 3+4*2 = 11\033[0m");

  print_colored(COLOR_RED, "FAIL");
  // 等价于: printf("\033[31mFAIL\033[0m");

7.2 main 的测试驱动结构

main_skeleton.c

int main(void) {
    const char *expressions[] = {"3+4*2", "(5+3)*2"};
    int expected[] = {11, 16};
    int num_expr = 2;
    int correct = 0;

    /* 标题 */
    printf(COLOR_BOLD COLOR_YELLOW
           "=== ANSI Terminal Calculator ===" COLOR_RESET "\n");
    printf("Evaluating %d expressions with ANSI color output.\n\n",
           num_expr);

    /* 逐个求值 */
    for (int i = 0; i < num_expr; i++) {
        printf(COLOR_CYAN "Parsing: \"%s\"" COLOR_RESET "\n",
               expressions[i]);
        int result = evaluate(expressions[i]);
        printf("  Result: %d\n", result);

        if (result == expected[i]) {
            printf(COLOR_GREEN "  OK: %s = %d" COLOR_RESET "\n\n",
                   expressions[i], result);
            correct++;
        } else {
            printf(COLOR_RED "  FAIL: %s = %d (expected %d)"
                   COLOR_RESET "\n\n",
                   expressions[i], result, expected[i]);
        }
    }

    /* 汇总 */
    printf(COLOR_BOLD COLOR_YELLOW
           "=== Summary ===" COLOR_RESET "\n");
    printf("Expressions evaluated: %d\n", num_expr);
    printf("Correct: " COLOR_GREEN "%d" COLOR_RESET "\n", correct);
    printf("Errors:  " COLOR_RED "%d" COLOR_RESET "\n",
           num_expr - correct);

    return 0;
}

整个 main 按"标题 → 逐个求值 → 汇总"三段式组织。每段使用不同颜色区分：标题用加粗黄色，解析头用青色，正确结果用绿色，错误用红色。

7.3 输出与验证

make test 使用管道将程序输出与 expected_output.txt 逐字节对比：

make test → ./terminal_calc 2>&1 | diff - expected_output.txt

这意味着输出必须精确匹配——包括空格、换行、ANSI 转义序列的每一个字节。一个多余的空格就会导致 diff 报告差异。

参考解答

练习1: parse_number — 多位数解析

solution_parse_number.c

#include <ctype.h>
#include <stdio.h>

static int parse_number(const char *s, int *pos) {
    int val = 0;
    while (isdigit((unsigned char)s[*pos])) {
        val = val * 10 + (s[*pos] - '0');
        (*pos)++;
    }
    return val;
}

int main(void) {
    const char *expr = "42+8";
    int i = 0;
    int num = parse_number(expr, &i);
    printf("parsed: %d, next char: '%c'\n", num, expr[i]);
    /* 预期输出: parsed: 42, next char: '+' */
    return 0;
}

要点：使用 while 循环（非 if）累积多位数字；*pos 通过指针传递让调用方索引自动推进；(unsigned char) 强制转换防止 isdigit 未定义行为。

练习2: precedence — 优先级编码

solution_precedence.c

#include <stdio.h>

static int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;  /* '(' 或其他字符 */
}

int main(void) {
    printf("* : %d\n", precedence('*'));  // 2
    printf("+ : %d\n", precedence('+'));  // 1
    printf("( : %d\n", precedence('('));  // 0
    printf("# : %d\n", precedence('#'));  // 0
    return 0;
}

要点：( 的优先级为 0 是精妙设计——确保它不会被任何运算符的 >= 条件触发弹栈，只能被 ) 显式处理。

练习3: apply_op — 四则运算

solution_apply_op.c

#include <stdio.h>

static int apply_op(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return (b != 0) ? a / b : 0;
        default:  return 0;
    }
}

int main(void) {
    printf("3 + 5 = %d\n",   apply_op(3, 5, '+'));  // 8
    printf("10 - 7 = %d\n",  apply_op(10, 7, '-')); // 3
    printf("4 * 6 = %d\n",   apply_op(4, 6, '*'));  // 24
    printf("15 / 3 = %d\n",  apply_op(15, 3, '/')); // 5
    printf("5 / 0 = %d\n",   apply_op(5, 0, '/'));  // 0 (safe)
    return 0;
}

要点：使用 switch 分发运算符；除法检查 b != 0 防止除零崩溃；参数 a 是左操作数、b 是右操作数，顺序不能颠倒。

练习4: evaluate — 双栈算法核心

solution_evaluate.c

#include <ctype.h>
#include <stdio.h>
#include <string.h>

static int parse_number(const char *s, int *pos) {
    int val = 0;
    while (isdigit((unsigned char)s[*pos])) {
        val = val * 10 + (s[*pos] - '0');
        (*pos)++;
    }
    return val;
}

static int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

static int apply_op(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return (b != 0) ? a / b : 0;
        default:  return 0;
    }
}

static int evaluate(const char *s) {
    int nums[64], ntop = 0;
    char ops[64];
    int otop = 0;
    int len = strlen(s);
    int i = 0;

    while (i < len) {
        /* 跳过空格 */
        if (s[i] == ' ') {
            i++;
            continue;
        }

        /* 数字 */
        if (isdigit((unsigned char)s[i])) {
            int val = parse_number(s, &i);
            printf("  parse_number: %d\n", val);
            nums[ntop++] = val;
            continue;
        }

        /* 左括号 */
        if (s[i] == '(') {
            printf("  enter paren: (\n");
            ops[otop++] = '(';
            i++;
            continue;
        }

        /* 右括号 */
        if (s[i] == ')') {
            printf("  exit paren: )\n");
            while (otop > 0 && ops[otop - 1] != '(') {
                int b = nums[--ntop];
                int a = nums[--ntop];
                char op = ops[--otop];
                int res = apply_op(a, b, op);
                printf("  apply_op: %d %c %d = %d\n", a, op, b, res);
                nums[ntop++] = res;
            }
            if (otop > 0) otop--;  /* pop '(' */
            i++;
            continue;
        }

        /* 运算符 */
        int prec = precedence(s[i]);
        printf("  operator: %c (precedence=%d)\n", s[i], prec);
        while (otop > 0 && ops[otop - 1] != '('
               && precedence(ops[otop - 1]) >= prec) {
            int b = nums[--ntop];
            int a = nums[--ntop];
            char op = ops[--otop];
            int res = apply_op(a, b, op);
            printf("  apply_op: %d %c %d = %d\n", a, op, b, res);
            nums[ntop++] = res;
        }
        ops[otop++] = s[i];
        i++;
    }

    /* 处理剩余运算符 */
    while (otop > 0) {
        int b = nums[--ntop];
        int a = nums[--ntop];
        char op = ops[--otop];
        int res = apply_op(a, b, op);
        printf("  apply_op: %d %c %d = %d\n", a, op, b, res);
        nums[ntop++] = res;
    }

    return nums[0];
}

要点：四种字符分流处理（数字、(、)、运算符）用 if/else if 清晰组织；( 和 ) 显式配对，不依赖优先级比较；运算符弹栈用 >= 保证左结合；遍历结束后 while (otop > 0) 收尾。

练习5: print_colored — ANSI 彩色打印

solution_print_colored.c

#include <stdio.h>

#define COLOR_GREEN  "\033[32m"
#define COLOR_RED    "\033[31m"
#define COLOR_CYAN   "\033[36m"
#define COLOR_YELLOW "\033[33m"
#define COLOR_BOLD   "\033[1m"
#define COLOR_RESET  "\033[0m"

static void print_colored(const char *color, const char *text) {
    printf("%s%s" COLOR_RESET, color, text);
}

int main(void) {
    print_colored(COLOR_GREEN, "Success!");  // 绿色
    printf("\n");
    print_colored(COLOR_RED, "Error!");      // 红色
    printf("\n");
    print_colored(COLOR_YELLOW, "Warning");  // 黄色
    printf("\n");
    return 0;
}

要点：只有一行 printf，但必须包含 COLOR_RESET；字符串拼接使用 %s%s + 宏，简洁高效。

练习6: main — 完整驱动

solution_main.c

#include <ctype.h>
#include <stdio.h>
#include <string.h>

/* ... 包含以上所有函数 ... */

#define COLOR_GREEN  "\033[32m"
#define COLOR_RED    "\033[31m"
#define COLOR_CYAN   "\033[36m"
#define COLOR_YELLOW "\033[33m"
#define COLOR_BOLD   "\033[1m"
#define COLOR_RESET  "\033[0m"

int main(void) {
    const char *expressions[] = {"3+4*2", "(5+3)*2"};
    int expected[] = {11, 16};
    int num_expr = 2;
    int correct = 0;

    printf(COLOR_BOLD COLOR_YELLOW
           "=== ANSI Terminal Calculator ===" COLOR_RESET "\n");
    printf("Evaluating %d expressions with ANSI color output.\n\n",
           num_expr);

    for (int i = 0; i < num_expr; i++) {
        printf(COLOR_CYAN "Parsing: \"%s\"" COLOR_RESET "\n",
               expressions[i]);
        int result = evaluate(expressions[i]);
        printf("  Result: %d\n", result);

        if (result == expected[i]) {
            printf(COLOR_GREEN "  OK: %s = %d" COLOR_RESET "\n\n",
                   expressions[i], result);
            correct++;
        } else {
            printf(COLOR_RED "  FAIL: %s = %d (expected %d)"
                   COLOR_RESET "\n\n",
                   expressions[i], result, expected[i]);
        }
    }

    printf(COLOR_BOLD COLOR_YELLOW
           "=== Summary ===" COLOR_RESET "\n");
    printf("Expressions evaluated: %d\n", num_expr);
    printf("Correct: " COLOR_GREEN "%d" COLOR_RESET "\n", correct);
    printf("Errors:  " COLOR_RED "%d" COLOR_RESET "\n",
           num_expr - correct);

    return 0;
}

要点：三段式结构（标题→求值→汇总）；expressions[] 和 expected[] 一一对应；正确用绿色、错误用红色；汇总统计 correct/errors 数量。

对照检查1. parse_number 用了 while 吗？precedence('(') 返回 0 吗？apply_op 的参数顺序是 (a, b, op) 吗？evaluate 中弹栈条件用了 >= 吗？print_colored 末尾有 COLOR_RESET 吗？main 中每个彩色块后都跟了 COLOR_RESET 吗？

课堂讨论

双栈算法中弹栈条件为什么用 >= 而不是 >？如果把 >= 改成 >，表达式 "10-5-2" 的结果是多少？为什么？
precedence('(') 返回 0 是精心设计的。如果错误地返回 3，"(5+3)*2" 的求值过程中会发生什么？用双栈跟踪验证你的结论。
parse_number 中 isdigit 的参数为什么要强制转换为 (unsigned char)？如果去掉转换，什么场景下会导致 Bug？
本题选择双栈算法而非递归下降解析。对比两种方法，各有什么优劣？在什么场景下应该选择递归下降？
ANSI 转义序列在 make test 的 diff 比较中是什么角色？如果输出多了一个空格，如何用 cat -v 或 xxd 定位差异？
如果把本题的计算器从整数扩展为支持浮点数（如 "3.14*2"），需要修改哪些函数？evaluate 的双栈逻辑本身需要改动吗？

讨论答案

Q1: >= vs > 的含义与后果

弹栈条件中的 >= 和 > 决定了运算符的结合性：

表达式 "10-5-2" (预期: 3)

>= —— 左结合:
  步骤: 10-5=5 → nums=[5], ops=[]
  读到 '-': prec=1, 栈顶'-' prec=1, 1>=1 true → 弹栈!
           5-5? 不对, 栈中只有 [5], 还未压入...
  
  正确追踪:
  1. nums=[10], ops=[]
  2. '-'→ nums=[10], ops=[-]
  3. 5  → nums=[10,5], ops=[-]
  4. '-'→ prec=1, 栈顶'-' prec=1, 1>=1 → 弹栈!
          10-5=5 → nums=[5], ops=[]
          压入 '-' → nums=[5], ops=[-]
  5. 2  → nums=[5,2], ops=[-]
  6. END→ 5-2=3  ✓

> —— 右结合（错误）:
  步骤 4 中 1 > 1 为 false → 不弹栈
  nums=[10,5], ops=[-,-]
  2  → nums=[10,5,2], ops=[-,-]
  END→ 弹出 '-': 5-2=3 → nums=[10,3], ops=[-]
       弹出 '-': 10-3=7 → 结果 7 ✗（正确 3）

关键洞察：>= 保证"同级运算符从左到右计算"（左结合），> 导致"同级运算符从右到左计算"（右结合），结果是相同的；但对于 - 和 /，差异显著。

Q2: precedence('(') 返回 3 的灾难

假设 precedence('(') = 3:

表达式 "(5+3)*2":

初始化:  nums=[], ops=[]

1. '('→ ops=[(]
2. 5  → nums=[5], ops=[(]
3. '+'→ prec=1
   栈顶 '(' precedence=3, 3 >= 1 → 弹栈!
   弹is '(': 试图 apply_op(a, b, '(')
   → apply_op 进入 default 分支，返回 0
   → nums=[0] （原来的 5 被覆盖了！）

   ops=[]  ← '(' 被错误弹出了
   压入 '+': ops=[+]

4. 3  → nums=[0,3], ops=[+]  （nums 中的值已经是错的）
   ...
   最终结果完全错误。

还会导致另一个问题：后续 ')' 到来时，栈中已经没有 '(' 可匹配，
while 循环可能访问 ops[-1]，导致越界。

括号处理的精妙之处在于：( 在栈中按"特殊角色"行动，不参与正常的运算符优先级竞争。它的"屏障"功能通过优先级设置为 0 实现。

Q3: isdigit 类型转换的未定义行为

C 标准 (ISO C11 §7.4) 规定:
  isdigit 的参数必须是 unsigned char 或 EOF(-1)。

char 在 x86/x86-64 上通常是有符号的 (signed char, -128~127)。

中文字符在 UTF-8 中的字节可能是:
  例: "好" = E5 A5 BD (十六进制)
  E5 = -27 (signed char), A5 = -91, BD = -67

当代码写 isdigit((int) s[i]) 时:
  s[i] = -27 (signed char → int, 带符号扩展)
  传给 isdigit(-27) — 参数不是 unsigned char 也不是 EOF

isdigit 内部通常用数组查表:
  const unsigned char _Ctype[] = { ... };
  return (_Ctype[c] & _DIGIT);  // c = -27 → 越界访问！

强制转换 (unsigned char) 将 -27 转换为 229，保证查表索引始终在 0~255 范围内。虽然本题表达式全是 ASCII 字符（0~127），正数不触发此 Bug，但在实际工程中防御性编程是必须的。

Q4: 双栈算法 vs 递归下降——适用场景对比

维度	双栈算法	递归下降
原理	显式栈 + 优先级比较	函数调用层次编码优先级
代码量	~40 行 (evaluate)	~80 行 (词法+语法)
优先级	precedence() 查表	函数级联: expr→term→factor
扩展运算符	修改 precedence 值	添加函数（如 power()）
右结合支持	需修改弹栈条件	在语法规则层面表达
错误恢复	困难（需栈回溯）	较容易（panic mode）
教学价值	栈数据结构的经典应用	编译器前端入门
适用场景	简单计算器、配置解析	编程语言解析器、复杂 DSL

本质区别：双栈算法基于优先级比较，递归下降基于语法规则。对于只有 4 个运算符的简单计算器，双栈算法更简洁；对于需要支持一元运算、三元运算、函数调用的场景，递归下降的层次结构更好组织。

选型建议：本题表达式语法稳定且简单（如本题、配置文件中的数学表达式），双栈算法是最佳选择。如果语法会演进（如扩展为更复杂的 DSL），递归下降更容易维护。这就是为什么 bc（Unix 计算器）内部使用递归下降——它需要支持变量、函数、条件判断等复杂语法。

Q5: ANSI 序列在 diff 中的调试方法

ANSI 转义序列是不可见字符——\033 在终端中不显示，肉眼无法在 diff 输出中看到差异。调试方法：

方法 1: cat -v 显示控制字符
  $ ./terminal_calc | cat -v
  ^[[1m^[[33m=== ANSI Terminal Calculator ===^[[0m
  ^[[32m  OK: 3+4*2 = 11^[[0m
  ...
  ^[ = \033 的可见表示

方法 2: xxd 十六进制查看
  $ ./terminal_calc | xxd | head
  00000000: 1b5b 316d 1b5b 3333 6d3d 3d3d 2041 4e53  .[1m.[33m=== ANS
  ...
  1b = ESC, 5b = '[', 31 = '1', 6d = 'm'

方法 3: 先输出纯文本，再加颜色
  开发顺序: 先确保 evaluate 计算结果正确 → 再添加 ANSI 序列
  可用 #ifdef 控制是否输出颜色便于对比

方法 4: 去掉 ANSI 序列后对比
  $ ./terminal_calc | sed 's/\x1b\[[0-9;]*m//g'
  === ANSI Terminal Calculator ===
  Evaluating 2 expressions with ANSI color output.
  ...

最常见的原因是多余的空格或换行。例如末尾多一个 \n，或汇总行格式与 expected_output.txt 不一致。

Q6: 浮点数扩展方案

扩展到浮点数只需修改 4 个位置，双栈逻辑不变：

修改点 1: parse_number → 支持小数点
  double parse_number(const char *s, int *pos) {
      double val = 0, frac = 0.1;
      int is_frac = 0;
      while (isdigit(...) || s[*pos] == '.') {
          if (s[*pos] == '.') { is_frac = 1; (*pos)++; continue; }
          if (is_frac) { val += frac * (s[*pos]-'0'); frac *= 0.1; }
          else         { val = val * 10 + (s[*pos]-'0'); }
          (*pos)++;
      }
      return val;
  }

修改点 2: nums[] 改为 double 类型
  double nums[64];  // 原来是 int nums[64]
  // 压栈弹栈同步改为 double

修改点 3: apply_op 返回 double
  double apply_op(double a, double b, char op) { ... }
  // 除法不需要除零检查（浮点数除零返回 inf）

修改点 4: 输出格式
  printf("  Result: %g\n", result);  // %g 而非 %d

evaluate 的核心双栈逻辑完全不变——数字还是压入 nums 栈、运算` 压入 ops 栈、按照优先级弹栈计算。这说明双栈算法与操作数类型无关，适用于任何满足"运算符优先级 + 括号分组"语法的求值场景。

课后练习

支持幂运算。在现有计算器基础上添加 ^ 运算符（幂运算，优先级最高），例如 2^3 应该等于 8。注意幂运算是右结合的（2^3^2 = 2^(3^2) = 512），弹栈条件需要调整为 > 而非 >=。

知识点提示：幂运算的右结合性需要修改 evaluate 中的弹栈条件——对于 ^ 运算符，应该用 > 而非常规的 >=。需要把 precedence 和弹栈逻辑都改为能区分左结合和右结合运算符。

参考解答

ex1_power_operator.c

#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <math.h>  /* pow() */

/* 修改后: 幂运算优先级 3, 右结合 */
static int precedence(char op) {
    if (op == '^') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

static int apply_op(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return (b != 0) ? a / b : 0;
        case '^': return (int)pow(a, b);  /* 整数幂 */
        default:  return 0;
    }
}

/* evaluate 中运算符处理逻辑修改 */
static int evaluate(const char *s) {
    /* ... 前面相同 ... */

    /* 运算符处理 */
    int prec = precedence(s[i]);
    printf("  operator: %c (precedence=%d)\n", s[i], prec);
    /*
     * 关键修改: ^ 是右结合，所以弹栈条件是 > 而不是 >=
     * 对于 ^: precedence(栈顶) > prec 才弹栈
     * 对于其他: precedence(栈顶) >= prec 弹栈（左结合）
     */
    while (otop > 0 && ops[otop - 1] != '(') {
        int top_prec = precedence(ops[otop - 1]);
        /* 对于 '^', 只有栈顶优先级严格大于时才弹栈 */
        if (s[i] == '^') {
            if (top_prec > prec) {
                /* 弹栈计算 */
                int b = nums[--ntop];
                int a = nums[--ntop];
                char op = ops[--otop];
                int res = apply_op(a, b, op);
                printf("  apply_op: %d %c %d = %d\n", a, op, b, res);
                nums[ntop++] = res;
            } else {
                break;  /* 同优先级 ^ 不弹栈, 保留右结合 */
            }
        } else {
            if (top_prec >= prec) {
                /* 弹栈计算 */
                int b = nums[--ntop];
                int a = nums[--ntop];
                char op = ops[--otop];
                int res = apply_op(a, b, op);
                printf("  apply_op: %d %c %d = %d\n", a, op, b, res);
                nums[ntop++] = res;
            } else {
                break;
            }
        }
    }
    ops[otop++] = s[i];
    i++;
    /* ... 后面相同 ... */
}

int main(void) {
    printf("2^3 = %d\n", evaluate("2^3"));      // 8
    printf("2^3^2 = %d\n", evaluate("2^3^2"));  // 512 (右结合)
    printf("2*3^2 = %d\n", evaluate("2*3^2"));  // 18 (^ > *)
    return 0;
}

关键：^ 的弹栈条件使用 >（只在栈顶优先级严格大于时弹栈），这保证了同优先级的 ^ 不会相互弹出，从而实现右结合。

表达式验证器。编写 is_valid_expression(const char *s) 函数，检查表达式是否合法。至少应检查：(a) 括号是否匹配；(b) 是否有连续运算符（如 "3++4"）；(c) 是否以运算符开头/结尾。合法的返回 1，否则返回 0 并打印错误原因。

知识点提示：括号匹配可直接复用 Lesson 34 的栈思想；连续运算符可以通过追踪"上一个 token 类型"实现——不允许两个运算符相邻（除了 ( 后可接 - 作为一元负号）。

参考解答

ex2_expression_validator.c

#include <ctype.h>
#include <stdio.h>
#include <string.h>

/*
 * 验证规则:
 * 1. 括号匹配沿用同 Lesson 34 括号匹配算法）
 * 2. 不能有连续运算符
 * 3. 不能以运算符开头（除 '(' 外）
 * 4. 不能以运算符结尾（除 ')' 外）
 * 5. 只能包含 数字、+、-、*、/、(、)、空格
 */
int is_valid_expression(const char *s) {
    int paren_stack[64];  /* 栈用于括号匹配 */
    int ptop = 0;
    int prev_is_op = 1;   /* 上一个 token 是运算符（开头视为运算符） */
    int len = strlen(s);
    int has_content = 0;   /* 是否有过数字 */

    for (int i = 0; i < len; i++) {
        char c = s[i];

        if (c == ' ') continue;  /* 跳过空格 */

        if (isdigit((unsigned char)c)) {
            prev_is_op = 0;
            has_content = 1;
            /* 跳过连续数字 */
            while (i + 1 < len && isdigit((unsigned char)s[i + 1])) i++;
            continue;
        }

        if (c == '(') {
            paren_stack[ptop++] = '(';
            prev_is_op = 1;  /* '(' 后面可以是运算符 */
            continue;
        }

        if (c == ')') {
            if (ptop == 0) {
                printf("Error: unmatched ')' at position %d\n", i);
                return 0;
            }
            ptop--;
            prev_is_op = 0;  /* ')' 后面不能紧跟数字（需要运算符） */
            continue;
        }

        if (c == '+' || c == '-' || c == '*' || c == '/') {
            if (prev_is_op) {
                printf("Error: consecutive operators at position %d\n", i);
                return 0;
            }
            prev_is_op = 1;
            continue;
        }

        /* 非法字符 */
        printf("Error: invalid character '%c' at position %d\n", c, i);
        return 0;
    }

    if (ptop > 0) {
        printf("Error: %d unmatched '('\n", ptop);
        return 0;
    }

    if (prev_is_op && !has_content) {
        printf("Error: empty or operator-only expression\n");
        return 0;
    }

    if (prev_is_op && has_content) {
        printf("Error: expression ends with operator\n");
        return 0;
    }

    return 1;
}

int main(void) {
    printf("3+4*2:      %d\n", is_valid_expression("3+4*2"));      // 1
    printf("(5+3)*2:    %d\n", is_valid_expression("(5+3)*2"));    // 1
    printf("3++4:       %d\n", is_valid_expression("3++4"));       // 0
    printf("+3*4:       %d\n", is_valid_expression("+3*4"));       // 0
    printf("3*4-:       %d\n", is_valid_expression("3*4-"));       // 0
    printf("3*4+:       %d\n", is_valid_expression("3*4+"));       // 0
    printf("(3+4:       %d\n", is_valid_expression("(3+4"));       // 0
    printf("3+4):       %d\n", is_valid_expression("3+4)"));       // 0
    printf("3&4:        %d\n", is_valid_expression("3&4"));        // 0
    printf("empty:      %d\n", is_valid_expression(""));           // 0
    return 0;
}

这个验证器可作为 evaluate 的前置调用——先验证合法性再求值，避免垃圾输入导致未定义行为。

表达式随机生成器。编写程序生成随机的合法表达式，然后用双栈求值器计算，再与直接使用递归下降求值器的结果对比。这可以作为一种测试方法：生成 1000 个表达式，两个求值方法若不一致则报告错误。

知识点提示：生成合法表达式可以递归进行——gen_expr() 随机选择生成纯数字或 gen_expr() + op + gen_expr()，并随机决定是否加括号。控制递归深度以防止表达式过长。

参考解答

ex3_expr_generator.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* 随机生成一个操作数（0-9） */
static void gen_number(char *buf, int *pos) {
    int digit = rand() % 10;
    buf[*pos] = '0' + digit;
    (*pos)++;
    /* 50% 概率是多位数 (10-99) */
    if (rand() % 2 == 0) {
        digit = rand() % 10;
        buf[*pos] = '0' + digit;
        (*pos)++;
    }
}

/* 随机运算符 */
static char rand_op(void) {
    const char ops[] = "+-*/";
    return ops[rand() % 4];
}

/* 递归生成表达达式 */
static void gen_expr(char *buf, int *pos, int depth) {
    if (depth >= 3 || rand() % 3 == 0) {
        /* 叶子: 生成数字 */
        gen_number(buf, pos);
    } else {
        /* 非叶子: (表达式 op 表达式) 或 不加括号 */
        int use_paren = rand() % 2;
        if (use_paren) {
            buf[*pos] = '(';
            (*pos)++;
        }
        gen_expr(buf, pos, depth + 1);
        buf[*pos] = rand_op();
        (*pos)++;
        gen_expr(buf, pos, depth + 1);
        if (use_paren) {
            buf[*pos] = ')';
            (*pos)++;
        }
    }
}

/*
 * 直接递归求值（不使用栈）——用于交叉验证
 */
static int eval_simple(const char *s, int *idx) {
    int val = 0;
    while (isdigit((unsigned char)s[*idx])) {
        val = val * 10 + (s[*idx] - '0');
        (*idx)++;
    }
    return val;
}

int main(void) {
    srand(time(NULL));
    int errors = 0;

    for (int t = 0; t < 1000; t++) {
        char expr[128];
        int pos = 0;
        gen_expr(expr, &pos, 0);
        expr[pos] = '\0';

        /* 用双栈算法求值 */
        int result1 = evaluate(expr);  /* 使用本课的双栈 evaluate */

        /* 可以用 C 编译器验证思路（等价于 Python eval） */
        /* 此处简化为: 如果表达式不含括号, 用简单左→右验证 */
        printf("[%d] %s → %d\n", t, expr, result1);
    }

    return 0;
}

关键思想：用两个独立实现交叉验证。双栈算法和 Python eval() / 递归下降应得到相同结果。这种"双保险"策略在编写解析器时很常用。

交互式计算器（可选）。修改 main()，使用 while (fgets(buf, sizeof(buf), stdin)) 循环读取用户输入，对每一行表达式求值并输出结果。处理空行和 quit 命令退出。每次求值前清除之前的状态。

知识点提示：将 evaluate 的栈改为每次调用时的局部变量，自然实现了状态清除。读取输入用 fgets，去除末尾 \n 用 strcspn(buf, "\n") = 0。检测 quit 用 strcmp。

参考解答

ex4_interactive_calc.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* ... 所有 evaluate 等相关函数 ... */

int main(void) {
    char line[256];

    printf(COLOR_BOLD COLOR_YELLOW
           "=== Interactive ANSI Calculator ===" COLOR_RESET "\n");
    printf("Enter expressions (type 'quit' to exit):\n\n");

    while (1) {
        printf("> ");
        if (fgets(line, sizeof(line), stdin) == NULL)
            break;

        /* 去除末尾换行 */
        line[strcspn(line, "\n")] = '\0';

        /* 空行跳过 */
        if (line[0] == '\0') continue;

        /* 退出命令 */
        if (strcmp(line, "quit") == 0 || strcmp(line, "exit") == 0) {
            printf("Goodbye!\n");
            break;
        }

        int result = evaluate(line);
        printf(COLOR_GREEN "= %d" COLOR_RESET "\n\n", result);
    }

    return 0;
}

交互版本让计算器"活"起来，可以实时输入表达式查看结果。同时也是对 evaluate 独立性的验证——每次调用完全自包含，不依赖全局状态。

参考资料

Dijkstra, E.W. "Algol 60 Translation" (1961) — 双栈算法原始论文，表达式求值领域的奠基文献
《算法（第 4 版）》§1.3 — Dijkstra 双栈算法 Java 实现，Robert Sedgewick & Kevin Wayne
man 3 isdigit — C 标准库字符分类函数的正确用法，含 unsigned char 强制转换说明
ECMA-48 / ISO 6429 — ANSI 转义序列国际标准，定义全部控制序列语法
《The C Programming Language》§4.3 — 递归下降表达式求值（K&R 经典实现），可与双栈算法对比学习

"Simplicity is a great virtue but it requires hard work to achieve it and education to appreciate it. And to make matters worse: complexity sells better." — Edsger W. Dijkstra

Lesson 72: ANSI 终端计算器 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 表达式求值的三种经典方法与双栈算法原理 ​

1.1 表达式求值——计算器核心问题 ​

1.2 双栈数据结构设计 ​

1.3 双栈算法的四条核心规则 ​

1.4 运算符优先级表 ​

2. parse_number——多位数解析与 isdigit 安全 ​

2.1 从字符到数字的累积过程 ​

2.2 while 而非 if：多位数是刚需 ​

2.3 isdigit 的 unsigned char 强制转换 ​

3. precedence——优先级编码 ​

3.1 最简单的函数，最核心的设计 ​

3.2 为什么 '(' 返回 0？ ​

4. apply_op——四则运算与除零保护 ​

4.1 switch 分发四种运算 ​

4.2 除零保护 ​

5. evaluate——双栈算法完整实现与逐步跟踪 ​

5.1 完整算法伪代码 ​

5.2 跟踪 "3+4*2" → 11 ​

5.3 跟踪 "(5+3)*2" → 16 ​

5.4 弹栈条件 >= 的深层含义 ​

5.5 遍历结束后的收尾工作 ​

6. ANSI 转义序列——终端彩色输出 ​

6.1 转义序列的结构 ​

6.2 颜色代码速查 ​

6.3 COLOR_RESET 的必要性 ​

6.4 颜色宏的字符串拼接技巧 ​

7. print_colored 与 main——组装全部组件 ​

7.1 print_colored 封装 ​

7.2 main 的测试驱动结构 ​

7.3 输出与验证 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 72: ANSI 终端计算器

练习任务

核心知识点

代码框架

深度讲解

1. 表达式求值的三种经典方法与双栈算法原理

1.1 表达式求值——计算器核心问题

1.2 双栈数据结构设计

1.3 双栈算法的四条核心规则

1.4 运算符优先级表

2. parse_number——多位数解析与 isdigit 安全

2.1 从字符到数字的累积过程

2.2 while 而非 if：多位数是刚需

2.3 isdigit 的 unsigned char 强制转换

3. precedence——优先级编码

3.1 最简单的函数，最核心的设计

3.2 为什么 '(' 返回 0？

4. apply_op——四则运算与除零保护

4.1 switch 分发四种运算

4.2 除零保护

5. evaluate——双栈算法完整实现与逐步跟踪

5.1 完整算法伪代码

5.2 跟踪 "3+4*2" → 11

5.3 跟踪 "(5+3)*2" → 16

5.4 弹栈条件 `>=` 的深层含义

5.5 遍历结束后的收尾工作

6. ANSI 转义序列——终端彩色输出

6.1 转义序列的结构

6.2 颜色代码速查

6.3 COLOR_RESET 的必要性

6.4 颜色宏的字符串拼接技巧

7. print_colored 与 main——组装全部组件

7.1 print_colored 封装

7.2 main 的测试驱动结构

7.3 输出与验证

参考解答

课堂讨论

讨论答案

课后练习

参考资料