设一个算法表达式中包含圆括号,方括号和花括号三种类型的括号编写一个算法,判断其中的括号是否匹配。 提示,本题使用一个运算符栈st,当遇到(、[或{时进栈,当遇到}、]、)时判断栈顶里为相应的括号,若是退栈则继续执行,否则算法结束。用一个简单c程序解答
时间: 2024-10-16 09:21:43 浏览: 3
这是一个经典的使用栈数据结构解决的问题,我们可以在 C 语言中创建一个函数来检查括号是否匹配。下面是一个简化的 C 程序实现:
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h> // 包含堆栈操作的头文件
// 定义一个字符类型用于存储括号
typedef enum {LEFT_PAREN = '(', RIGHT_PAREN = ')', LEFT_BRACKET = '[', RIGHT_BRACKET = ']', LEFT CURLY_BRACE = '{', RIGHT CURLY_BRACE = '}' } BracketType;
bool isParenthesesMatch(const char *expression) {
Stack *stack = createStack(); // 初始化空栈
for (char c : expression) {
if (c == LEFT_PAREN || c == LEFT_BRACKET || c == LEFT_CURLY_BRACE) {
push(stack, c);
} else if (c == RIGHT_PAREN && peek(stack) == LEFT_PAREN) {
pop(stack); // 如果找到对应匹配的左括号,则出栈
} else if (c == RIGHT_BRACKET && peek(stack) == LEFT_BRACKET) {
pop(stack); // 同理处理方括号
} else if (c == RIGHT_CURLY_BRACE && peek(stack) == LEFT_CURLY_BRACE) {
pop(stack); // 处理大括号
} else {
return false; // 非法括号对,立即返回false
}
}
return stack_empty(stack); // 所有括号都已检查,如果没有剩余括号,说明匹配
}
Stack* createStack() {
// 创建栈结构并初始化,这里假设Stack是一个自定义的数据结构,包含元素和top指针
Stack *stack = (Stack*)malloc(sizeof(Stack));
stack->top = -1;
return stack;
}
void push(Stack *stack, char item) {
stack->top++;
stack->data[stack->top] = item;
}
char peek(Stack *stack) {
return stack->data[stack->top];
}
bool stack_empty(Stack *stack) {
return stack->top == -1;
}
void freeStack(Stack *stack) {
free(stack->data);
free(stack);
}
int main() {
char expression[] = "({[]})";
if (isParenthesesMatch(expression)) {
printf("The parentheses in the expression are matched.\n");
} else {
printf("The parentheses in the expression are not matched.\n");
}
return 0;
}
```
上述程序首先定义了一个状态机,遍历输入的表达式,对于每个字符,如果遇到左括号就入栈,遇到右括号时,检查栈顶是否有对应的左括号,若有则出栈。如果在整个过程中没有遇到非法的括号组合或者右括号无法匹配到左括号,那么括号就是匹配的。
阅读全文