stack06.java

已经编写好的数据结构课本程序可以减轻您的负担

// =============== 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;
   	}   	
}