9. 栈的应用：递归的实现原理、栈在括号匹配中的应用、栈在表达式求值中的应用

栈这个数据结构，别看它结构简单——就一个后进先出（LIFO）的线性表，但它的应用场景比你想象的多得多。我个人习惯把栈比作一个「弹夹」，你压进去的子弹，最后压进去的会最先被打出去。这个特性，恰好和计算机世界里很多问题的处理逻辑不谋而合。

今天我们就来聊聊栈的三个经典应用：递归的实现原理、括号匹配、以及表达式求值。这三个场景，我在实际项目中都踩过坑，也从中总结了一些经验，分享给你。

9.1 递归的实现原理：栈是幕后功臣

很多初学者觉得递归很玄乎，函数调用自己，怎么就能正常工作？其实，递归的底层依赖的就是栈。每次函数调用，系统都会在内存中开辟一块区域，叫「函数调用栈」。这块区域会记录函数的返回地址、局部变量、参数等信息。

我刚开始学递归时，总觉得它是个黑魔法。直到有一次我手写了一个深度递归的斐波那契数列，结果程序直接崩溃了——栈溢出了。嗯，从那以后我才真正理解了栈的容量是有限的。

来看一个简单的例子：计算阶乘 n!。

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;  // 终止条件
    }
    return n * factorial(n - 1);  // 递归调用
}

int main() {
    int result = factorial(5);
    printf("5! = %d\n", result);
    return 0;
}

当调用 factorial(5) 时，栈的变化是这样的：

调用顺序	栈帧内容	栈状态（从底到顶）
1	factorial(5) 等待 factorial(4) 返回	[factorial(5)]
2	factorial(4) 等待 factorial(3) 返回	[factorial(5), factorial(4)]
3	factorial(3) 等待 factorial(2) 返回	[factorial(5), factorial(4), factorial(3)]
4	factorial(2) 等待 factorial(1) 返回	[factorial(5), factorial(4), factorial(3), factorial(2)]
5	factorial(1) 返回 1	[factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
6	factorial(2) 得到 2*1=2，返回	[factorial(5), factorial(4), factorial(3)]
7	factorial(3) 得到 3*2=6，返回	[factorial(5), factorial(4)]
8	factorial(4) 得到 4*6=24，返回	[factorial(5)]
9	factorial(5) 得到 5*24=120，返回	[]

9.2 栈在括号匹配中的应用

括号匹配是栈的经典应用之一。你想想看，编译器在解析代码时，怎么知道你的括号有没有配对？其实原理很简单：遇到左括号就压栈，遇到右括号就弹栈并检查是否匹配。

我在做代码编辑器插件时，就实现过这个功能。当时用户输入一个括号，编辑器要实时高亮匹配的括号。如果匹配不上，就标红提示。这个功能的核心逻辑，就是栈。

算法思路：

1. 遍历字符串中的每个字符
2. 如果是左括号（'('、'['、'{'），压入栈
3. 如果是右括号（')'、']'、'}'），检查栈顶是否是对应的左括号
   • 如果匹配，弹出栈顶
   • 如果不匹配或栈为空，说明括号不匹配
4. 遍历结束后，如果栈为空，说明所有括号都匹配；否则不匹配

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

#define MAX_SIZE 100

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

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

bool isEmpty(Stack *s) {
    return s->top == -1;
}

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

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

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

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

bool checkBrackets(char *expr) {
    Stack s;
    init(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&s, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&s) || !isMatching(pop(&s), c)) {
                return false;
            }
        }
    }
    return isEmpty(&s);
}

int main() {
    char expr1[] = "{[()]}";
    char expr2[] = "{[(])}";
    
    printf("表达式 %s : %s\n", expr1, checkBrackets(expr1) ? "匹配" : "不匹配");
    printf("表达式 %s : %s\n", expr2, checkBrackets(expr2) ? "匹配" : "不匹配");
    
    return 0;
}

9.3 栈在表达式求值中的应用

表达式求值，说白了就是让计算机理解并计算你写的数学表达式。比如你输入 "3 + 5 * 2"，计算机怎么知道要先算乘法再算加法？这里就需要用到栈了。

表达式有三种形式：中缀、前缀和后缀。我们平时写的是中缀表达式（运算符在中间），但计算机更容易处理后缀表达式（运算符在后面）。所以求值过程分两步：中缀转后缀，然后计算后缀表达式。

我记得有一次在嵌入式项目中，需要实现一个简单的计算器功能。芯片资源有限，不能直接用浮点运算库。我就用栈实现了整数表达式的求值，效果还不错。

9.3.1 中缀表达式转后缀表达式

转换规则：

• 遇到操作数，直接输出
• 遇到左括号，压栈
• 遇到右括号，弹出栈中运算符直到遇到左括号
• 遇到运算符，弹出栈中优先级高于或等于当前运算符的运算符，然后当前运算符压栈
• 遍历结束后，弹出栈中所有运算符

举个例子：中缀表达式 "3 + 5 * 2" 转后缀的过程：

步骤	当前字符	输出	栈
1	3	3	空
2	+	3	+
3	5	3 5	+
4	*	3 5	+ *
5	2	3 5 2	+ *
6	结束	3 5 2 * +	空

最终后缀表达式为 "3 5 2 * +"。

9.3.2 后缀表达式求值

计算后缀表达式就简单了：

• 遇到操作数，压栈
• 遇到运算符，弹出两个操作数，计算结果，再压栈
• 遍历结束后，栈顶就是结果

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

#define MAX 100

typedef struct {
    int data[MAX];
    int top;
} IntStack;

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

int evalPostfix(char *expr) {
    IntStack s;
    init(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == ' ') continue;
        
        if (isdigit(c)) {
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;  // 回退一步
            push(&s, num);
        } else {
            int b = pop(&s);
            int a = pop(&s);
            switch (c) {
                case '+': push(&s, a + b); break;
                case '-': push(&s, a - b); break;
                case '*': push(&s, a * b); break;
                case '/': push(&s, a / b); break;
            }
        }
    }
    return pop(&s);
}

int main() {
    char expr[] = "3 5 2 * +";
    printf("后缀表达式 %s = %d\n", expr, evalPostfix(expr));
    return 0;
}

9.4 知识体系总览

为了让你更直观地理解栈在这三个应用中的关系，我画了一张图：

从这张图可以看出，栈的核心思想——后进先出，恰好能完美匹配嵌套结构。无论是递归的层层调用、括号的嵌套匹配、还是表达式的优先级处理，本质上都是在处理「先遇到的后处理，后遇到的先处理」这种逻辑。

---

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