【牛客】括号序列

题目描述:
给出一个仅包含字符’(’,’)’,’{’,’}’,’[‘和’]’,的字符串,判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭,"()“和”()[]{}“都是合法的括号序列,但”(]“和”([)]"不合法。
解题思路:
对于括号匹配问题,采用栈解题比较容易一些。具体步骤如下所示:
1.首先定义一个字符栈,利用循环遍历字符串;
2.判断如果是左括号,则将当前字符压入栈中;
3.如果不符合条件上述2,判断当前栈是否为空,如果为空则说明右括号多了,直接返回false
4.接下来判断当前字符是否与栈顶字符相互匹配,如果匹配则弹出栈顶元素;
5.最后判断栈是否为空,如果为空则说明所有括号匹配成功,返回true
完整代码如下所示:

public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<>();//定义一个栈
        for(int i = 0; i < s.length();i++){
            if(s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '['){
                stack.push(s.charAt(i));//如果当前符号为左括号则入栈
            }else if(stack.isEmpty()){
                return false;//既然当前括号不是左括号,判断一下此时栈是否为空,如果为空则说明是右括号多了,直接返回
            }else if( stack.peek() == '(' && s.charAt(i) == ')' ||
                     stack.peek() == '{' && s.charAt(i) == '}' ||
                     stack.peek() == '[' && s.charAt(i) == ']'){
                    //如果栈顶元素与当前字符相匹配则弹出栈顶元素
                    stack.pop();
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
}
上一篇:剑指 Offer 05. 替换空格


下一篇:leetcode-罗马数字转整数