用c语言给出完整代码 算法设计:设字符串仅有圆括号、方括号、花括号组成,仅能嵌套;使用顺序栈,编写一个算法判断是否匹配。测试“[{{()}[]}(){[ ]}]”,“{}”
时间: 2024-05-15 07:16:09 浏览: 14
以下是使用顺序栈实现括号匹配的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, char c) {
if (is_full(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int is_match(char a, char b) {
if (a == '(' && b == ')') {
return 1;
} else if (a == '[' && b == ']') {
return 1;
} else if (a == '{' && b == '}') {
return 1;
} else {
return 0;
}
}
int is_balanced(char *str) {
Stack s;
init(&s);
int i = 0;
while (str[i] != '\0') {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
push(&s, str[i]);
} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
if (is_empty(&s) || !is_match(pop(&s), str[i])) {
return 0;
}
}
i++;
}
return is_empty(&s);
}
int main() {
char str1[] = "[{{()}[]}(){[ ]}]";
char str2[] = "{}";
if (is_balanced(str1)) {
printf("%s is balanced\n", str1);
} else {
printf("%s is not balanced\n", str1);
}
if (is_balanced(str2)) {
printf("%s is balanced\n", str2);
} else {
printf("%s is not balanced\n", str2);
}
return 0;
}
```
在上面的代码中,我们定义了一个结构体 `Stack` 来表示顺序栈,其中包含一个字符数组 `data` 和一个整型变量 `top`。函数 `init` 用于初始化栈,函数 `is_empty` 和 `is_full` 用于判断栈是否为空或已满,函数 `push` 和 `pop` 用于入栈和出栈操作,函数 `is_match` 用于判断左右括号是否匹配,函数 `is_balanced` 用于判断一个字符串中的括号是否匹配。
在 `main` 函数中,我们定义了两个字符串 `str1` 和 `str2`,分别用于测试括号匹配和不匹配的情况。我们通过调用 `is_balanced` 函数来判断这两个字符串中的括号是否匹配,如果匹配则输出相应的提示信息,否则输出不匹配的信息。
在使用顺序栈实现括号匹配时,我们可以遍历字符串中的每个字符,如果遇到左括号则入栈,如果遇到右括号则出栈并判断是否与左括号匹配。如果在遍历完成后栈为空,则表示括号匹配,否则表示不匹配。在出栈时需要注意栈为空的情况,如果栈为空而又遇到了右括号,则表示不匹配。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)