假设表达式中允许包含圆括号、方括号和大括号3中括号,用C语言编写一个算法判断表达式中括号是否正确配对。
时间: 2024-06-12 15:11:18 浏览: 105
这里提供一个基于顺序栈的C语言算法来判断表达式中的括号是否正确配对:
1. 定义一个栈结构体,包含一个数组和一个栈顶指针top。
2. 遍历表达式中的每个字符,如果是左括号(圆括号、方括号或大括号),则将其入栈;如果是右括号,则判断栈顶元素是否与其匹配,如果匹配则将栈顶元素出栈,否则返回错误。
3. 遍历完整个表达式后,如果栈为空,则说明所有括号都正确匹配,否则返回错误。
4. 最后返回正确或错误的结果。
下面是代码实现:
```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;
}
void push(Stack *s, char c) {
if (s->top == MAX_SIZE - 1) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (s->top == -1) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_match(char left, char right) {
return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}
int is_balanced(char *expr) {
Stack s;
init(&s);
for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') {
push(&s, expr[i]);
} else if (expr[i] == ')' || expr[i] == ']' || expr[i] == '}') {
if (is_empty(&s) || !is_match(pop(&s), expr[i])) {
return 0;
}
}
}
return is_empty(&s);
}
int main() {
char expr[MAX_SIZE];
printf("Enter an expression: ");
scanf("%s", expr);
if (is_balanced(expr)) {
printf("The expression is balanced\n");
} else {
printf("The expression is not balanced\n");
}
return 0;
}
```
阅读全文