设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号,编写一个算法判断其中的括号是否匹配用c语言编写全部代码
时间: 2024-03-05 21:52:12 浏览: 110
检查一个算术表达式中的括号是否正确匹配。
可以使用栈来实现括号匹配的判断。具体实现步骤如下:
1. 定义一个栈,用于存储左括号。
2. 遍历算术表达式中的每个字符,如果是左括号,则将其压入栈中。
3. 如果是右括号,则弹出栈顶元素,判断该左括号是否与当前右括号匹配。如果不匹配,说明括号不匹配;如果匹配,则继续遍历。
4. 如果遍历结束后栈为空,则说明括号匹配;如果栈不为空,则说明括号不匹配。
下面是具体的C语言实现代码:
```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--];
}
char peek(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_matching(char left, char right) {
if (left == '(' && right == ')') {
return 1;
} else if (left == '[' && right == ']') {
return 1;
} else if (left == '{' && right == '}') {
return 1;
} else {
return 0;
}
}
int is_balanced(char *expression) {
Stack s;
init(&s);
for (int i = 0; expression[i] != '\0'; i++) {
char c = expression[i];
if (c == '(' || c == '[' || c == '{') {
push(&s, c);
} else if (c == ')' || c == ']' || c == '}') {
if (is_empty(&s)) {
return 0;
}
char left = pop(&s);
if (!is_matching(left, c)) {
return 0;
}
}
}
return is_empty(&s);
}
int main() {
char expression[MAX_SIZE];
printf("Enter an arithmetic expression: ");
fgets(expression, MAX_SIZE, stdin);
if (is_balanced(expression)) {
printf("The expression is balanced\n");
} else {
printf("The expression is not balanced\n");
}
return 0;
}
```
在这个代码中,我们定义了一个`Stack`结构体表示栈,包含一个字符数组`data`和一个整数`top`,分别表示栈的元素和栈顶位置。我们还定义了一些栈的基本操作,如初始化、入栈、出栈、查看栈顶元素和判断栈是否为空。
在`is_matching`函数中,我们判断左括号`left`和右括号`right`是否匹配。如果匹配,返回`1`,否则返回`0`。
在`is_balanced`函数中,我们遍历算术表达式中的每个字符,如果是左括号,则将其入栈;如果是右括号,则弹出栈顶元素,判断是否与当前右括号匹配。如果栈为空或者不匹配,则说明括号不匹配。遍历结束后,如果栈为空,则说明括号匹配;否则说明括号不匹配。
最后,在`main`函数中,我们从标准输入中读取算术表达式,并调用`is_balanced`函数判断括号是否匹配。如果匹配,输出`The expression is balanced`,否则输出`The expression is not balanced`。
阅读全文