【每天一道算法题】动图解析栈的应用之括号匹配（附源码）

本专栏将会从基础开始，循序渐进，每天刷一道算法题，也请大家多多支持。数据结构虽然难，但只要肯坚持，一定能学好，希望大家都能够从中获益。
专栏地址: 每天一道算法题专栏 数据结构专栏
本专栏的所有代码都将更新在Gitee上，项目地址：项目地址
相关数据结构演示软件:链接地址
数据结构在线演示地址：https://visualgo.net/zh https://algorithm-visualizer.org/

准备好了吗
Let’s go!

• • 栈在括号匹配中的应用

所谓括号校验匹配就是对多种类型的括号进行正确配对的校验（包括：()、[]、{}）即([])或者[()]为正确的表达式，如果出现交叉则匹配失败，如[(])或([())则为不正确格式。下图是括号匹配的示意图，相同的数字表示所配对的括号：

从上图可以发现：

1️⃣:每出现一个右括号，就消耗一个左括号

2️⃣:最后出现的左括号最先被匹配

所以可以用栈的特点来解决该问题,算法演示如下：

代码如下:

public static boolean bracketCheck(String str){
    LinkedStack S = new LinkedStack(); //初始化一个栈
    for(int i=0;i
        //如果扫描到左括号，则入栈
        if(str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{' ){
            S.push(str.charAt(i));
        }else{
            //扫描到右括号，且当前栈空
            if(S.isEmpty()){
                return false;
            }
            //栈顶元素出栈
            char topElem = S.pop();
            //判断是否匹配
            if(str.charAt(i) == ')' && topElem != '('){
                return false;
            }
            if(str.charAt(i) == ']' && topElem != '['){
                return false;
            }
            if(str.charAt(i) == '}' && topElem != '{'){
                return false;
            }
        }
    }
    //检索完全部括号后，栈空说明匹配成功
    return S.isEmpty();
}

完整代码如下:

//链栈

import java.util.Scanner;

//结点
class LinkedNode{
    public T iData;         //数据域
    public LinkedNode next;    //指向下一个结点

    public LinkedNode(T iData) {
        this.iData = iData;
        this.next = null;
    }

    public LinkedNode(T iData, LinkedNode next) {
        this.iData = iData;
        this.next = next;
    }

    //输出用
    @Override
    public String toString() {
        return "LinkedNode{" +
                "iData=" + iData +
                ", next=" + next +
                '}';
    }
}
//链栈
class LinkedStack {
    public LinkedNode first; //链表的第一个结点

    //构造函数
    public void LinkList() {
        first = null;
    }

    //判断链栈是否为空
    public boolean isEmpty() {
        return first == null;
    }

    //push
    public void push(T data){
        LinkedNode newNode = new LinkedNode(data);
        newNode.next = first;
        first = newNode;
    }

    //pop
    public T pop(){
        if (first == null){
            System.out.println("链表为空");
            return null;
        }
        T front =  first.iData;
        first = first.next;
        return front;
    }



}


public class _002LinkStackTest {
    public static boolean bracketCheck(String str){
        LinkedStack S = new LinkedStack(); //初始化一个栈
        for(int i=0;i
            //如果扫描到左括号，则入栈
            if(str.charAt(i) == '(' || str.charAt(i) == '[' || str.charAt(i) == '{' ){
                S.push(str.charAt(i));
            }else{
                //扫描到右括号，且当前栈空
                if(S.isEmpty()){
                    return false;
                }
                //栈顶元素出栈
                char topElem = S.pop();
                //判断是否匹配
                if(str.charAt(i) == ')' && topElem != '('){
                    return false;
                }
                if(str.charAt(i) == ']' && topElem != '['){
                    return false;
                }
                if(str.charAt(i) == '}' && topElem != '{'){
                    return false;
                }
            }
        }
        //检索完全部括号后，栈空说明匹配成功
        return S.isEmpty();
    }

    public static void main(String[] args) {
//        LinkedStack integerLinkedNode = new LinkedStack();
//
//        integerLinkedNode.push(1);
//        integerLinkedNode.push(2);
//        integerLinkedNode.push(3);
//
//        while(!integerLinkedNode.isEmpty()){
//            System.out.println(integerLinkedNode.pop());
//        }
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();  //测试案例:[(())[]]
        System.out.println(bracketCheck(str));


    }
}

代码的运行结果如下: