栈的应用——括号匹配

括号字符串：{         (        (        )        ]        [        ]        }

思路：

扫描括号字符串数组，遇到左括号就入栈，遇到右括号就将栈顶的左括号弹出匹配（遇到左括号进栈，遇到右括号就消耗一个左括号）

匹配失败的情况

1、右括号单身

扫描到最后栈为空但是字符串还没有扫描结束，说明右括号单身，因为栈中存放的是左括号，左括号全部弹出匹配但是字符串数组还没有扫描结束，说明下一个扫描的字符元素是右括号（如果是左括号就会进栈，栈不为空）。

2、左括号单身

字符串扫描结束但是栈不空说明左括号单身。

3、左右符号不匹配

扫描过程中遇到右括号，从栈顶弹出左括号与之匹配，但是右括号类型和左括号不统一，比如‘)’遇到了‘{’，匹配失败。

代码实现

bool bracketCheck(char str[],int length){
    SqStack s;//申明一个栈
    InitStack(s);//初始化栈
    //扫描字符串
    int i=0;
    for(i=0;i<length;i++)
    {
        //左括号入栈
        if(str[i]=='('||str[i]=='['||str[i]=='{')
            Push(s,str[i]);
        
        else{
            //如果遇到右括号弹出栈顶元素
            //栈空？
            if(Empty(s))
                return false;
            char backelem;
            Pop(s,backelem);
            //左右括号匹配
            if(str[i]=='('&&backelem!=')')
                return false;
            if(str[i]=='['&&backelem!=']')
                return false;
            if(str[i]=='{'&&backelem!='}')
                return false;
        }
    }
    //字符串扫描结束，判断栈空？
    return StackEmpty(s);
}

如果不是传入字符串数组的方式，而是将括号字符串存放在一个栈中，如何进行括号匹配？

思路：

我们借助一个空辅助栈，扫描栈顶元素，如果是右括号，弹出进入辅助栈，如果是左括号，弹出和辅助栈的栈顶元素匹配

匹配失败的情况：

1、如果辅助栈空，左括号单身；

2、如果扫描结束辅助栈非空，说明右括号单身

3、左右括号不是一类型，匹配失败

代码实现：

bool brackerCheck2(Strack s){
    //申请一个辅助栈
    SqStrack s2;
    InitStrack(s2);
    //扫描符号栈
    while(s.top!=-1){
        char sbackelem;//栈s的栈顶元素标记
        char s2backelem;//栈s2的栈顶元素标记
        bool falg1,flag2;//出栈成功标记
        //右括号出栈进入辅助栈
        if(s.data[s.top]==')'||s.data[s.top]==']'||s.data[s.top]=='}'){
            Pop(s,sbackelem);
            Push(s2,sbackelem);
        }  
        //扫描到左括号，弹出和辅助栈的栈顶元素匹配
        else{
            Pop(s,sbackelem);
            //s2出栈成功
            if(Pop(s2,s2backelem)&&sbackelem!=s2backelem)
                return false;
            //s2空切s非空
            else{
                //左括号单身
                return false;
            }
        }
    }
    //符号栈空
    //辅助栈非空，右括号单身
    if(s2.top!=-1)
        return false;
}