// =============== Program Description ===============
// 程式名稱： Stack06.java
// 程式目的： 中序運算式轉後序運算式
// Written By Kuo-Yu Huang. (WANT Studio.) 
// ===================================================
import ConsoleReader.*;					// 引入已定義的資料輸入類別

public class Stack06
{	
	public static void main (String args[])	
	{
		StackArray Operator = new StackArray();	// 運算子堆疊
		String 	Inorder = new String();		// 宣告前序運算式字串
   		int 	InPosition = 0;			// 前序運算式位置
   		int 	Operator1 = 0;			// 運算子

   		System.out.print("Please input the inorder expression :");
   							// 讀取前序運算式存入字串
		ConsoleReader console = new ConsoleReader(System.in);
		Inorder = console.readLine();

	       	System.out.print("The postorder expression is [");
		while ( true )
        	{
        						// 判斷是否為運算子
               		if  (Operator.IsOperator( Inorder.charAt(InPosition) ) )
               		{
	  			if  (Operator.Top == -1 || (char) Inorder.charAt(InPosition) == '(' )
	  						// 將運算子存到堆疊中
	       				Operator.Push( Inorder.charAt(InPosition) );
	 			else
	 			{
	       				if ( (char)Inorder.charAt(InPosition) == ')' )
	       				{       					
	       						// 取出運算子直到取出' ( '
	                 			if ( Operator.AStack[Operator.Top] != 40  )
	                 			{
	                 				Operator1 = Operator.Pop();
       							System.out.print((char)Operator1);
       						}
	       				}
	       				else
	       				{
						if ( Operator.Priority( Inorder.charAt(InPosition) )
							<= Operator.Priority( Operator.AStack[Operator.Top] )
							&& Operator.Top != -1 )
						{
		         				Operator1 = Operator.Pop();
	                 				if ( Operator1 != 40  )
	       							System.out.print((char)Operator1);
						}
						Operator.Push(Inorder.charAt(InPosition));
	       				}
	    			}
	 		}
			else
				System.out.print(Inorder.charAt(InPosition));
			InPosition++;
   		 	if ( InPosition >= Inorder.length() )
   		 		break;   			
		}

		while ( Operator.Top != -1 )	// 取出在堆疊中所有的運算子
               	{
			Operator1 = Operator.Pop();
       			System.out.print((char)Operator1);
               	}
	       	System.out.println("]");	       		       	
	}
}

class StackArray
{
	int MaxSize = 20;
	int[] AStack = new int[MaxSize];		// 宣告堆疊陣列
	int Top = -1;					// 堆疊頂端
	
//--------------------------------------------
// 存入堆疊資料
//--------------------------------------------
	public void Push(int Value)
	{
   		int i;

   		if (Top >= MaxSize)			// 判斷是否已超出堆疊最大容量
   		   System.out.println("The stack is full!!");   		
   		else
   		{			
   			Top++;				// 堆疊頂端指標+1
   			AStack[Top] = Value;		// 將資料存入堆疊中
   		}
	}
	
//--------------------------------------------
// 從堆疊中取出資料
//--------------------------------------------
	public int Pop()
	{
     		int Temp;				// 暫存從堆疊取出來的資料
     		int i;					// 迴圈計數變數

     		if (Top < 0)				// 判斷堆疊是否為空
     		{
            		System.out.println("The stack is empty!!");
            		return -1;
     		}

     		Temp = AStack[Top];			// 將取出資料暫存於變數中
     		Top--;					// 堆疊頂端指標-1
     		
     		return Temp;
	}	

//--------------------------------------------
//        判斷是否為運算子
//--------------------------------------------
	public boolean IsOperator(int Operator)
	{
    
		if ( Operator == 43 || Operator == 45
			|| Operator == 42 || Operator == 47 
			|| Operator == 40 || Operator == 41)
      		 	return true;  				// + - * / 運算子
      		else 
      			return false;    
	}
	
//--------------------------------------------
//        判斷運算子的優先權
//--------------------------------------------
	public int Priority(int operator)
	{
								// + - ( 運算子
   		if ( operator == 43 || operator == 45 || operator == 40)
      			return 1;
      		else if ( operator == 42 || operator == 47 )	// * / 運算子
      			return 2;
      		else
      			return 0;
   	}   	
}