基于链栈的括号匹配。
时间: 2024-06-12 07:08:26 浏览: 20
基于链栈的括号匹配是一种常见的算法,用于判断一个表达式中的括号是否匹配。首先,我们需要定义一个栈数据结构来存储左括号。然后,遍历表达式中的每个字符,如果遇到左括号,则将其推入栈中;如果遇到右括号,则检查栈顶元素是否与当前右括号匹配,如果匹配则将栈顶元素出栈,继续遍历后续字符;如果不匹配,则说明括号不配对,返回错误信息。最后,检查栈是否为空,如果为空则表示所有的左括号都有与之匹配的右括号,反之则说明某个左括号缺少匹配的右括号。
代码示例:
```
typedef struct {
char data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
void initStack(Stack *s) {
s->top = NULL;
}
void push(Stack *s, char ch) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = ch;
node->next = s->top;
s->top = node;
}
char pop(Stack *s) {
if (s->top == NULL) {
return '\0';
}
char ch = s->top->data;
Node *temp = s->top;
s->top = s->top->next;
free(temp);
return ch;
}
int isMatching(char left, char right) {
if (left == '(' && right == ')') {
return 1;
} else if (left == '[' && right == ']') {
return 1;
} else if (left == '{' && right == '}') {
return 1;
}
return 0;
}
int isBalanced(char *exp) {
Stack s;
initStack(&s);
char ch;
int i = 0;
while ((ch = exp[i++]) != '\0') {
if (ch == '(' || ch == '[' || ch == '{') {
push(&s, ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
if (s.top == NULL) {
return 0;
} else if (!isMatching(pop(&s), ch)) {
return 0;
}
}
}
return s.top == NULL;
}
int main() {
char exp[100];
printf("请输入带括号的表达式('{}','[]','()'): ");
gets(exp);
if (isBalanced(exp)) {
printf("括号匹配\n");
} else {
printf("括号不匹配\n");
}
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)