20.Valid Parentheses

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

括号必须以正确的顺序关闭，"()" 和 "()[]{}" 是有效的但是 "(]" 和 "([)]" 不是。

思路：

利用栈（stack）：先进后出，栈只允许访问栈顶的元素，并且只能在一端进行出栈入栈的操作。

栈存放基本类型（int,short,long,byte,float,double,boolean,char）的局部变量数据和对象的引用，但对象本身并不存放在栈中，而是放在堆中（new 出来的对象）或者常量池中（字符串常量对象放在常量池中）。

栈和常量池中的对象可以共享，堆中的对象不能共享。栈中的数据大小和生命周期是确定的，当没有引用指向数据的时候，栈数据就会消失。堆中的对象由垃圾回收器回收。

java中stack继承（extends）Vecotr，基本操作如下：

• 初始化： Stack<Character> st = new Stack<Character>;
• 入栈：st.push(item);
• 出栈：st.pop()返回栈顶元素;
• 查看栈顶对象：st.peek();返回栈顶对象
• 判断栈是否为空：st.empty();当栈中不含任何项是返回true，否则返回false;
• 返回对象在栈中的位置：st.search(Object o);返回在栈中的位置，即返回对象在栈中到最上顶端的距离。

解答（java）

import java.util.Stack;

public class Solution {
    public boolean isValid(String s){
        if(s.length()==0){
            return true;
        }
        Stack<Character> characterStack = new Stack<Character>();
        characterStack.push(s.charAt(0));

        for(int i =1;i<s.length();i++){
            if(!characterStack.empty()&&Match(characterStack.peek(),s.charAt(i))){
                characterStack.pop(); //出栈
            }else{
                characterStack.push(s.charAt(i));
            }
        }
        if(characterStack.empty()){
            return true;
        }
        return false;
    }

    private boolean Match(Character peek, char c) {
        if((peek=='('&&c==')')||(peek=='{'&& c=='}')||(peek=='['&&c==']')){
            return true;
        }
            return false;
    }
}

转载于:https://www.jianshu.com/p/3a553b3b13a4