力扣-20. 有效的括号

悠悠 2022-11-27 10:15 164阅读 0赞

## 20. 有效的括号 ##

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。  
有效字符串需满足：  
左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。  
示例 1:  
输入: “()”  
输出: true  
示例 2:  
输入: “()\[\]\{\}”  
输出: true  
示例 3:  
输入: “(\]”  
输出: false  
示例 4:  
输入: “(\[)\]”  
输出: false  
示例 5:  
输入: “\{\[\]\}”  
输出: true  
**题意+思路：** 一个简化的括号匹配，用栈的思想，左括号就入栈，遇到右括号就出栈匹配，如果匹配失败就返回false，否则出栈继续匹配  
**代码**

bool isValid(char * s){ 
        int len=strlen(s);
        char ch[8010];
        int num=0;
        bool flag=false;
        for(int i=0;i<len;i++)
        { 
            if(s[i]=='('||s[i]=='['||s[i]=='{')
            { 
                ch[num++]=s[i];
            }
            else if(s[i]==']'||s[i]==')'||s[i]=='}')
            { 
                if(num==0)
                { 
                    flag=true;
                    break;
                }
                else if(s[i]==')')
                { 
                    if(ch[num-1]=='(')num--;
                    else flag=true;
                }
                else if(s[i]==']')
                { 
                    if(ch[num-1]=='[')num--;
                    else flag=true;
                }
                else if(s[i]=='}')
                { 
                    if(ch[num-1]=='{')num--;
                    else flag=true;
                }
            }
        }
        if(flag==true||num>0)return false;
        return true;
    }