【算法与数据结构】栈的典型用法之一:括号匹配

栈的典型用法之一:括号匹配

Java

解题思路

【算法与数据结构】栈的典型用法之一:括号匹配

栈是一种“先进后出”的数据结构。

本例中,栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素。

所以我的解决方案使用栈,碰到任意左括号时入栈,否则取出栈顶元素,判断当前字符是否与栈顶元素匹配,不匹配则停止循环并返回假,否则全部循环完之后判断栈是否为空(不为空可能存在在最前面只有左括号的情况),是空则返回真,否则返回假。

代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        // 依次遍历字符串中的字符
        for (int i = 0; i < s.length(); i++) {
            char tag = s.charAt(i);

            if (tag == ‘(‘ || tag == ‘[‘ || tag == ‘{‘) {
                // 判断是为左括号则入栈
                stack.push(tag);
            } else {
                // 否则看是否匹配

                // 栈为空说明没有左括号就来了右括号,不符合规则,失败
                if(stack.isEmpty()){
                    return false;
                }

                // 取出栈顶元素,上面判断了不为空,所以没异常
                char top = stack.pop();

                // 判断栈顶元素是否与目标元素是匹配的,不匹配可以直接返回假了
                if (top == ‘(‘ && tag!=‘)‘){
                    return false;
                }else if (top == ‘[‘ && tag!=‘]‘){
                    return false;
                }else if (top == ‘{‘ && tag!=‘}‘){
                    return false;
                }
            }
        }
        // 最后判断是否还有多的没有匹配的,可以直接返回结果
        return stack.isEmpty();
    }
}

【算法与数据结构】栈的典型用法之一:括号匹配

上一篇:Go语言--结构体struct


下一篇:数据结构,数组排序