c语言实现括号匹配问题
时间: 2023-10-13 14:06:42 浏览: 96
括号匹配问题是指在一个字符串中,是否所有的括号都可以正确地匹配。例如,字符串”( )”是匹配的,而字符串”( ) )”是不匹配的。
下面是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100 // 定义最大字符串长度
typedef struct {
char data[MAX_SIZE];
int top;
} Stack; // 定义栈结构体
void InitStack(Stack *stack) {
stack->top = -1;
} // 初始化栈
int IsEmpty(Stack *stack) {
return stack->top == -1;
} // 判断栈是否为空
int IsFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
} // 判断栈是否已满
void Push(Stack *stack, char ch) {
if (IsFull(stack)) {
printf("Stack is full\n");
exit(1);
}
stack->data[++stack->top] = ch;
} // 入栈
char Pop(Stack *stack) {
if (IsEmpty(stack)) {
printf("Stack is empty\n");
exit(1);
}
return stack->data[stack->top--];
} // 出栈
int Match(char left, char right) {
if (left == '(' && right == ')')
return 1;
else if (left == '[' && right == ']')
return 1;
else if (left == '{' && right == '}')
return 1;
else
return 0;
} // 判断左右括号是否匹配
int IsBalanced(char *str) {
Stack stack;
InitStack(&stack); // 初始化栈
int len = strlen(str);
for (int i = 0; i < len; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{')
Push(&stack, str[i]); // 左括号入栈
else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
if (IsEmpty(&stack) || !Match(Pop(&stack), str[i]))
return 0; // 栈为空或左右括号不匹配,返回0
}
}
return IsEmpty(&stack); // 栈为空则匹配成功
}
int main() {
char str[MAX_SIZE];
printf("请输入一个字符串:");
scanf("%s", str);
if (IsBalanced(str))
printf("该字符串括号匹配成功\n");
else
printf("该字符串括号匹配失败\n");
return 0;
}
```
该实现中使用了一个栈来存储左括号,并在遇到右括号时弹出栈顶元素进行匹配。如果匹配成功,则继续扫描字符串;否则,说明括号匹配失败。如果扫描完字符串后,栈为空,则说明括号匹配成功。