C语言编写一个算法利用链栈判断输入的表达式中括号是否配对(假设只含有左、右圆括号)。在主函数中测试该算法的正确性。
时间: 2024-10-14 16:08:31 浏览: 13
在C语言中,我们可以使用队列数据结构和一个布尔数组来判断表达式的括号是否配对。这里我们先创建一个简单的队列用于存储遇到的左括号,当遇到右括号时,从队列中弹出一个左括号并与之匹配。如果队列为空或者弹出的左括号不等于当前右括号,说明有括号未配对。
以下是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100
bool stack[MAX_STACK_SIZE];
int top = -1;
// 判断括号是否匹配
bool isMatch(char op1, char op2) {
if (op1 == '(' && op2 == ')') return true;
else if (op1 == '[' && op2 == ']') return true;
else if (op1 == '{' && op2 == '}') return true;
else return false;
}
// 向队列添加元素
void push(char c) {
if (top >= MAX_STACK_SIZE - 1) {
printf("Error: Stack overflow!\n");
return;
}
stack[++top] = c;
}
// 从队列移除并返回元素
char pop() {
if (top < 0) {
printf("Error: Stack underflow!\n");
return '\0';
}
return stack[top--];
}
// 检查表达式括号是否配对
bool checkParentheses(char* expression) {
int i = 0;
while (expression[i]) {
if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{') {
push(expression[i]);
} else if (expression[i] == ')' || expression[i] == ']' || expression[i] == '}') {
if (top < 1 || !isMatch(stack[top], expression[i])) {
return false;
}
pop();
}
i++;
}
// 如果只剩下一个左括号没匹配,表示有遗漏
return top == -1;
}
int main() {
char testExpr[] = "((()))";
char brokenExpr[] = "({[()]})";
bool result = checkParentheses(testExpr);
if (result) {
printf("%s has balanced parentheses.\n", testExpr);
} else {
printf("%s has unbalanced parentheses.\n", testExpr);
}
result = checkParentheses(brokenExpr);
if (result) {
printf("%s has balanced parentheses.\n", brokenExpr);
} else {
printf("%s has unbalanced parentheses.\n", brokenExpr);
}
return 0;
}
```
在这个例子中,`checkParentheses` 函数会检查给定字符串 `expression` 中的所有括号是否配对,通过不断地遍历输入字符串,将遇到的左括号推入队列,遇到右括号则尝试从队列中弹出并匹配。如果在遍历结束后队列为空,则表示所有括号都已配对,否则表示有括号未配对。
阅读全文