import java.util.Stack;

public class Solution {

    public static void main(String[] args) {

        Solution s = new Solution();

        System.out.println(s.isValid("[]{"));

    }

    public boolean isValid(String s) {

        //栈的特性：先进后出(后进先出 LIFO Last In First Out) 压栈 弹栈

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            if (c == '(' || c == '[' || c == '{') {

                stack.push(c);

            } else {

                if (stack.isEmpty())

                    return false;

                char topChar = stack.pop();

                //如果c 源值是 ( 且目标值不是反向C 表示两者并不是对立关系  返回false  匹配完必须是空

                if (c == ')' && topChar != '(') {

                    return false;

                }

                if (c == ']' && topChar != '[') {

                    return false;

                }

                if (c == '}' && topChar != '{') {

                    return false;

                }

            }

        }

        return stack.isEmpty();

    }

}