第九章：栈的应用（一）——括号匹配与表达式求值

栈这个东西，别看它结构简单——先进后出，就四个字。但实际用起来，威力大得很。我做了这么多年嵌入式开发，栈用得最多的场景，就是括号匹配和表达式求值。今天咱们就把这两个经典问题彻底讲透。

9.1 括号匹配问题

先问个问题：你写代码的时候，有没有遇到过括号不匹配的编译错误？编译器是怎么知道你少写了一个 '}' 的？

说白了，就是靠栈。

9.1.1 算法思路

括号匹配的规则很简单：

• 遇到左括号（'('、'['、'{'），就压入栈
• 遇到右括号（')'、']'、'}'），就从栈顶弹出一个左括号，检查是否匹配
• 如果栈为空时遇到右括号，或者遍历完栈不为空，说明不匹配

嗯，这里要注意：匹配不只是数量相等，类型也要对上。'(' 不能匹配 ']'，这是常识。

9.1.2 代码实现

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

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool push(Stack *s, char ch) {
    if (s->top == MAX_SIZE - 1) return false;
    s->data[++s->top] = ch;
    return true;
}

char pop(Stack *s) {
    if (s->top == -1) return '\0';
    return s->data[s->top--];
}

char peek(Stack *s) {
    if (s->top == -1) return '\0';
    return s->data[s->top];
}

bool isMatching(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

bool checkBrackets(const char *expr) {
    Stack s;
    initStack(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        
        if (ch == '(' || ch == '[' || ch == '{') {
            push(&s, ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (s.top == -1) {
                printf("错误：位置 %d 处多余的右括号 '%c'\n", i, ch);
                return false;
            }
            char left = pop(&s);
            if (!isMatching(left, ch)) {
                printf("错误：位置 %d 处括号不匹配，期望 '%c'，实际 '%c'\n", 
                       i, getMatchingChar(left), ch);
                return false;
            }
        }
    }
    
    if (s.top != -1) {
        printf("错误：有 %d 个左括号未匹配\n", s.top + 1);
        return false;
    }
    
    return true;
}

9.2 表达式求值：中缀转后缀

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

后缀表达式（也叫逆波兰表达式）就不一样了，它把运算符放在后面，比如 "3 5 2 * +"。计算机处理后缀表达式，只需要一个栈，从左到右扫一遍就行，不需要考虑优先级。

9.2.1 转换规则

中缀转后缀的算法，我习惯用「运算符栈法」。规则如下：

1. 遇到操作数（数字），直接输出
2. 遇到左括号 '('，压入栈
3. 遇到右括号 ')'，不断弹出栈顶运算符并输出，直到遇到 '('，然后丢弃 '('
4. 遇到运算符（+、-、*、/），如果栈顶运算符优先级 >= 当前运算符，则弹出并输出，重复直到不满足条件，然后压入当前运算符
5. 遍历完后，将栈中剩余运算符全部弹出并输出

9.2.2 代码实现

int getPriority(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

void infixToPostfix(const char *infix, char *postfix) {
    Stack s;
    initStack(&s);
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        
        // 跳过空格
        if (ch == ' ') continue;
        
        // 如果是数字，直接输出
        if (ch >= '0' && ch <= '9') {
            postfix[j++] = ch;
            postfix[j++] = ' ';
        } else if (ch == '(') {
            push(&s, ch);
        } else if (ch == ')') {
            while (s.top != -1 && peek(&s) != '(') {
                postfix[j++] = pop(&s);
                postfix[j++] = ' ';
            }
            pop(&s); // 弹出 '('
        } else {
            // 运算符
            while (s.top != -1 && getPriority(peek(&s)) >= getPriority(ch)) {
                postfix[j++] = pop(&s);
                postfix[j++] = ' ';
            }
            push(&s, ch);
        }
    }
    
    // 弹出剩余运算符
    while (s.top != -1) {
        postfix[j++] = pop(&s);
        postfix[j++] = ' ';
    }
    postfix[j] = '\0';
}

9.3 后缀表达式计算

后缀表达式计算就简单多了。只需要一个操作数栈：

1. 遇到数字，压入栈
2. 遇到运算符，弹出两个操作数，计算结果，再压回栈
3. 遍历完后，栈顶就是最终结果

注意顺序：对于减法和除法，先弹出的是右操作数，后弹出的是左操作数。这个顺序搞反了，结果就错了。

int evaluatePostfix(const char *postfix) {
    Stack s;
    initStack(&s);
    
    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];
        
        if (ch == ' ') continue;
        
        if (ch >= '0' && ch <= '9') {
            // 处理多位数
            int num = 0;
            while (ch >= '0' && ch <= '9') {
                num = num * 10 + (ch - '0');
                ch = postfix[++i];
            }
            push(&s, num);
            i--; // 回退一步
        } else {
            int b = pop(&s); // 右操作数
            int a = pop(&s); // 左操作数
            int result;
            
            switch (ch) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': 
                    if (b == 0) {
                        printf("错误：除零\n");
                        return 0;
                    }
                    result = a / b; 
                    break;
                default:
                    printf("错误：未知运算符 '%c'\n", ch);
                    return 0;
            }
            push(&s, result);
        }
    }
    
    return pop(&s);
}

9.4 完整示例

咱们跑一个完整的例子，看看效果：

int main() {
    char infix[] = "3 + 5 * ( 2 - 8 ) / 4";
    char postfix[100];
    
    printf("中缀表达式: %s\n", infix);
    
    infixToPostfix(infix, postfix);
    printf("后缀表达式: %s\n", postfix);
    
    int result = evaluatePostfix(postfix);
    printf("计算结果: %d\n", result);
    
    return 0;
}

// 输出：
// 中缀表达式: 3 + 5 * ( 2 - 8 ) / 4
// 后缀表达式: 3 5 2 8 - * 4 / + 
// 计算结果: -4

手动验证一下：3 + 5 * (2 - 8) / 4 = 3 + 5 * (-6) / 4 = 3 + (-30) / 4 = 3 + (-7) = -4。嗯，没问题。

9.5 知识体系总览

下面这张图，把本章的核心逻辑串起来了：

括号匹配、中缀转后缀、后缀计算，这三个问题看似独立，其实底层都依赖同一个数据结构——栈。你想想看，是不是很有意思？

---

公众号:蓝海资料掘金营，微信deep3321