// =============== Program Description ===============
// 程式名稱： Stack03.java
// 程式目的： 輸入一中序運算式,並計算其值。
// Written By Kuo-Yu Huang. (WANT Studio.) 
// ===================================================
import ConsoleReader.*;					// 引入已定義的資料輸入類別

public class Stack03
{	
	public static void main (String args[])	
	{
		StackArray Operator = new StackArray();	// 運算子堆疊
		StackArray Operand = new StackArray();	// 運算元堆疊
		String 	Expression = new String();	// 宣告運算式字串
   		int 	Position = 0;			// 運算式位置
   		int 	Operator1;			// 運算子
   		int 	Operand1 = 0;			// 前運算元
   		int 	Operand2 = 0;			// 後運算元
   		int 	Evaluate = 0;			// 運算結果

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

		while ( true )
   		{
   							// 判斷是否為運算子
     			if ( Operator.IsOperator( (int) Expression.charAt(Position) ) )
     			{
				if ( Operator.Top != -1 )
				{
					if ( Operator.Priority( (int) Expression.charAt(Position) )
	   					<= Operator.Priority(Operator.AStack[Operator.Top]) )
	   				{
	             					// 從堆疊中取出兩個運算元和一個運算子
 	             				Operand1 = Operand.Pop();
 	             				Operand2 = Operand.Pop();
 	             				Operator1 = Operator.Pop();
	             				Operand.Push(Operand.TwoResult(Operator1,Operand1,Operand2) );
					}
	   			}
							// 存入運算子堆疊
				Operator.Push( (int) Expression.charAt(Position) );
   			}
     			else
     			{
							// 存入運算元堆疊--需做Ascii碼轉換
				Operand.Push( (int) (Expression.charAt(Position)-48) );
			}
			Position++;
   		 	if ( Position >= Expression.length() )
   		 		break;   		 	
		}
   							// 取出運算子堆疊的內容
   		while ( Operator.Top != -1 )
   		{
	 		Operator1 = Operator.Pop();
         		Operand1 = Operand.Pop();
         		Operand2 = Operand.Pop();
         						// 計算後兩運算元後存入堆疊
	 		Operand.Push( (int) Operand.TwoResult(Operator1,Operand1,Operand2) );
   		}
   							// 取出運算式最終結果
   		Evaluate = Operand.Pop();
		System.out.print("The expression [ "+Expression+" ] ");
		System.out.println("result is "+Evaluate);
	}
}

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 )
      		 	return true;  				// + - * / 運算子
      		else 
      			return false;    
	}
	
//--------------------------------------------
//        判斷運算子的優先權
//--------------------------------------------
	public int Priority(int operator)
	{
   		if ( operator == 43 || operator == 45 )		// + - 運算子
      			return 1;
      		else if ( operator == 42 || operator == 47 )	// * / 運算子
      			return 2;
      		else
      			return 0;
   	}
   	
//--------------------------------------------
//      計算任兩個運算元的值
//--------------------------------------------
	public int TwoResult(int operator,int operand1,int operand2)
	{
    		switch (operator)
    		{
      			case 43:
      				return (operand2 + operand1);
      			case 45:
      				return (operand2 - operand1);
      			case 42:
      				return (operand2 * operand1);
      			case 47:
      				return (operand2 / operand1);
    		}
    		return 0;
	}
}