如何用栈实现括号匹配的长尾？
- 内容介绍
- 文章标签
- 相关推荐
本文共计824个文字，预计阅读时间需要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!");
}
本文共计824个文字，预计阅读时间需要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!");
}