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++算法设计的学习有所帮助。