LeetCode OJ：Valid Parentheses（有效括号）

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

简单的堆栈问题，代码如下：

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         if(!s.size())
 5             return true;
 6         char c;
 7         stack<char> stk;
 8         for(int i = 0; i < s.size(); ++i){
 9             if(s[i] == '[' || s[i] == '{' || s[i] == '('){
10                 stk.push(s[i]);
11                 continue;
12             }else if(s[i] == ']'){
13                 if(stk.empty())
14                     return false;
15                 c = stk.top();
16                 stk.pop();
17                 if(c != '[')
18                     return false;
19             }else if(s[i] == '}'){
20                 if(stk.empty())
21                     return false;
22                 c = stk.top();
23                 stk.pop();
24                 if(c != '{')
25                     return false;
26             }else{
27                 if(stk.empty())
28                     return false;
29                 c = stk.top();
30                 stk.pop();
31                 if(c != '(')
32                     return false;
33             }
34         }
35         if(stk.empty())
36             return true;
37         return false;
38     }
39 };

简单一点的话可以使用下面这种方式：

 1 bool ValidParentheses(string s)
 2 {
 3     if (!s.size())
 4         return true;
 5     stack<char> stk;
 6     map<char, char> m;
 7     m['('] = ')';
 8     m['['] = ']';
 9     m['{'] = '}';
10     for (auto c : s){
11         if (c == '(' || c == '[' || c == '{'){
12             stk.push(c);
13         }
14         else if (c == ')' || c == ']' || c == '}'){
15             if (stk.empty())
16                 return false;
17             if (c == m[stk.top()])
18                 stk.pop();
19             else
20                 return false;
21         }
22     }
23     if (stk.empty())
24         return true;
25     return false;
26 }

java版本代码如下所示：

 1 public class ValidParentheses {
 2     public static void main(String[] args) {
 3         // TODO Auto-generated method stub
 4         ValidParentheses validParentheses = new ValidParentheses();
 5         String string = new String("[]{}(){[]}");
 6         System.out.println("" + validParentheses.ValidParentheses(string));
 7     }
 8     
 9     boolean ValidParentheses(String str){
10         if(str.length() == 0)
11             return true;
12         Stack<Character> stk = new Stack<Character>();
13         char [] parentheses = str.toCharArray();
14         for(char c : parentheses){
15             if(c == '(' || c == '{' || c == '['){
16                 stk.push(c);
17             }else if(c == ')'){
18                 if(stk.empty() || stk.pop() != '(')
19                     return false;
20             }else if(c == '}'){
21                 if(stk.empty() || stk.pop() != '{')
22                     return false;
23             }else if(c == ']'){
24                 if(stk.empty() || stk.pop() != '[')
25                     return false;
26             }
27         }
28         if(stk.empty())
29             return true;
30         return false;
31     }
32 }