设计一个算法,判断一个可能含有小括号 51与))、中括号(T与)和大括号 (g与列)的表达式中各类括号是否匹配。 若匹配,则返回1;否则返回0。用c语言写
时间: 2024-04-30 21:18:23 浏览: 132
以下是一个使用栈的算法,可以判断表达式中的括号是否匹配。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.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)) {
fprintf(stderr, "Stack is full\n");
exit(1);
}
s->data[++(s->top)] = c;
}
char pop(Stack* s) {
if (is_empty(s)) {
fprintf(stderr, "Stack is empty\n");
exit(1);
}
return s->data[(s->top)--];
}
int is_match(char left, char right) {
switch (left) {
case '(':
return right == ')';
case '[':
return right == ']';
case '{':
return right == '}';
default:
return 0;
}
}
int check_expression(char* expr) {
Stack s;
init(&s);
for (int i = 0; i < strlen(expr); ++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[] = "((a+b)*c)-{d+e}";
if (check_expression(expr)) {
printf("Expression is valid\n");
} else {
printf("Expression is invalid\n");
}
return 0;
}
```
该算法使用栈来保存左括号,当遇到右括号时,从栈中弹出一个左括号进行匹配。如果栈为空或者弹出来的左括号和右括号不匹配,则表达式不合法。最后,如果栈为空,则表示所有括号都匹配,表达式合法。