intopost.java

中缀表达式转换成后缀表达式算法

package cn.com.ascent;

/**
 * 
 * 把中缀表达式转换成后缀表达式的类
 *
 */

public class InToPost {

	private StackX theStack;
	private String input;
	private String output="";
	
	public InToPost(String in){
		input=in;
		int maxSize=in.length();
		theStack=new StackX(maxSize);
	}
	
	/**
	 * 此方法要把中缀表达式转换成后缀表达式
	 */
	public String doTrans(){
		//for循环扫描输入的字符串
		for(int j=0;j<input.length();j++){
			char ch=input.charAt(j);
			switch(ch){
			case '+':
			case '-':
				gotOper(ch,1);
				break;
			case '*':
			case '/':
				gotOper(ch,2);
				break;
			case '(':
				theStack.push(ch);
				break;
			case ')':
				gotParen(ch);
				break;
			default:
				output=output+ch;
			    break;
			}
		}
		
		//把最后一个字符弹出，并放置到输入字符串的末尾。
		while(!theStack.isEmpty()){
			output=output+theStack.pop();
		}
		return output;
	}
	
	/**
	 * @param opThis
	 * @param prec1
	 * 根据扫描到的操作符和操作符得优先级来判断是否要把操作符栈的栈顶元素弹出。
	 * 不管弹出不弹出栈顶元素，都要把扫描到的操作符压入栈中。
	 * 如果扫描到的操作符为')'或者优先级小于栈顶的操作符的优先级，则表示栈顶操作符的操作可以计算了，就把
	 * 栈顶的操作符弹出，放置到输出字符串的后面。如果扫面到的是操作数，则直接放置到输出字符串的后面
	 */
	
	public void gotOper(char opThis,int prec1){
		
		while(!theStack.isEmpty()){
			char opTop=theStack.pop(); //弹出栈顶操作符
			
			if(opTop=='('){
				theStack.push(opTop); 
				break;
			}else{
				int prec2;
				if(opTop=='+'||opTop=='-')
					prec2=1;    //给操作符赋优先级
				else
					prec2=2;    //乘法和除法的操作符的优先级
				if(prec2<prec1){  //如果栈顶的操作符的优先级prec2低与扫描到的操作符优先级prec1，则不弹出栈里面的操作符
					              //也就是说目前栈里面的操作符还不能进行运算
					theStack.push(opTop);
					break;
				}else{
					output=output+opTop; 
				}
			}
		}
		theStack.push(opThis); //把新扫描到的操作符压入栈中
		
	}
	
	
	/**
	 * 取出栈中的操作符,当扫描到')'操作符的时候才调用此方法
	 * 如果此时栈中的操作符是'('则直接把栈顶操作符弹出，不做任何其他处理
	 * 如果不是'('则需要把操作符弹出并放置到结果字符串的后面。
	 */
	public void gotParen(char ch){
		while(!theStack.isEmpty()){
			char chx=theStack.pop();
			if(chx=='(')
				break;
			else
				output=output+chx;
		}
		
	}
	
	
	
	public static void main(String[] args) {
		InToPost into=new InToPost("1*2+(3-(5+3)*(1+3)-(4-1))");
     	String output=into.doTrans();
     	System.out.println(output);
     	ParsePost p=new ParsePost(output);
     	int result=p.doParse();
     	System.out.println("计算结果是："+result);
	}

}


class StackX{
	
	/**
	 * maxSize:栈的最大容量
	 * stackArray:用来实现栈结构的数组
	 * top:指向栈的顶部
	 */
	private int maxSize;
	private char[] stackArray;
	private int top;
	
	/**
	 * 
	 * @param s:初始化栈的大小为s,则栈最顶端下标为s-1；
	 */
	
	public StackX(int s){
		maxSize=s;
		stackArray=new char[s];
		top=-1;
	}
	
	/**
	 * 
	 * @param j
	 * 把数据j压入栈中，其中注意是先把top自加1，使其指向栈的顶部后在把数据
	 * 赋进去的。
	 */
	public void push(char j){
		stackArray[++top]=j;
	}
	
	/**
	 * 
	 * @return
	 * 返回栈顶的元素，其中是先返回栈顶元素后把top自减1，这样保证下次访问的时候
	 * 是访问的下一个元素，也就是把原来栈顶的元素已弹出。
	 */
	public char pop(){
		return stackArray[top--];
	}
	
	/**
	 * 
	 * @return
	 * 返回目前栈顶的元素，但并不把这个元素弹出，所以top也就没有做任何自我的处理
	 */
	public char peek(){
		return stackArray[top];
	}
	
	/**
	 * 
	 * @return
	 * 判断栈是否为空，当top==-1的时候，也就是说栈中没有任何元素了，此时栈为空
	 */
	
	public boolean isEmpty(){
		return (top==-1);
	}
	
	/**
	 * 
	 * @return
	 * 判断栈是否已经满了，因为我们是用数组结构来实现栈的，所以栈的最大下标为数组最大容量-1.、
	 * 因为数组下标是从0开始计数的。
	 */
	
	public boolean isFull(){
		return (top==maxSize-1);
	}
}


class StackY{
	
	/**
	 * maxSize:栈的最大容量
	 * stackArray:用来实现栈结构的数组
	 * top:指向栈的顶部
	 */
	private int maxSize;
	private int[] stackArray;
	private int top;
	
	/**
	 * 
	 * @param s:初始化栈的大小为s,则栈最顶端下标为s-1；
	 */
	
	public StackY(int s){
		maxSize=s;
		stackArray=new int[s];
		top=-1;
	}
	
	/**
	 * 
	 * @param j
	 * 把数据j压入栈中，其中注意是先把top自加1，使其指向栈的顶部后在把数据
	 * 赋进去的。
	 */
	public void push(int j){
		stackArray[++top]=j;
	}
	
	/**
	 * 
	 * @return
	 * 返回栈顶的元素，其中是先返回栈顶元素后把top自减1，这样保证下次访问的时候
	 * 是访问的下一个元素，也就是把原来栈顶的元素已弹出。
	 */
	public int pop(){
		return stackArray[top--];
	}
	
	/**
	 * 
	 * @return
	 * 返回目前栈顶的元素，但并不把这个元素弹出，所以top也就没有做任何自我的处理
	 */
	public int peek(){
		return stackArray[top];
	}
	
	/**
	 * 
	 * @return
	 * 判断栈是否为空，当top==-1的时候，也就是说栈中没有任何元素了，此时栈为空
	 */
	
	public boolean isEmpty(){
		return (top==-1);
	}
	
	/**
	 * 
	 * @return
	 * 判断栈是否已经满了，因为我们是用数组结构来实现栈的，所以栈的最大下标为数组最大容量-1.、
	 * 因为数组下标是从0开始计数的。
	 */
	
	public boolean isFull(){
		return (top==maxSize-1);
	}
}



/**
 * 
 * 计算转换后的后缀表达式
 *
 */
class ParsePost{
	private StackY stack;
	private String input;
	
	public ParsePost(String in){
		input=in;
		stack=new StackY(input.length());
	}
	
	public int doParse(){
		
		char ch;
		int j;
		int num1,num2,interAns;
		for(j=0;j<input.length();j++){
			ch=input.charAt(j);
			if(ch>='0'&& ch<='9'){
				stack.push((int)(ch)-'0');
			}
			else{
				
				num2=stack.pop();
				num1=stack.pop();
				switch(ch){
				case '+':
					interAns=num1+num2;
					
					break;
				case '-':
					interAns=num1-num2;
					break;
				case '*':
					interAns=num1*num2;
					
					break;
				case '/':
					interAns=num1/num2;
					break;
				default:
					interAns=0;		
				}
				stack.push(interAns);
			}
		}
		
		interAns=stack.pop();
		return interAns;
	}
}