欢迎来到天天文库
浏览记录
ID:37718054
大小:32.50 KB
页数:4页
时间:2019-05-29
《堆栈实现括号匹配问题 C》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、堆栈实现括号匹配问题C/C++括号匹配:1. 括号匹配的四种可能性:①左右括号配对次序不正确②右括号多于左括号③左括号多于右括号④左右括号匹配正确2. 算法思想:顺序扫描算数表达式(表现为一个字符串),当遇到三种类型的左括号时候让该括号进栈;当扫描到某一种类型的右括号时,比较当前栈顶元素是否与之匹配,若匹配,退栈继续判断;若当前栈顶元素与当前扫描的括号不匹配,则左右括号配对次序不正确;若字符串当前为某种类型的右括号而堆栈已经空,则右括号多于左括号;字符串循环扫描结束时,若堆栈非空(即堆栈尚有某种类型的左括号),则说明左括号多
2、于右括号;否则,括号配对正确。3. 程序实现: #include#includeusingnamespacestd;#definemaxsize100structsStack{ charsign[maxsize]; inttop;};intInitsStack(sStack&SS){ SS.top=-1; return1;}intIsEmptysStack(sStack&SS){ if(SS.top==-1)return1;
3、 return0;}intPushsStack(sStack&SS,charc){ SS.sign[++SS.top]=c; return1;}intUpsStack(sStack&SS){ if(IsEmptysStack(SS)){cout<<"栈空"<4、 returnSS.sign[SS.top];}intmain(){ strings; cout<<"输入表达式"<>s; intlength=s.length(); inti; sStackSS; InitsStack(SS); for(i=0;i5、6、s[i]=='['7、8、s[i]=='{') 9、 PushsStack(SS,s[i]); elseif(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)=='(') UpsStack(SS); elseif(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)!='(') cout<<"括号匹配次序不10、正确"<11、(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)=='{') UpsStack(SS); elseif(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)!='{') cout<<"括号匹配次序不正确"<12、13、s[i]==']'14、15、s[i]=='}')16、&&IsEmptysStack(SS)) cout<<"右括号多于左括号"<
4、 returnSS.sign[SS.top];}intmain(){ strings; cout<<"输入表达式"<>s; intlength=s.length(); inti; sStackSS; InitsStack(SS); for(i=0;i5、6、s[i]=='['7、8、s[i]=='{') 9、 PushsStack(SS,s[i]); elseif(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)=='(') UpsStack(SS); elseif(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)!='(') cout<<"括号匹配次序不10、正确"<11、(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)=='{') UpsStack(SS); elseif(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)!='{') cout<<"括号匹配次序不正确"<12、13、s[i]==']'14、15、s[i]=='}')16、&&IsEmptysStack(SS)) cout<<"右括号多于左括号"<
5、
6、s[i]=='['
7、
8、s[i]=='{')
9、 PushsStack(SS,s[i]); elseif(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)=='(') UpsStack(SS); elseif(s[i]==')'&&!IsEmptysStack(SS)&&TopsStack(SS)!='(') cout<<"括号匹配次序不
10、正确"<11、(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)=='{') UpsStack(SS); elseif(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)!='{') cout<<"括号匹配次序不正确"<12、13、s[i]==']'14、15、s[i]=='}')16、&&IsEmptysStack(SS)) cout<<"右括号多于左括号"<
11、(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)=='{') UpsStack(SS); elseif(s[i]=='}'&&!IsEmptysStack(SS)&&TopsStack(SS)!='{') cout<<"括号匹配次序不正确"<12、13、s[i]==']'14、15、s[i]=='}')16、&&IsEmptysStack(SS)) cout<<"右括号多于左括号"<
12、
13、s[i]==']'
14、
15、s[i]=='}')
16、&&IsEmptysStack(SS)) cout<<"右括号多于左括号"<
此文档下载收益归作者所有