package stack;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/27 10:24
 * @description: 给定一个只包括'(', ')','{', '}', '[', ']'的字符串s，判断字符串是否有效
 * 有效字符串需满足：
 * 1、左括号必须用相同类似的右括号闭合
 * 2、左括号必须以正确的顺序闭合
 */
public class IsValid {


    //整体思想：把右括号应该对应的左括号存到map，遍历字符串，如果对应的字符串在map中的value值能匹配上栈顶就栈顶--，
    // 否则栈顶++或返回false（入栈的是一个右括号：栈为空或者和栈顶没有匹配上）
    public boolean isValid(String s) {

        //判断字符串个数的奇偶性
        int n = s.length();
        if(n%2 == 1){
            return false;
        }

        Map<Character,Character> pairs = new HashMap<Character,Character>(){{
            put(')','(');
            put(']','[');
            put('}','{');
        }};
        //java集合提供了接口Deque来实现一个双端队列，它的功能是：
        //既可以添加到队尾，也可以添加到队首
        Deque<Character> stack = new LinkedList<Character>();
        for(int i = 0;i<n;i++){
            char ch = s.charAt(i);
            if(pairs.containsKey(ch)) {   //是右括号类型
                if(stack.isEmpty() || stack.peek() != pairs.get(ch)){  //是右括号的情况下：如果栈是空的，或者栈顶没有对应的左括号闭合，则返回fasle
                    return false;
                }
                stack.pop();        //匹配上了，则把栈顶下移
            }else {   //是左括号类型
                stack.push(ch);  //放到栈顶，栈顶上移
            }

        }
        return stack.isEmpty();
    }
}