设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号,用c语言编写一个算法判断其中的括号是否匹配。
时间: 2024-02-03 08:13:48 浏览: 82
可以使用栈来判断括号是否匹配。遍历算术表达式,遇到左括号就将其入栈,遇到右括号就将栈顶元素出栈,并判断它们是否匹配。如果括号匹配,继续遍历;如果不匹配,或者栈为空,就说明括号不匹配。
以下是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
char data;
struct StackNode *next;
} StackNode;
typedef struct {
StackNode *top;
} Stack;
Stack* createStack() {
Stack *s = (Stack*) malloc(sizeof(Stack));
s->top = NULL;
return s;
}
void push(Stack *s, char data) {
StackNode *node = (StackNode*) malloc(sizeof(StackNode));
node->data = data;
node->next = s->top;
s->top = node;
}
char pop(Stack *s) {
if (s->top == NULL) {
printf("Error: stack is empty.\n");
exit(EXIT_FAILURE);
}
StackNode *node = s->top;
char data = node->data;
s->top = node->next;
free(node);
return data;
}
int isEmpty(Stack *s) {
return s->top == NULL;
}
int isMatched(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
int checkParentheses(char *expr) {
Stack *s = createStack();
while (*expr != '\0') {
if (*expr == '(' || *expr == '[' || *expr == '{') {
push(s, *expr);
} else if (*expr == ')' || *expr == ']' || *expr == '}') {
if (isEmpty(s) || !isMatched(pop(s), *expr)) {
return 0;
}
}
expr++;
}
int result = isEmpty(s);
free(s);
return result;
}
int main() {
char expr[100];
printf("Enter an expression: ");
scanf("%s", expr);
if (checkParentheses(expr)) {
printf("The parentheses are matched.\n");
} else {
printf("The parentheses are not matched.\n");
}
return 0;
}
```
这个程序中,我们定义了一个栈结构,使用链表来实现。`push` 函数将一个字符入栈,`pop` 函数将栈顶元素出栈,并返回它的值。`isEmpty` 函数判断栈是否为空。`isMatched` 函数判断左右括号是否匹配。`checkParentheses` 函数遍历算术表达式,将左括号入栈,遇到右括号就出栈,并判断左右括号是否匹配,最后判断栈是否为空。
在主函数中,我们从标准输入读入一个算术表达式,调用 `checkParentheses` 函数来判断其中的括号是否匹配。如果返回值为真,则输出括号匹配;否则输出括号不匹配。
阅读全文