用c.设计算法判断一个算术表达式的圆括号是否配对。(提示:对表达式进行扫描,遇‘ (’ 进栈,遇‘ )’退掉栈顶的‘ (’,表达式被扫描完毕,栈为空)
时间: 2024-10-10 07:04:27 浏览: 13
要设计一个C语言算法来判断算术表达式中的圆括号是否配对,你可以使用栈(stack)的数据结构。这里有一个简单的示例:
```c
#include <stdio.h>
#include <stdbool.h>
// 假设链表节点定义如下
typedef struct Node {
char ch;
struct Node *next;
} Node;
bool isParenthesesBalanced(Node* L) {
// 初始化栈和标志变量
char stack[] = {'\0'};
int top = -1, open_brackets[3] = {0}; // 用于存储三种类型的左括号计数
Node* p = L->next;
// 遍历链表
while (p != NULL) {
switch (p->ch) {
case '(':
stack[++top] = '(';
open_brackets[0]++;
break;
case '[':
stack[++top] = '[';
open_brackets[1]++;
break;
case '{':
stack[++top] = '{';
open_brackets[2]++;
break;
case ')':
if (top == -1 || stack[top] != '(') {
return false; // 匹配错误
}
stack[top--] = '\0'; // 出栈
open_brackets[0]--;
break;
case ']':
if (top == -1 || stack[top] != '[') {
return false; // 匹配错误
}
stack[top--] = '\0'; // 出栈
open_brackets[1]--;
break;
case '}':
if (top == -1 || stack[top] != '{') {
return false; // 匹配错误
}
stack[top--] = '\0'; // 出栈
open_brackets[2]--;
break;
default:
continue;
}
p = p->next;
}
// 检查栈是否为空以及开放括号是否全部关闭
for (int i = 0; i < 3; i++) {
if (open_brackets[i]) {
return false; // 未关闭的括号
}
}
if (top == -1) {
return true; // 所有括号已匹配
} else {
return false; // 栈非空,表示还有未匹配的括号
}
}
int main() {
// 创建一个链表模拟输入的算术表达式
Node* head = ...; // 假设已经构建好链表
if (isParenthesesBalanced(head)) {
printf("The parentheses are balanced.\n");
} else {
printf("The parentheses are not balanced.\n");
}
return 0;
}
```
在这个算法中,我们遍历链表中的每个字符,如果遇到左括号就入栈并增加相应类型的计数器,遇到右括号则检查栈顶元素是否与其相配,如果匹配则出栈相应的计数器减一。最后,检查栈是否为空以及是否有剩余的开放括号,以确定整个表达式中的括号是否配对。
阅读全文