20. Valid Parentheses

Nothing interesting. Just use stack.

1:  class Solution {  
2:  public:  
3:    bool isValid(string s) {  
4:      stack<char> stk;  
5:      for (char c : s) {  
6:        switch(c) {  
7:          case '(':  
8:            stk.push(c);  
9:            break;  
10:          case ')':  
11:            if (stk.empty() || stk.top() != '(') return false;  
12:            stk.pop();  
13:            break;  
14:          case '[':  
15:            stk.push(c);  
16:            break;  
17:          case ']':  
18:            if (stk.empty() || stk.top() != '[') return false;  
19:            stk.pop();  
20:            break;  
21:          case '{':  
22:            stk.push(c);  
23:            break;  
24:          case '}':  
25:            if (stk.empty() || stk.top() != '{') return false;  
26:            stk.pop();  
27:            break;  
28:        }  
29:      }  
30:      return stk.empty();  
31:    }  
32:  };  

When I revisit this problem, I have a more concise code. However, I made a mistake in line 15 where I returned true.

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