简单括号匹配_栈

 课程笔记 10：数据结构（清华）　栈_opnd push-CSDN博客

括号匹配。对于一个表达式，要想确认其中所使用的括号是否匹配，可以采用减而治之的思路，将每对邻近括号消去，则剩下的达式括号匹配当且仅当原表达式括号匹配。利用这一思路，我们可以采用栈结构来实现：

bool paren (const char exp[], int n){

Stack S;int j = 0;

for (int i = 0; i < n; i ++){

        if (exp[i] == '(') S.push(++ j);

        if (!S.empty() && (exp[i] == ')'))S.pop();

        if (S.empty() && (exp[i] == ')'))return false;

}

return S.empty();}
 

#include <stdio.h>// 括号匹配函数
int paren(const char exp[]) {int stack[1000] = {0};int top = -1;for (int i = 0; exp[i] != '\0'; i++) {if (exp[i] == '(')stack[++top] = 1;else if (exp[i] == ')') {if (top >= 0) top--;else return 0;}}return top == -1;
}int main() {char exp[1000];gets(exp);if (paren(exp))  printf("括号匹配\n");else  printf("括号不匹配\n");return 0;
}

#include <stdio.h>
#include <stdlib.h>// 定义栈结构
typedef struct Stack {int *data;int top;int capacity;
} Stack;// 初始化栈
void initStack(Stack *s, int capacity) {s->data = (int *)malloc(capacity * sizeof(int));s->top = -1;s->capacity = capacity;
}// 入栈操作
void push(Stack *s, int value) {if (s->top < s->capacity - 1) {s->data[++(s->top)] = value;}
}// 出栈操作
int pop(Stack *s) {if (s->top >= 0) {return s->data[(s->top)--];}return -1;  // 表示栈为空，无元素可出栈
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 括号匹配函数
int paren(const char exp[], int n) {Stack S;initStack(&S, n);  // 初始化栈，大小为表达式长度for (int i = 0; i < n; i++) {if (exp[i] == '(') {push(&S, 1);  // 这里入栈的值可以是任意值，仅用于标记左括号} else if (exp[i] == ')') {if (!isEmpty(&S)) {pop(&S);} else {// 右括号多了，直接返回 0 表示不匹配free(S.data);return 0;}}}int result = isEmpty(&S);  // 判断栈是否为空，为空则括号匹配free(S.data);  // 释放栈内存return result;
}int main() {char exp[1000];fgets(exp, sizeof(exp), stdin);  // 读取表达式，包含换行符int len = 0;while (exp[len] != '\n' && exp[len] != '\0') {len++;}int match = paren(exp, len);if (match) {printf("括号匹配\n");} else {printf("括号不匹配\n");}return 0;
}