数据结构C语言代码用栈实现括号匹配
时间: 2024-05-17 19:09:21 浏览: 22
栈是一种常用的数据结构,可以用来实现括号匹配。下面是一个使用C语言代码实现栈来进行括号匹配的示例:
```c
#include <stdio.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 isEmpty(Stack *s) {
return s->top == -1;
}
// 判断栈是否已满
bool isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack *s, char c) {
if (isFull(s)) {
printf("Stack is full.\n");
return;
}
s->data[++(s->top)] = c;
}
// 出栈
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return '\0';
}
return s->data[(s->top)--];
}
// 括号匹配函数
bool isParenthesesMatch(char *str) {
Stack s;
initStack(&s);
for (int i = 0; str[i] != '\0'; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
push(&s, str[i]);
} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
if (isEmpty(&s)) {
return false;
}
char top = pop(&s);
if ((str[i] == ')' && top != '(') ||
(str[i] == ']' && top != '[') ||
(str[i] == '}' && top != '{')) {
return false;
}
}
}
return isEmpty(&s);
}
int main() {
char str[MAX_SIZE];
printf("请输入括号序列:");
scanf("%s", str);
if (isParenthesesMatch(str)) {
printf("括号匹配成功!\n");
} else {
printf("括号匹配失败!\n");
}
return 0;
}
```
这段代码中,我们使用一个字符数组来存储输入的括号序列,然后通过遍历序列中的每个字符,将左括号入栈,遇到右括号时与栈顶元素进行匹配。如果匹配成功,则继续遍历;如果匹配失败或者栈为空,则括号匹配失败。最后判断栈是否为空,如果为空则括号匹配成功,否则匹配失败。