【数据结构与算法】06. java判断字符串是否合法（栈）

一个月前，和小伙伴每周来一道算法题，一直没有总结，今天看数据结构中的栈和队列，看到了一个非常有意思的总结，什么是栈，什么是队列呢？一个经典的评论且有味的总结是这么说的，“吃饭吃多了想吐，就是栈。吃饭吃多了想拉，就是队列。” 笑死啦。 栈这种受限的线性结构，有什么神奇之处呢？

如果给你一段字符串 “{ [ ( ) ] }”,给你三种括号，且这三种括号任意嵌套，如何检查这段字符串是否合法。比如“{ [ ] ( )[ { } ] }” 或“[ { ( ) } ( [ ] ) ]”等都为合法格式，而“{ [ }( )]”或”[ ( { ) ]”为不合法的格式。通过什么样的方式检查它呢？

其实栈这种数据结构可以解决该类问题，我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

package com.fjx.stringcheck;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class ValidCheck {
    public static void main(String[] args) {
        // 定义字符串的内容
        String symbol="[(]){}";
        // 调用判断方法
        boolean result=isValid(symbol);
        System.out.print(result);
    }

    public static boolean isValid(String s){
        // 定义一个空栈
        Stack<Character> stack=new Stack<>();
        // 定义 map ,用来存放匹配的符号
        Map<Character,Character> map=new HashMap<>();
        // 将字符串存入数组arr中
        char[] arr=s.toCharArray();
        // 通过键值对的方式存储数据
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

            for (int i=0;i<arr.length;i++){
                // 如果 map 的键中不包含右边括号，也就是做左括号直接进栈
                if (!map.containsKey(arr[i])){
                    stack.push(arr[i]);
                }else {
                    // 栈顶弹出左括号，如果与右括号不匹配，则不合法，直接返回false
                    if (map.get(arr[i])!=stack.pop()){
                        return false;
                    }
                }
            }
        // 判断栈是否为空,为空,说明所有符号都已匹配完毕,全都合法，否则不合法
        if (stack.empty()){
            return true;
        }else {
            return false;
        }
    }
}

栈，你 GET 到了么？