【JAVA、C++】LeetCode 020 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.

解题思路：

由于"()","[()]","{{({[]})}}"都会通过，即出现')]}'这种字符就需要判断前面字符是否是对应的字符，如果用指针的话，实现起来相当复杂，考虑到这种情况和栈的后进先出颇为相似，因此采用stack类

JAVA实现如下：

	static public boolean isValid(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            int pos = "()[]{}".indexOf(s.charAt(i));
            if (pos % 2 !=0) {
                if (stack.isEmpty() || stack.pop() != pos - 1)
                    return false;
            } else
            	stack.push(pos);
        }
        return stack.isEmpty();
    }

C++

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