package edu.yuliang.Data_Structure_Basics;

 import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

 /*

 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

 有效字符串需满足：

 左括号必须用相同类型的右括号闭合。

 左括号必须以正确的顺序闭合。

 注意空字符串可被认为是有效字符串。

 实现思路：

 {  [  (  )  ]  }

 1、依次遍历字符串，只要是{  [  (  都把它压入栈中

 2、如果是  )   ]    }    则先后判断栈顶元素是否为(  ，如果是则匹配成功，栈顶中  (  出栈，不是则返回false，不匹配

 3、判断栈顶元素是否为 ] ，如果是则匹配成功，栈顶中  [  出栈

 4、判断栈顶元素是否为 } ，如果是则匹配成功，栈顶中  {  出栈

 5、判断栈中是否还存在元素，如果不存在则表示之前已经全部匹配出栈，如果还存在则表示部分未匹配，判断依据，stack.isEmpty()。

  */

 import java.util.Scanner;

 import java.util.Stack;

 public class stack_match {

     public static void main(String[] args) {

         Stack stack =new Stack();

         Scanner scanner  =new Scanner(System.in);

         //char[] arr =string.toCharArray();

         //System.out.println(string.length());

         //System.out.println(arr.length);一样长

         while (scanner.hasNext()){

             String string = scanner.next();

             boolean is_match=match(string);

             System.out.println(is_match);

         }

     }

     public static Boolean match(String string){

         //申明一个stack

         Stack stack =new Stack();

         //遍历 string

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

             char c =string.charAt(i);

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

                 //左括号压入栈中

                 stack.push(c);

             }

             else {

                 //若不是就行对比

                 if(stack.isEmpty()){

                     return false;

                 }

                 char top_char= (char) stack.pop();

                 if((c==')'&&top_char=='(')||(c==']'&&top_char=='[')||(c=='}'&&top_char=='{')){

                     //若是匹配了就不用在次push里面

                 }

                 else {

                     stack.push(top_char);

                 }

             }

         }

         //最后为空的话就输出匹配

         if(stack.isEmpty())

             return true;

         return false;

     }

 }