栈在括号匹配中的应用是如何实现的？

更新于

2026-10-10 01:12:44

1阅读来源：SEO基础

内容介绍
文章标签
相关推荐

本文共计803个文字，预计阅读时间需要4分钟。

题目：设计算法，检测一个通过键盘输入的表达式中是否只出现括号（）和[]，并允许任意顺序的嵌套。

思路：当读取到一个左括号时，产生一个匹配的意愿，若再读取到右括号，则检查是否有一个未使用的匹配的意愿，如果有，则使用它，否则表达式中存在不匹配的括号。重复此过程，直到读取完整个表达式。如果所有左括号都有对应的右括号，则表达式中括号匹配；否则，不匹配。

例题：假设通过键盘输入的一个表达式中只出现()和[]并允许任意顺序的嵌套，设计算法，检测括号是否匹配。

思路：当读取到一个左括号时，将产生一个“匹配的意愿”，若再读取到一个左括号，又将产生一个“匹配的意愿”，且后读取到的比先读取到的“匹配的意愿更强烈”

因此可借助栈，按“意愿强烈的优先级” 保存所有未匹配的左括号，即读到左括号即入栈。

当遇到右括号时，则从栈中弹出左括号，检验匹配情况。

( ) [ ] 的ASCII码分别为40、41、91、93

在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。

当遇到一个右括号时，栈已空，说明到目前为止，右括号多于左括号
从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况
算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号

#include<stdio.h> #include<stdlib.h> #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -2 #define ERROR 0 typedef char SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack *s) { s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!s->base) exit(OVERFLOW); s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK; } Status Push(SqStack *s,SElemType e) { if(s->top-s->base>=s->stacksize) { s->base=(SElemType*) realloc (s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s->base) exit(OVERFLOW); s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; return OK; } Status Pop(SqStack *s,SElemType *e) { if(s->top==s->base) return ERROR; *e=* -- s->top; return OK; } Status StackEmpty(SqStack s) { return s.top==s.base; } int main() { char ch,e; SqStack s; InitStack(&s); //( 40 、 )41 、[ 91 、] 93 while((ch=getchar())!='\n') { if(ch=='('||ch=='[') Push(&s,ch); else if(ch==')'||ch==']') { if(!StackEmpty(s)) { Pop(&s,&e); if(!(ch-e==1||ch-e==2)){printf("error!!");exit(0);} } else { printf("error!"); exit(0); } } } if(!StackEmpty(s)) printf("error!"); else printf("success!"); return 0; } Status khpp() { char ch,e; SqStack s; InitStack(&s); //( 40 、 )41 、[ 91 、] 93 while((ch=getchar())!='\n') { if(ch=='('||ch=='[') Push(&s,ch); else if(ch==')'||ch==']') { if(!StackEmpty(s)) { Pop(&s,&e); if(!(ch-e==1||ch-e==2)){ printf("error!!"); return 0;} } else { printf("error!"); return 0; } } } if(!StackEmpty(s)) printf("error!"); else printf("success!"); }

标签：应用举例括号匹配