stack03.java

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

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