第29章 字符串的表达式计算：中缀转后缀（逆波兰）与求值

各位同学，今天我们来聊一个经典问题——表达式计算。

说白了，就是给你一个字符串 "3 + 5 * ( 2 - 8 )"，你怎么让计算机算出正确结果？

你可能会说：“这还不简单？从左到右算呗。” 但计算机没你那么聪明。它不知道乘除优先于加减，也不知道括号里的要先算。所以，我们需要一种计算机能“理解”的表达式形式——逆波兰表达式（也叫后缀表达式）。

29.1 为什么需要逆波兰？

我们平时写的表达式叫中缀表达式，比如 3 + 5 * 2。运算符在中间，人看着舒服，但计算机处理起来很麻烦——因为有优先级和括号。

逆波兰表达式把运算符放在操作数后面，比如 3 5 2 * +。这样就不需要括号了，也没有优先级问题。计算机只需要一个栈，遇到数字就压栈，遇到运算符就弹出两个数计算，再把结果压回去。

我个人习惯把逆波兰求值比作“吃豆子”——从左到右吃，遇到数字就存起来，遇到运算符就吐两颗豆子出来算，再吞回去。简单粗暴，但有效。

29.2 中缀转后缀的算法

转换过程需要两个东西：一个输出队列（存放结果），一个运算符栈（临时存放运算符）。

规则如下：

1. 遇到数字，直接输出。
2. 遇到左括号，压入栈。
3. 遇到右括号，不断弹出栈顶运算符并输出，直到遇到左括号（左括号弹出但不输出）。
4. 遇到运算符，如果栈顶运算符优先级 >= 当前运算符，则弹出栈顶并输出，重复直到不满足条件，再把当前运算符压栈。
5. 扫描结束后，把栈里剩余的运算符全部弹出并输出。

嗯，这里要注意：优先级怎么定？一般乘除为2，加减为1，左括号视为0（因为它只在栈里做标记，不参与比较）。

代码示例：中缀转后缀

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

#define MAX 100

// 栈结构
typedef struct {
    char data[MAX];
    int top;
} Stack;

void init(Stack *s) { s->top = -1; }
void push(Stack *s, char c) { s->data[++s->top] = c; }
char pop(Stack *s) { return s->data[s->top--]; }
char peek(Stack *s) { return s->data[s->top]; }
int isEmpty(Stack *s) { return s->top == -1; }

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

// 中缀转后缀
void infixToPostfix(char *infix, char *postfix) {
    Stack s;
    init(&s);
    int j = 0;
    for (int i = 0; infix[i] != '\0'; i++) {
        char c = infix[i];
        if (isdigit(c)) {
            // 处理多位数
            while (isdigit(infix[i])) {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' ';  // 用空格分隔数字
            i--;  // 回退一位
        } else if (c == '(') {
            push(&s, c);
        } else if (c == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[j++] = pop(&s);
                postfix[j++] = ' ';
            }
            pop(&s);  // 弹出 '('
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!isEmpty(&s) && priority(peek(&s)) >= priority(c)) {
                postfix[j++] = pop(&s);
                postfix[j++] = ' ';
            }
            push(&s, c);
        }
    }
    while (!isEmpty(&s)) {
        postfix[j++] = pop(&s);
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
}

这段代码里，我特意用空格分隔数字和运算符。为什么？因为后面求值时，需要按空格拆分。你想想看，如果不加空格，35+ 到底是 3 5 + 还是 35 +？所以，分隔符很重要。

29.3 后缀表达式求值

有了后缀表达式，求值就简单了。还是用栈，不过这次是数字栈。

算法：

1. 从左到右扫描后缀表达式。
2. 遇到数字，压入数字栈。
3. 遇到运算符，弹出两个数字（注意顺序：先弹出的是右操作数，后弹出的是左操作数），计算，结果压回栈。
4. 扫描结束后，栈顶就是最终结果。

代码示例：后缀求值

// 数字栈
typedef struct {
    int data[MAX];
    int top;
} NumStack;

void initNum(NumStack *s) { s->top = -1; }
void pushNum(NumStack *s, int v) { s->data[++s->top] = v; }
int popNum(NumStack *s) { return s->data[s->top--]; }

int evalPostfix(char *postfix) {
    NumStack s;
    initNum(&s);
    char *token = strtok(postfix, " ");
    while (token != NULL) {
        if (isdigit(token[0])) {
            pushNum(&s, atoi(token));
        } else {
            int b = popNum(&s);  // 右操作数
            int a = popNum(&s);  // 左操作数
            switch (token[0]) {
                case '+': pushNum(&s, a + b); break;
                case '-': pushNum(&s, a - b); break;
                case '*': pushNum(&s, a * b); break;
                case '/': pushNum(&s, a / b); break;
            }
        }
        token = strtok(NULL, " ");
    }
    return popNum(&s);
}

这里用了 strtok 按空格拆分，简单高效。但要注意，strtok 会修改原字符串，如果你需要保留原串，记得先拷贝一份。

29.4 完整示例

我们把上面两段代码合起来，测试一下：

int main() {
    char infix[] = "3 + 5 * ( 2 - 8 )";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("中缀: %s\n", infix);
    printf("后缀: %s\n", postfix);
    int result = evalPostfix(postfix);
    printf("结果: %d\n", result);
    return 0;
}

输出：

中缀: 3 + 5 * ( 2 - 8 )
后缀: 3 5 2 8 - * + 
结果: -27

手动验证一下：2 - 8 = -6，5 * (-6) = -30，3 + (-30) = -27。正确！

29.5 避坑指南与个人经验

我在实际项目中用过这个算法好几次，踩过不少坑。这里分享几个：

• 多位数处理：很多初学者只处理个位数，遇到 123 + 456 就崩了。一定要用循环读取连续数字。
• 空格分隔：我一开始没加空格，结果 35+ 被当成 35 和 +，解析出错。后来统一加空格，世界清净了。
• 负数处理：如果表达式里有负数，比如 -3 + 5，需要特殊处理。我一般把负号视为“取负”运算符，或者把 -3 当作 0 - 3 处理。
• 除零检查：这个不用多说，做除法前一定要检查除数是否为0。我曾经在线上环境忘了检查，结果程序直接崩溃，被运维骂了一顿。

29.6 知识结构图

下面我用一张 SVG 图，把本章的核心逻辑串起来：

这张图很直观：中缀表达式先进“转换车间”，变成后缀表达式；再进“求值车间”，得到最终结果。两个车间各有一个栈，各司其职。

29.7 扩展思考

如果你想让程序支持浮点数、幂运算、函数调用（比如 sin、cos），怎么办？

其实思路一样：

• 浮点数：把数字栈类型从 int 改成 double，解析时用 atof。
• 幂运算：给 ^ 一个更高的优先级（比如3），并且注意它是右结合的（2^3^2 等于 2^(3^2)）。
• 函数：把函数名当作运算符，遇到时压栈，遇到右括号时弹出计算。

嗯，这些扩展留给你自己去尝试。代码是死的，思路是活的。你只要掌握了栈的“压弹”哲学，就能应对各种变体。

---

好了，这一章就到这里。表达式计算是字符串处理的经典应用，也是很多面试题的常客。希望你能亲手写一遍代码，把坑踩一遍，才能真正掌握。