LeetCode 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.

 

终于有一道栈的题目了，首先题目看清，containing just，也就是传入的字符串只有这6种字符，括号正常匹配，包括{[]}这种也是合理的

1：凡是括号的左半边( [ {都压栈

2：如果新来的是括号的右半边：

（1）如果stack是空的，没法匹配，返回false

（2）如果stack的栈顶不是匹配的左半边，根据递归的想法，没法匹配，返回false

（3）如果stack的栈顶是匹配的左半边，直接弹出，可以想象成连连看一样，配对了自动消除

假如字符串合理，最终stack里应该都弹出，清空了

Java源码

package com.maoxiaomeng;

import java.util.Stack;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */


public class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        if (s == null || len == 0 || len % 2 != 0) {
            return false;
        }
        /**
         * ([{}])
         */
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < len; i++) {
            char current = s.charAt(i);
            if (current == '(' || current == '[' || current == '{') {
                stack.push(current);
            } else if (current == ')') {
                if (stack.isEmpty() || stack.peek() != '(') {
                    return false;
                } else {
                    stack.pop();
                }
            } else if (current == ']') {
                if (stack.isEmpty() || stack.peek() != '[') {
                    return false;
                } else {
                    stack.pop();
                }
            } else if (current == '}') {
                if (stack.isEmpty() || stack.peek() != '{') {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }

        return stack.isEmpty();
    }
}

这里要注意的是isEmpty的判断和peek()的值，在if里是有先后次序的，一开始我把isEmpty放在||的后面，那么假如字符串第一个字符为)/]/}的时候，这个时候还没有压栈，为空，调用peek()方法就会抛出异常

peek()源码如下

/**
 * Looks at the object at the top of this stack without removing it
 * from the stack.
 *
 * @return  the object at the top of this stack (the last item
 *          of the <tt>Vector</tt> object).
 * @throws  EmptyStackException  if this stack is empty.
 */
public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

必须非空才能调用