欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构(Java)之栈(3)-括号匹配

程序员文章站 2022-07-10 20:28:59
...

给定字符串"{[()]}",判断字符串是否有效.括号必须以正确的顺序匹配,"()“和”()[]{}“是有效的但是”(]“和”([)]"不是.

思路:

①声明一个栈 Stack
②逐一遍历字符串中的每个字符
③如果是左括号就压入栈
④如果是右括号,我们看是否能和栈顶元素能与右括号匹配,匹配就出栈
⑤如果栈中为空,此字符串是一个合法的括号匹配的字符串
–栈顶元素反应了在嵌套的层次关系中,最近的需要匹配的元素

import java.util.Stack;

public class Solution {
    public boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i <s.length() ; i++) {
            //取出字符串的的字符
            char c = s.charAt(i);
            if (c == '('||c == '['||c == '{'){
                //如果是左括号,压入栈
                stack.push(c);
            } else{
                if(stack.empty()){
                    //判断栈是否为空,若为空匹配失败
                    return false;
                }
                //取出栈顶元素与此右括号匹配
                char topChar = stack.pop();
                //如果此c元素是右括号且栈顶元素不是左圆括号,则匹配失败
                if (c ==')' && topChar!='('){
                    return false;
                }
                if (c == ']'&&topChar !='['){
                    return false;
                }
                if (c == '}'&& topChar!='{'){
                    return false;
                }
            }
        }
        //遍历完成后,判断栈中是否还有元素,若没有则匹配成功
        return stack.empty();
    }
}

main方法测试:

public static void main(String[] args) {
        Solution solution = new Solution();
        String s1 = "{[]})";
        System.out.println("'"+ s1 + "/'的检验结果" + solution.isValid(s1));
        String s2 = "[([]{})]";
        System.out.println("'"+ s2 + "/'的检验结果" + solution.isValid(s2));
        String s3 = "([{}])";
        System.out.println("'"+ s3 + "/'的检验结果" + solution.isValid(s3));
        String s4 = "({[]}";
        System.out.println("'"+ s4 + "/'的检验结果" + solution.isValid(s4));
        String s5 = "({[]])";
        System.out.println("'"+ s5 + "/'的检验结果" + solution.isValid(s5));
    }

运行结果展示:
数据结构(Java)之栈(3)-括号匹配