[数据结构与算法]Leetcode-20. 有效的括号(简单）

题目：

给定一个只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1：?

输入：s = "()"
输出：true

示例?2：?

输入：s = "()[]{}"
输出：true

示例?3：?

输入：s = "(]"
输出：false

示例?4：?

输入：s = "([)]"
输出：false

示例?5：?

输入：s = "{[]}"
输出：true

题解：

?本题看起来不大好做，但是用一下栈就比较容易解决，栈特点先进后出，具体思路如下：

1、遍历字符串，左括号入栈

2、右括号，拿出栈顶元素与其匹配，匹配成功继续，失败返回false?

3、最后栈为空返回true否则false

例子：

例1、输入：s = "([)]"

s[0] == '(' 入栈

s[1] == '[' 入栈

s[2] == ')' 与栈顶元素比较，栈顶元素为'['? 与s[2]不匹配，返回false

例2、输入：s = "()[]{}"

s[0] == '(' 入栈

s[1] == ')' 与栈顶元素比较，栈顶元素为'(' 与s[1] 匹配,pop掉栈顶元素

s[2] == '[' 入栈

s[3] == ']'?与栈顶元素比较，栈顶元素为'[' 与s[3] 匹配,pop掉栈顶元素

s[4] == '{' 入栈

s[5] == '}'?与栈顶元素比较，栈顶元素为'}' 与s[5] 匹配,pop掉栈顶元素

最后栈为空，返回true

例2、输入：s = "]"

s[0] == ']' 栈为空，返回false

AC代码：

class Solution {
public:
    bool isValid(string s) {
     stack<char>st;

     for(int i=0;i<s.size();i++)
     {
         if(s[i]=='('||s[i]=='['||s[i]=='{')
         {
            st.push(s[i]);
         }
         else if(s[i]==')')
         {
             if(st.empty())
             {
                 return false;
             }
             else if(st.top()!='(')
             {
                 return false;
             }
             else
             {
                 st.pop();
             }
         }
             else if(s[i]==']')
         {
                if(st.empty())
             {
                 return false;
             }
             else if(st.top()!='[')
             {
                 return false;
             }
             else
             {
                 st.pop();
             }
         }
             else if(s[i]=='}')
         {
                if(st.empty())
             {
                 return false;
             }
             else if(st.top()!='{')
             {
                 return false;
             }
             else
             {
                 st.pop();
             }
         }

     }

     return st.empty();
    }
};

附：

STL真好用，很多直接拿来用，用的我都快把底层实现给忘了。