《程序猿笔试题系列》之 有效括号序列

题目

     给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

示例

输入："["返回值：false
输入："[]"返回值：true

解答

使用栈

(1)当遇到左括号：'(', '[',,'{'或者栈为空时，就将当前位置的字符入栈。

(2)如果遇到右括号时，就比对当前字符和栈顶字符是不是对应的括号。

(3)如果不对应或者栈此时失控，那么直接返回false，说明这个字符串不是合法的括号序列

(4)如果是对应的括号，那么就把栈顶的字符出栈，进行下一次循环。

最终，如果栈是空，就返回true，栈不为空，就返回false。

解答：

public boolean isValid (String s) {        // write code here        if(s == null){            return false;        }        Stack<Character> temp = new Stack<>();        for(char item :s.toCharArray()){            if(item == '['){                temp.push(']');            }else if(item == '{'){                temp.push('}');            }else if(item == '('){                temp.push(')');            }else if(temp.isEmpty() || temp.pop() != item){                //如果 还有数据 并且不是 [ { (  ,那么temp就是空的，不符合要求，或者弹出的元素不等于当前的 也不是                return false;            }        }        return temp.isEmpty();    }

欢迎关注微信公众号：Java的学习之路