leetcode 20 有效的括号——栈

一、题目描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

二、解题思路与代码

这是一道简单题，初看题目想了几种方法：双指针、递归、动态规划，但是都无从下手，最后瞟了眼题解，嘿嘿。思想还是很简单的，用栈先进先出的特性来解题，思路如下：
1.遍历字符串，将所有左括号入栈，遇到右括号时将栈顶元素弹出，判断是否匹配，若不匹配则返回false，匹配则继续遍历。
2.遍历完成后判断栈是否为空，不为空则表明没有完全匹配，返回false。
注意，遍历前可以先将奇数长度的字符串排除。

	public boolean isValid(String s) {
        if (s == null) {
            return false;
        }
        if (s.length() % 2 != 0) {
            return false;
        }
        Deque<Character> stack = new ArrayDeque<>();
       
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ')' || ch == ']' || ch == '}') {
                boolean isSame = isTopSame(ch, stack);
                if (!isSame) {
                    return false;
                }
            } else {
                stack.push(ch);
            } 

        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }

    private boolean isTopSame(char ch, Deque<Character> stack) {
    // 当stack无元素时，pop()方法会抛出NoSuchElementException，若要使用pop()需要先为栈判空，简易起见使用poll()。
        Character top = stack.poll(); 
        if (top == null) {
            return false;
        }
        if (top == '(') {
            top = ')';
        } else if (top == '[') {
            top = ']';
        } else {
            top = '}';
        }
        if (top != ch) {
            return false;
        }
        return true;
    }

三、注意事项

Java中有Stack 类，但是不建议使用，往往用双端队列 ArrayDeque代替栈职能。