10.假设表达式中允许包含圆括号、方括号和大括号3种括号,编写一个算法判断表达式中的括号是否正确配对。写一个简单程序用c语言
时间: 2024-10-25 10:17:47 浏览: 42
设计一个算法判别一个算术表达式的圆括号是否正确配对
在C语言中,你可以通过遍历输入字符串并维护一个栈数据结构来检查括号是否匹配。以下是一个简单的C语言程序示例:
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
// 检查括号类型的枚举
enum BracketType {
OPEN_PAREN = '(',
OPEN_BRACE = '{',
OPEN_SQUARE = '[',
CLOSE_PAREN = ')',
CLOSE_BRACE = '}',
CLOSE_SQUARE = ']'
};
bool isValidParentheses(const char* expression) {
if (expression == NULL || strlen(expression) == 0) {
return false;
}
stack_t brackets = {0}; // 初始化空栈
bool bracketMap[3] = {false, false, false}; // 存储当前层已打开的括号
for (int i = 0; expression[i]; i++) {
char c = expression[i];
switch (c) {
case OPEN_PAREN:
brackets.top++;
bracketMap[OPEN_PAREN - 1] = true;
break;
case CLOSE_PAREN:
if (!bracketMap[CLOSE_PAREN - 1]) {
return false;
}
brackets.top--;
bracketMap[CLOSE_PAREN - 1] = false;
break;
case OPEN_BRACE:
brackets.top++;
bracketMap[OPEN_BRACE - 1] = true;
break;
case CLOSE_BRACE:
if (!bracketMap[CLOSE_BRACE - 1]) {
return false;
}
brackets.top--;
bracketMap[CLOSE_BRACE - 1] = false;
break;
case OPEN_SQUARE:
brackets.top++;
bracketMap[OPEN_SQUARE - 1] = true;
break;
case CLOSE_SQUARE:
if (!bracketMap[CLOSE_SQUARE - 1]) {
return false;
}
brackets.top--;
bracketMap[CLOSE_SQUARE - 1] = false;
break;
default: continue; // 非括号字符忽略
}
}
return brackets.top == 0; // 如果最后栈为空,表示所有括号都已关闭
}
int main() {
const char* test_cases[] = {"()()", "({})", "[[]]", "({[})]", "test()"};
int num_tests = sizeof(test_cases) / sizeof(test_cases[0]);
for (int i = 0; i < num_tests; i++) {
if (isValidParentheses(test_cases[i])) {
printf("%s: %s\n", test_cases[i], "括号匹配");
} else {
printf("%s: %s\n", test_cases[i], "括号不匹配");
}
}
return 0;
}
```
这个程序首先初始化一个栈和一个布尔数组来跟踪每个层的括号状态。然后遍历输入的字符串,对于遇到的每种括号,它会尝试关闭对应的括号。如果找到未匹配的括号或者到达了最后一个括号而栈不为空,则说明括号配对错误。
运行上述程序可以看到测试用例的结果,括号正确的输出"括号匹配",反之则"括号不匹配"。
阅读全文