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.

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

 class Solution {

 public:

     bool isValid(string s) {

         if(!s.size())

             return true;

         char c;

         stack<char> stk;

         for(int i = ; i < s.size(); ++i){

             if(s[i] == '[' || s[i] == '{' || s[i] == '('){

                 stk.push(s[i]);

                 continue;

             }else if(s[i] == ']'){

                 if(stk.empty())

                     return false;

                 c = stk.top();

                 stk.pop();

                 if(c != '[')

                     return false;

             }else if(s[i] == '}'){

                 if(stk.empty())

                     return false;

                 c = stk.top();

                 stk.pop();

                 if(c != '{')

                     return false;

             }else{

                 if(stk.empty())

                     return false;

                 c = stk.top();

                 stk.pop();

                 if(c != '(')

                     return false;

             }

         }

         if(stk.empty())

             return true;

         return false;

     }

 };

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

 bool ValidParentheses(string s)

 {

     if (!s.size())

         return true;

     stack<char> stk;

     map<char, char> m;

     m['('] = ')';

     m['['] = ']';

     m['{'] = '}';

     for (auto c : s){

         if (c == '(' || c == '[' || c == '{'){

             stk.push(c);

         }

         else if (c == ')' || c == ']' || c == '}'){

             if (stk.empty())

                 return false;

             if (c == m[stk.top()])

                 stk.pop();

             else

                 return false;

         }

     }

     if (stk.empty())

         return true;

     return false;

 }

java版本代码如下所示：

 public class ValidParentheses {

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         ValidParentheses validParentheses = new ValidParentheses();

         String string = new String("[]{}(){[]}");

         System.out.println("" + validParentheses.ValidParentheses(string));

     }

     boolean ValidParentheses(String str){

         if(str.length() == 0)

             return true;

         Stack<Character> stk = new Stack<Character>();

         char [] parentheses = str.toCharArray();

         for(char c : parentheses){

             if(c == '(' || c == '{' || c == '['){

                 stk.push(c);

             }else if(c == ')'){

                 if(stk.empty() || stk.pop() != '(')

                     return false;

             }else if(c == '}'){

                 if(stk.empty() || stk.pop() != '{')

                     return false;

             }else if(c == ']'){

                 if(stk.empty() || stk.pop() != '[')

                     return false;

             }

         }

         if(stk.empty())

             return true;

         return false;

     }

 }

巴特西

LeetCode OJ：Valid Parentheses（有效括号）

最新文章

热门文章