括号匹配问题 栈c语言
时间: 2023-11-07 12:32:33 浏览: 36
非常欢迎您提出问题。关于括号匹配问题,它是一种经典的栈应用问题,通常用于识别代码中是否有错误的括号匹配问题。在C语言中可以使用栈来解决这个问题。具体的实现方法需要遍历字符串,遇到左括号就将其入栈,遇到右括号就将栈顶元素出栈,如果栈顶元素和当前右括号不匹配,则可以得知括号匹配错误。如果字符串遍历完成后,栈中仍有元素,则说明括号匹配也存在问题。希望对您有所帮助。
相关问题
括号匹配问题 栈c语言代码
好的,我可以回答关于编程问题的提问。以下是一个括号匹配的栈C语言代码示例:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
char stack[MAX_SIZE];
int top = -1;
void push(char ch) {
if (top == MAX_SIZE - 1) {
printf("Stack overflow\n");
exit(1);
}
stack[++top] = ch;
}
char pop() {
if (top == -1) {
printf("Stack underflow\n");
exit(1);
}
return stack[top--];
}
int isPair(char open, char close) {
if (open == '(' && close == ')')
return 1;
else if (open == '{' && close == '}')
return 1;
else if (open == '[' && close == ']')
return 1;
else
return 0;
}
int isBalanced(char* exp) {
for (int i = 0; i < strlen(exp); i++) {
if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[') {
push(exp[i]);
} else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
if (top == -1 || !isPair(pop(), exp[i]))
return 0;
}
}
if (top == -1)
return 1;
else
return 0;
}
int main() {
char exp[MAX_SIZE];
printf("Enter the expression: ");
fgets(exp, MAX_SIZE, stdin);
if (isBalanced(exp))
printf("The expression is balanced\n");
else
printf("The expression is not balanced\n");
return 0;
}
```
该代码可以用于判断一个表达式中的括号是否匹配。如果表达式中每个左括号都有对应的右括号,且左右括号的顺序正确,那么表达式就是匹配的。如果不匹配,程序会输出一条错误信息。
括号匹配问题 栈c语言 指针
括号匹配问题可以使用栈来解决。具体实现可以使用一个指针指向栈顶元素,每次遇到左括号就将其入栈,遇到右括号就将栈顶元素出栈并进行匹配,如果匹配成功则继续,否则就说明括号不匹配。
以下是一个基于指针的栈的实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct StackNode {
char data;
struct StackNode *next;
} StackNode;
typedef struct Stack {
StackNode *top;
int size;
} Stack;
// 初始化栈
void init(Stack *stack) {
stack->top = NULL;
stack->size = 0;
}
// 入栈
void push(Stack *stack, char data) {
StackNode *node = (StackNode*)malloc(sizeof(StackNode));
node->data = data;
node->next = stack->top;
stack->top = node;
stack->size++;
}
// 出栈
char pop(Stack *stack) {
if (stack->top == NULL) {
printf("Error: stack is empty\n");
exit(1);
}
char data = stack->top->data;
StackNode *tmp = stack->top;
stack->top = stack->top->next;
free(tmp);
stack->size--;
return data;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
return stack->top == NULL;
}
// 括号匹配
int isValid(char *s) {
Stack stack;
init(&stack);
while (*s != '\0') {
switch (*s) {
case '(':
case '[':
case '{':
push(&stack, *s);
break;
case ')':
if (isEmpty(&stack) || pop(&stack) != '(') {
return 0;
}
break;
case ']':
if (isEmpty(&stack) || pop(&stack) != '[') {
return 0;
}
break;
case '}':
if (isEmpty(&stack) || pop(&stack) != '{') {
return 0;
}
break;
default:
break;
}
s++;
}
return isEmpty(&stack);
}
int main() {
char s1[] = "()[]{}";
char s2[] = "([)]";
char s3[] = "{[]}";
printf("%s is %s\n", s1, isValid(s1) ? "valid" : "invalid");
printf("%s is %s\n", s2, isValid(s2) ? "valid" : "invalid");
printf("%s is %s\n", s3, isValid(s3) ? "valid" : "invalid");
return 0;
}
```