package DataStructure.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 20. 有效的括号 https://leetcode.cn/problems/valid-parentheses/
 * 题目简述:给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串中括号的顺序是否有效
 */
public class ValidParentheses {

 public static void main(String[] args) {
 System.out.println(isValid("()[]{}"));
 }

 /**
 * 思路:使用一个栈,遍历字符串,遇到左括号则入栈,遇到右括号若此时栈不为空则出栈一个元素检查是否是对应的左括号,不是则直接返回false。
 * 全部遍历完成后,若栈空,则返回true
 * 像涉及到栈、队列这类题要注意到栈可能重新为空的情况
 */
 public static boolean isValid(String s) {
 Deque<Character> stack = new ArrayDeque<>();
 for (int i=0;i < s.length();i++) {
 char nextChar = s.charAt(i);
 if (stack.isEmpty()) {
 stack.addLast(nextChar);
 continue;
 }
 char topChar = stack.getLast();
 if ((topChar == '(' && nextChar == ')') || (topChar == '[' && nextChar == ']') || topChar == '{' && nextChar == '}') {
 stack.removeLast();
 } else {
 stack.addLast(nextChar);
 }
 }
 return stack.isEmpty();
 }
}