栈在括号匹配中的应用(栈/链栈 纯C实现)

目录

1 问题背景

2 具体思路

3 代码实现

3.1 顺序栈实现

3.2 链栈实现

---

1 问题背景

  栈的括号匹配问题是指在给定一个字符串（包含多种括号），判断其中的括号是否能够正确匹配，即每个左括号是否有一个对应的右括号与之匹配，并且左右括号必须以正确的顺序进行匹配。

例如，字符串"((()))"中的括号就能够正确匹配，而字符串"()())"中的括号就无法正确匹配。

 

2 具体思路

这是王道给出的流程图：

图1 王道给出的流程图

 

看起来有点吃力，我来总结一下，很简单，就几步：

1. 遍历给定的字符串，对于每个字符进行判断。
2. 如果字符是左括号，将其入栈。
3. 如果字符是右括号，将其与栈顶元素作比较，判断该元素是否是与之匹配的左括号。如果是，弹出栈顶元素，并继续遍历；如果不是，说明括号不匹配，返回false。
4. 如果字符串遍历完毕，栈为空，则说明全部括号匹配，返回true；否则，返回false。

注意如果在准备弹出元素时发现栈已为空，说明前面没有左括号与该右括号匹配，返回false。

3 代码实现

以Acwing上一道例题举例：3693. 括号匹配 - AcWing题库

输入格式

共一行，包含一个由 `<`,`(`,`{`,`[`,`>`,`)`,`}`,`]` 构成的字符串。

输出格式

如果输入的字符串中的括号正确匹配则输出 `yes`，否则输出 `no`。

数据范围

输入字符串长度不超过 10000。

输入样例：

    (){}

输出样例：

    yes

 

3.1 顺序栈实现

#include<stdio.h>
#include<string.h>
#include<stdbool.h>    //C语言引入该库才有bool值#define MAX_SIZE 100000  //定义栈中元素的最大个数typedef struct {int data[MAX_SIZE];  //静态数组存放栈中元素int top;    //栈顶指针
} SqStack;//初始化栈
void initStack(SqStack *s) {s->top = -1;
}//判断栈空
bool stackEmpty(SqStack s) {return s.top == -1;  //如果栈是空的，那么就会返回true
}//新元素入栈
bool push(SqStack *s, int x) {if (s->top == MAX_SIZE - 1) //如果栈已满，返回falsereturn false;s->data[++(s->top)] = x;  //否则先将栈顶指针的值加1，然后再使用增加后的栈顶指针指向的位置作为数组下标，将x存储到data数组中return true;
}//出栈
bool pop(SqStack *s, int *x) {if (s->top == -1) { //因为栈已空，再出栈报错返回falsereturn false;}*x = s->data[s->top--]; //从栈顶取出一个元素并赋值给x*，然后将栈顶指针减1，即把栈顶指针指向它下方的元素/*为什么给x*呢？因为需要通过指针参数才能把栈的元素值传递出去，进而传给topElem*/return true;
}//括号匹配算法的主体
bool bracketCheck(char str[]) {SqStack s;    initStack(&s);for (int i = 0; i < strlen(str); i++) {if (str[i] == '<' || str[i] == '(' || str[i] == '{' || str[i] == '[') {push(&s, str[i]);} else {if (stackEmpty(s)) {return false;}int topElem;  //topElem作为中间变量，记录从栈中弹出的栈顶元素if (!pop(&s, &topElem)) { //如果取出栈顶元素失败，说明栈为空，则匹配失败，返回falsereturn false;}if (str[i] == '>' && topElem != '<') {return false;}if (str[i] == ')' && topElem != '(') {return false;}if (str[i] == ']' && topElem != '[') {return false;}if (str[i] == '}' && topElem != '{') {return false;}}}return stackEmpty(s); //栈空，说明所有括号都能匹配成功，返回true；否则说明还有没配成功的括号，返回false
}int main() {char str[MAX_SIZE];  //接收字符串scanf("%s", str);if (bracketCheck(str)) printf("yes");else printf("no");return 0;
}

3.2 链栈实现

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;typedef struct {Node* top;int count;
} LinkedStack;// 初始化链栈
void InitStack(LinkedStack* S) {S->top = NULL;S->count = 0;
}// 判断栈空
bool StackEmpty(LinkedStack* S) {return S->count == 0;
}// 新元素入栈
bool Push(LinkedStack* S, int x) {Node* node = (Node*)malloc(sizeof(Node));if (node == NULL) {return false;  // 内存分配失败，入栈失败}node->data = x;node->next = S->top;S->top = node;S->count++;return true;
}// 弹出栈顶元素
bool Pop(LinkedStack* S, int* x) {if (StackEmpty(S)) {return false;  // 栈空，弹出失败}Node* node = S->top;S->top = node->next;*x = node->data;free(node);S->count--;return true;
}// 读取栈顶元素
bool GetTop(LinkedStack* S, int* x) {if (StackEmpty(S)) {return false;  // 栈空，读取失败}*x = S->top->data;return true;
}// 括号匹配检查
bool bracketCheck(char str[]) {LinkedStack S;InitStack(&S);for (int i = 0; i < strlen(str); i++) {if (str[i] == '<' || str[i] == '(' || str[i] == '{' || str[i] == '[') {Push(&S, str[i]);} else {if (StackEmpty(&S)) {return false;  // 栈空，匹配失败}int topElem;if (!Pop(&S, &topElem)) {return false;  // 弹出失败，匹配失败}if (str[i] == '>' && topElem != '<') {return false;  // 匹配失败}if (str[i] == ')' && topElem != '(') {return false;  // 匹配失败}if (str[i] == ']' && topElem != '[') {return false;  // 匹配失败}if (str[i] == '}' && topElem != '{') {return false;  // 匹配失败}}}return StackEmpty(&S);
}int main() {char str[100000];scanf("%s", str);if (bracketCheck(str)) {printf("yes\n");} else {printf("no\n");}return 0;
}