LeetCode20. 有效的括号

题目

分析

括号不匹配分为三种情况：左括号多了，右括号多了，不多不少但类型不匹配。

我们用一个栈保存左括号的应该匹配的右括号，就是每遇到一个左括号，将相应类型的右括号压栈。为什么要这样想？因为括号匹配的要求是：

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

尤其是第二条这就是栈的应用。

如何判断左括号多了？ 遍历完了字符串发现栈不为空。

如何判断右括号多了？在匹配过程中，遍历字符产还没结束，栈反而空了

如何判断匹配成功？字符串遍历完后，栈空。

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack<char>stk;
 5         for(int i = 0;i < s.length();i++){
 6             if(s[i] == '(' ) stk.push(')');
 7             else if(s[i] == '[') stk.push(']');
 8             else if(s[i] == '{') stk.push('}');
 9             else if(stk.empty() || s[i] != stk.top()) {return false;}
10             else stk.pop();
11         }
12         return stk.empty();
13     }
14 };

class Solution {
public:
    bool isValid(string s) {
        stack<char>stk;
        for(int i = 0;i < s.length();i++){
            if(s[i] == '(' ) stk.push(')');
            else if(s[i] == '[') stk.push(']');
            else if(s[i] == '{') stk.push('}');
            else if(stk.empty() || s[i] != stk.top()) {return false;}
            else stk.pop();
        }
        return stk.empty();
    }
};