堆栈实现括号匹配问题 C

《堆栈实现括号匹配问题 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;i

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<<"右括号多于左括号"<