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();
 }
}