[LeetCode] Valid Parentheses 验证括

链接：https://leetcode.com/problems/valid-parentheses/#/description
难度：Easy
题目：20. 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.

翻译：给定一个仅包含字符'（'，'）'，'{'，'}'，'['和']'的字符串，确定输入字符串是否有效。括号必须以正确的顺序关闭，“（）”和“（）[] {}”都是有效的，但“（]”和“（[）]”不是。

思路：用数据结构——栈就可以实现。遍历字符串，把左括号压栈，碰到右括号就把栈的顶部元素拿出来与右括号匹配，匹配成功则顶部元素出栈，进入下一次循环，匹配不成功或者栈中无元素，则字符串不是有效闭合。直到所有元素遍历完，栈中无元素，即为有效闭合；如果所有元素遍历完了，栈中还有元素，则不是有效闭合。

基础概念

在 Java 中 Stack 类表示后进先出（LIFO）的对象堆栈。栈是一种非常常见的数据结构，它采用典型的先进后出的操作方式完成的。每一个栈都包含一个栈顶，每次出栈是将栈顶的数据取出，如下：

Stack 通过五个操作对 Vector 进行扩展，允许将向量视为堆栈。这个五个操作如下：

示例代码:

//Create the Stack instance and add a couple of elements to it
Stack stack = new Stack();
String s1 = "element 1";
String s2 = "element 2";
stack.push(s1);
stack.push(s2);
System.out.println(stack.peek());
//element 2
//Find position of a certain element
int pos = stack.search("element 1");
System.out.println(pos);
//2
System.out.println(stack.pop());
System.out.println(stack.pop());
//element 2
//element 1
System.out.println(stack.empty());
//true

参考代码：
Java

public class Solution {
    public boolean isValid(String s) {
        if(s==null || s.length()==0)
            return false;
        Stack<Character> parentheses = new Stack<Character>(); 
        for (int i = 0; i< s.length(); i++){
            char c = s.charAt(i); 
            if(c=='(' || c=='[' || c =='{')
                parentheses.push(c);
            else{
                if (parentheses.empty())
                    return false;
                if (c == ')' && parentheses.peek() != '(')
                    return false;
                if (c == ']' && parentheses.peek() !='[')
                    return false;
                if (c == '}' && parentheses.peek() !='{')
                    return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
}

参考资料
http://outofmemory.cn/code-snippet/2087/java-usage-Stack-class