20. Valid Parentheses

Leetcode link

解题思路

看到这种有对称性并且对输入输出顺序有的题目，第一个想到的就是先进先出的栈了。

我们可以设计这样一个栈：当遇到左括号时，就把他们压入栈，而当遇到右括号时，只需确定两件事：

1. 当前栈是否为空？

   如果是直接返回 false

2. 当前栈顶是否是相对应的括号？

   如果不是直接返回 false

如果上述两个校验都通过了，那么只需要把当前的栈顶弹出去继续对比就好了。

最后，当输入的 字符串比对完了之后，我们需要检查当前的栈是否为空，如果为空表示所有左右括号是对称的，可以返回 true 了。如果不是则表示左括号多于右括号，返回 false

C++

class Solution {
 public:
  bool isValid(string s) {
    stack<char> stack;
    for (char c : s) {
      switch (c) {
        case '(':
        case '{':
        case '[':
          stack.push(c);
          break;
        case ')':
          if (stack.empty() || stack.top() != '(') return false;
          stack.pop();
          break;
        case '}':
          if (stack.empty() || stack.top() != '{') return false;
          stack.pop();
          break;
        case ']':
          if (stack.empty() || stack.top() != '[') return false;
          stack.pop();
          break;
      }
    }
    return stack.empty();
  }
};

Javascript

var isValid = function(s) {
    const stack = [];
    for(let c of s) {
        if(c === '(' || c === '{' || c === '['){
            stack.push(c);
        } else {
            if(stack.length === 0) return false
            if(c === ')' && stack[stack.length-1] !== '(') return false;
            if(c === '}' && stack[stack.length-1] !== '{') return false;
            if(c === ']' && stack[stack.length-1] !== '[') return false;
            stack.pop()
        }
    }
    return stack.length === 0;
};