用c语言完成假设一算术表达式中包括三种括号:圆括号"("和")",方括号"["和"]",花括 号"{"和"}",且三种括号可按意次序嵌套使用,试编写程序判定输入的表达式所 含的括号是否正确配对出现(已知表达式已存入数据元素为字符的顺序表 中)。若匹配,则返回1,否则返回0。
时间: 2023-09-23 18:04:40 浏览: 76
以下是用C语言实现的算法:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
void push(Stack *s, char c) {
if (s->top == MAXSIZE - 1) {
printf("Stack is full.\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (s->top == -1) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}
char get_top(Stack *s) {
if (s->top == -1) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top];
}
int is_match(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
}
int check_expression(char *exp) {
Stack s;
init(&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 (s.top == -1 || !is_match(pop(&s), exp[i])) {
return 0;
}
}
}
return s.top == -1;
}
int main() {
char exp[MAXSIZE];
printf("Enter an expression:\n");
scanf("%s", exp);
if (check_expression(exp)) {
printf("The expression is correct.\n");
} else {
printf("The expression is incorrect.\n");
}
return 0;
}
```
其中,我们使用了栈来实现括号匹配的算法。遍历表达式字符串,如果遇到左括号,则将其入栈;如果遇到右括号,则从栈中弹出一个左括号并判断是否匹配。如果栈为空或者左右括号不匹配,则表达式不正确,返回0;否则,遍历完整个表达式后,如果栈为空,则表达式正确,返回1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![dsw](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)