C++中用栈来判断括号字符串匹配问题的实现方法
本文实例主要实现：输入一个括号字符串，依次检验，若为左括号则入栈，若为右括号则出栈一个字符判断是否与之相对应，在最后还需判断栈是否为空，如果不为空则不匹配。
首先回顾栈的基本知识：
1.定义栈的结构体并初始化一个新栈：
structstack
{
charstrstack[stacksize];
inttop;
};
voidInitStack(stack&s)
{
s.top=-1;
}
2.出栈和入栈操作：
charPush(stack&s,chara)
{
if(s.top==stacksize-1)
{
return0;
}
s.top++;
s.strstack[s.top]=a;
returna;
}
charPop(stack&s)
{
if(s.top==-1)
{
return0;
}
chara=s.strstack[s.top];
s.top--;
returna;
}
3.判断栈是否为空：
intEmpty(stack&s,intre)
{
if(s.top==-1)
{
return1;
}
else
{
return0;
}
}
以上是栈的基本操作，定义一个栈和初始化一个新栈，出栈和入栈操作，以及判断栈是否为空的情况。接下来将写一个函数，检查字符串的每个字符，左括号则进行入栈操作，右括号则进行出栈操作看其是否匹配，最后判断是否为空以判定是否匹配。
主要功能代码如下：
intCheck(char*str)
{
stacks;
InitStack(s);
intstrn=strlen(str);
for(inti=0;i<strn;i++)
{
chara=str[i];
switch(a)
{
case'(':
case'[':
case'{':
Push(s,a);
break;
case')':
if(Pop(s)!='(')
{
return0;
}
break;
case']':
if(Pop(s)!='[')
{
return0;
}
break;
case'}':
if(Pop(s)!='{')
{
return0;
}
break;
}
}
intre=0;
re=Empty(s,re);
if(re==1)
{
return1;
}
else
{
return0;
}
}
自此，括号字符串匹配的判断问题已经解决，下面贴出完整的经过编译运行过的代码。
完整实例代码如下：
#include<iostream>
#include<stdio.h>
#include<string.h>
usingnamespacestd;
#definestacksize100
structstack
{
charstrstack[stacksize];
inttop;
};
voidInitStack(stack&s)
{
s.top=-1;
}
charPush(stack&s,chara)
{
if(s.top==stacksize-1)
{
return0;
}
s.top++;
s.strstack[s.top]=a;
returna;
}
charPop(stack&s)
{
if(s.top==-1)
{
return0;
}
chara=s.strstack[s.top];
s.top--;
returna;
}
intEmpty(stack&s,intre)
{
if(s.top==-1)
{
return1;
}
else
{
return0;
}
}
intCheck(char*str)
{
stacks;
InitStack(s);
intstrn=strlen(str);
for(inti=0;i<strn;i++)
{
chara=str[i];
switch(a)
{
case'(':
case'[':
case'{':
Push(s,a);
break;
case')':
if(Pop(s)!='(')
{
return0;
}
break;
case']':
if(Pop(s)!='[')
{
return0;
}
break;
case'}':
if(Pop(s)!='{')
{
return0;
}
break;
}
}
intre=0;
re=Empty(s,re);
if(re==1)
{
return1;
}
else
{
return0;
}
}
voidmain()
{
charstr[100];
cout<<"请输入一个长度小于100的字符串:"<<endl;
cin>>str;
intre=Check(str);
if(re==1)
{
cout<<"你输入的字符串括号完全匹配！"<<endl;
}
elseif(re==0)
{
cout<<"你输入的字符串括号不匹配！"<<endl;
}
}
希望本文所述实例对大家C++算法设计的学习有所帮助。