假设表达式中允许包含3种括号:圆括号、方括号和大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。要求使用c语言,给出完整代码
时间: 2024-02-11 20:09:58 浏览: 240
[详细完整版]数据结构实例.pdf
5星 · 资源好评率100%
好的,这里是使用顺序栈判断表达式中的括号是否正确配对的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 定义栈的最大容量
typedef struct {
char data[MAX_SIZE];
int top; // 栈顶指针
} Stack;
// 初始化栈
void initStack(Stack* stack) {
stack->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
// 入栈
int push(Stack* stack, char c) {
if (isFull(stack)) {
return 0; // 栈满,入栈失败
}
stack->data[++stack->top] = c;
return 1; // 入栈成功
}
// 出栈
int pop(Stack* stack) {
if (isEmpty(stack)) {
return 0; // 栈空,出栈失败
}
stack->top--;
return 1; // 出栈成功
}
// 获取栈顶元素
char getTop(Stack* stack) {
if (isEmpty(stack)) {
return '\0'; // 栈空,返回空字符
}
return stack->data[stack->top];
}
// 判断括号是否匹配
int isMatch(char left, char right) {
if (left == '(' && right == ')') {
return 1;
}
if (left == '[' && right == ']') {
return 1;
}
if (left == '{' && right == '}') {
return 1;
}
return 0;
}
// 判断表达式中的括号是否配对
int isBalanced(char* expression) {
Stack stack;
initStack(&stack);
for (int i = 0; expression[i] != '\0'; i++) {
if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{') {
push(&stack, expression[i]);
} else if (expression[i] == ')' || expression[i] == ']' || expression[i] == '}') {
if (isEmpty(&stack)) {
return 0; // 栈空,括号不匹配
}
char left = getTop(&stack);
if (!isMatch(left, expression[i])) {
return 0; // 括号不匹配
}
pop(&stack);
}
}
return isEmpty(&stack); // 如果栈为空,说明所有括号都匹配
}
int main() {
char expression[MAX_SIZE];
printf("请输入表达式:");
scanf("%s", expression);
if (isBalanced(expression)) {
printf("括号匹配\n");
} else {
printf("括号不匹配\n");
}
return 0;
}
```
运行程序后,输入表达式,即可判断其中的括号是否正确配对。如果括号匹配,程序输出“括号匹配”,否则输出“括号不匹配”。
阅读全文