设计一个算法,判断一个可能含有花括号、中括号、和圆括号的表达式中各类括号是否匹配,若匹配,则返回1;否则返回0。其中表达式只包含三种括号,花括号{}、中括号[]、圆括号(),即它仅由 (、)、[、]、{、}六个字符组成。用C语言编写代码
时间: 2023-10-30 21:13:05 浏览: 96
可以使用栈(stack)来解决这个问题。遍历表达式中的每个字符,如果是左括号,则将其入栈。如果是右括号,则将栈顶元素出栈并判断是否与当前右括号匹配,若不匹配,则返回0;否则继续遍历。最后如果栈为空,则说明所有括号都匹配,返回1;否则返回0。
以下是具体实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 100
typedef struct {
char data[MAX_LEN];
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_LEN - 1;
}
void push(Stack *s, char c) {
if (isFull(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int match(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) || !match(pop(&s), exp[i])) {
return 0;
}
}
}
return isEmpty(&s);
}
int main() {
char exp[MAX_LEN];
printf("Enter an expression: ");
scanf("%s", exp);
if (isBalanced(exp)) {
printf("The expression is balanced\n");
} else {
printf("The expression is not balanced\n");
}
return 0;
}
```
测试代码:
```
Enter an expression: {[()]}
The expression is balanced
Enter an expression: {[(])}
The expression is not balanced
```