Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.
An input string is valid if:
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 };
leetcode 20. Valid Parentheses
原文：https://www.cnblogs.com/qinduanyinghua/p/11552957.html