使用C语言设计一个算法,判断一个可能含有小括号('('与')')、中括号('['与']')和大括号('{'与'}')的表达式中各类括号是否匹配。若匹配,则返回1;否则返回0。。
时间: 2023-08-07 17:07:31 浏览: 75
可以使用栈(stack)数据结构来实现括号匹配的判断。具体算法如下:
1. 创建一个栈,用于存储左括号。
2. 遍历表达式中的每个字符。
3. 如果当前字符是左括号('('、'['、'{'),则将其压入栈中。
4. 如果当前字符是右括号(')'、']'、'}'),则弹出栈顶元素,并判断其是否为相应的左括号。如果不是,则表达式中的括号不匹配,返回0。
5. 如果遍历完整个表达式后,栈为空,则表达式中的括号匹配,返回1;否则不匹配,返回0。
下面是相应的C代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack *s, char c) {
if (isFull(s)) {
printf("Error: Stack is full!\n");
exit(1);
}
s->data[++s->top] = c;
}
// 出栈
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Error: Stack is empty!\n");
exit(1);
}
return s->data[s->top--];
}
// 判断括号是否匹配
int isMatch(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
int isBalanced(char *exp) {
Stack s;
initStack(&s);
for (int i = 0; exp[i] != '\0'; i++) {
if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
push(&s, exp[i]);
} else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
if (isEmpty(&s) || !isMatch(pop(&s), exp[i])) {
return 0;
}
}
}
return isEmpty(&s);
}
int main() {
char exp[MAX_SIZE];
printf("Enter an expression: ");
scanf("%s", exp);
printf("%s\n", isBalanced(exp) ? "Balanced" : "Not balanced");
return 0;
}
```