leetcode 20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

思路：栈实现

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack<char> st;
 5         int len = s.length();
 6         for (int i = 0; i < len; ++i) {
 7             if (!st.empty()) {
 8                 if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
 9                     st.push(s[i]);
10                 } else if ((s[i] == ')' && st.top() == '(') ||
11                            (s[i] == '}' && st.top() == '{') ||
12                            (s[i] == ']' && st.top() == '[')) {
13                     st.pop();
14                 } else {
15                     st.push(s[i]);
16                 }
17             } else {
18                 st.push(s[i]);
19             }
20         }
21         if (st.empty())
22             return true;
23         else
24             return false;
25     }
26 };