stack04.java

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

// =============== Program Description ===============
// 程序名称： Stack04.java
// 程序目的： 输入一前序表达式,并计算其值。
// Written By Kuo-Yu Huang. (WANT Studio.) 
// ===================================================
import ConsoleReader.*;					// 导入已定义的数据输入类

public class Stack04
{	
	public static void main (String args[])	
	{
		StackArray Prefix = new StackArray();	// 前序表达式堆栈
		StackArray Operand = new StackArray();	// 运算量堆栈
		String 	Expression = new String();	// 声明表达式字串
   		int 	Position = 0;			// 表达式位置
   		int 	Operator1;			// 运算符
   		int 	Operand1 = 0;			// 前运算量
   		int 	Operand2 = 0;			// 后运算量
   		int 	Evaluate = 0;			// 运算结果
   		int	Token = 0;			// 输出字符

   		System.out.print("Please input the preorder expression :");
   							// 读取前序表达式存入字串
		ConsoleReader console = new ConsoleReader(System.in);
		Expression = console.readLine();

		while ( true )
   		{
   			if ( Expression.charAt(Position) < '0' )
				Prefix.Push( (int) Expression.charAt(Position));
			else
				Prefix.Push( (int) Expression.charAt(Position)-48);
			Position++;
   		 	if ( Position >= Expression.length() )
   		 		break;   		 	
		}
   							// 取出表达式堆栈的内容
    		while ( Prefix.Top != -1 )
    		{
           		Token = Prefix.Pop();		// 先取出一个数据值  		
           		
	       		if (Prefix.IsOperator(Token))	// 判断是否为运算符
               		{
		    		Operand1 = Operand.Pop();
		    		Operand2 = Operand.Pop();
		    					// 计算后运算量后存入堆栈
				Operand.Push(Operand.TwoResult(Token,Operand1,Operand2) );
              		}
            		else
                					// 存入运算量堆栈--需做ASCII码转换
	     			Operand.Push(Token);
   		}   							
   							// 取出表达式的最终结果
   		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;
	}
}