当前位置：首页 > news >正文

从括号匹配看栈：数据结构入门的实战与原理

news 2025/5/4 20:12:47

在计算机科学的世界里，数据结构是程序员的 “瑞士军刀”，不同的数据结构适用于不同的场景，能高效解决各类问题。其中，栈作为一种简单却强大的数据结构，在很多实际应用中发挥着关键作用。今天，我们就通过一个经典的问题 —— 括号匹配，来深入理解栈的原理与应用。

一、认识栈：后进先出的 “数据仓库”

栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构。就像一叠盘子，我们只能从最上面取盘子，也只能把新盘子放到最上面。在栈中，新元素的添加（进栈，Push）和已有元素的移除（出栈，Pop）都只能在一端进行，这一端被称为栈顶（Top）。

二、栈的基本操作：搭建数据处理的 “脚手架”

#include <stdio.h>
#define MaxSize 100
typedef char ElemType;// 定义栈结构体
typedef struct stack {ElemType elem[MaxSize];  // 存储栈元素的数组int top;                 // 栈顶指针
} *Sqstacktp, Sqstack;// 初始化栈
void InitSqstack(Sqstacktp s) {s->top = 0;  // 栈顶指针初始化为 0，表示栈为空
}// 进栈操作
void Push(Sqstacktp s, ElemType x) {if (s->top == MaxSize) {  // 判断栈是否已满printf("Overflow\n");  // 栈满则输出溢出信息} else {s->elem[s->top] = x;  // 将元素 x 放入栈顶位置s->top++;             // 栈顶指针加 1}
}// 出栈操作
ElemType Pop(Sqstacktp s) {if (s->top == 0) {  // 判断栈是否为空return '\0';    // 栈空则返回空字符} else {s->top--;              // 栈顶指针减 1return s->elem[s->top];// 返回栈顶元素}
}// 读栈顶元素
ElemType GetSqstacktop(Sqstacktp s) {if (s->top == 0) {  // 判断栈是否为空return '\0';    // 栈空则返回空字符} else {return s->elem[s->top - 1];  // 返回栈顶元素}
}// 判断括号是否匹配函数
void match() {Sqstack s;char ch;int flag = 1;  // 用于标记括号是否匹配，初始化为 1 表示匹配InitSqstack(&s);  // 初始化栈printf("请输入一个带括号的算术表达式: ");while ((ch = getchar()) != '\n') {  // 逐个读取输入的字符，直到换行符if (ch == ')' || ch == ']' || ch == '}') {  // 遇到右括号if (GetSqstacktop(&s) == '(' && ch == ')') {  // 判断栈顶左括号是否匹配Pop(&s);  // 匹配则出栈} else if (GetSqstacktop(&s) == '[' && ch == ']') {Pop(&s);} else if (GetSqstacktop(&s) == '{' && ch == '}') {Pop(&s);} else {flag = 0;  // 不匹配则标记为不匹配}}if (ch == '(' || ch == '[' || ch == '{') {  // 遇到左括号Push(&s, ch);  // 左括号进栈}}if (s.top == 0 && flag) {  // 栈为空且标记为匹配printf("表达式括号匹配\n");} else {printf("表达式括号不匹配\n");}
}int main() {match();return 0;
}

三、括号匹配：栈的经典应用场景

括号匹配问题是栈的典型应用之一。在编程语言中，括号必须正确配对，否则代码会出现语法错误。例如，{}、[]、() 必须成对出现，并且嵌套顺序要正确。利用栈的后进先出特性，我们可以轻松解决这个问题。

在 match 函数中，我们首先初始化一个栈和一个标记变量 flag。然后，逐个读取输入的字符：