题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。

思路

由于栈结构的特殊性，非常适合做对称匹配类的题目。
看到这种括号匹配啥的，第一反应就是使用栈了。


括号的判断：

直接判断啦，还以为有什么ASII码（尴尬）

第一种做法

直接遍历，左括号入栈，遇到右括号开始匹配出栈，比第二种做法节约了一个栈的内存。

  1. class Solution {
  2. public:
  3.     bool isValid(string s) {
  4.         //括号问题用栈处理
  6.         //建立哈希表形成括号与数字之间的对应
  7.         map<char,int> m={{'(',1},{'{',2},{'[',3},{')',4},{'}',5},{']',6}};
  8.         stack<int> kh;
  9.         bool istrue=true;//判断最终结果
  11.         for(char c:s){
  12.             int flag =m[c];
  14.             if(1<=flag&&flag<=3){
  15.                 //说明是开括号,入栈
  16.                 kh.push(flag);
  17.             }else if(!kh.empty()&&kh.top()==flag-3){
  18.                 //配对成功,出栈
  19.                 kh.pop();
  20.             }else{
  21.                 //栈为空，则说明第一个是闭括号
  22.                 //不相等，说明配对失败
  23.                 istrue =false;
  24.                 break;
  25.             }
  26.         }
  28.         if(!kh.empty()){
  29.             //遍历结束后栈不为空，则说明开括号多余
  30.             istrue =false;
  31.         }
  33.         return istrue;
  35.     }
  36. };

第二种做法（按照思路）

先用一个栈存入所有字符，然后弹出 右括号存入到一个新的栈中，如果碰到左括号就开始匹配。
【ps：这种解题思路也适用于模拟计算器吧，中缀表达式类型】

class Solution {
public:
    bool isValid(string s) {
    //括号问题用栈处理
    stack<char> total_s; //存储所有字符
    stack<char> temp_s; //中间栈

    map<char,int> m ={{'(',1},{'{',2},{'[',3},{']',4},{'}',5},{')',6}}; //建立一个对应哈希表，方便后续判断
    for(auto c:s){
        total_s.push(c);
    }

    while(!total_s.empty()){
        if(m[total_s.top()]>3){
            //是右括号
            temp_s.push(total_s.top());
            total_s.pop();
        }else{
            //是左括号
            if(temp_s.empty()){
                //中转栈为空，无匹配右括号
                return false;
            }else{
                if(m[total_s.top()]+m[temp_s.top()]==7){
                    //匹配成功
                    temp_s.pop();
                    total_s.pop();
                }else{
                    return false;
                }
            }
        }
    }

    return total_s.empty()&&temp_s.empty();

    }
};

第三种做法

遍历字符串，碰到左括号就入栈对应右括号，碰到右括号就判断与栈顶是否相同，相同则出栈，不同则return false。

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};