java栈中缀表达式转为后缀表达式

思路：

遇到数字，则输出。

遇到操作符，入栈，在入栈前若该操作符优先级较低或与栈中优先级相同则将栈中操作符弹出，输出。

遇到左括号入栈，直到遇到右括号，将左括号之前的操作符弹出，输出。弹出左括号。

例子：

a + b * c + (d * e + f ) * g

 

输出	栈	备注
ab	+
abc	+*	*优先级大于+所以入栈
abc*+	+	+优先级小于*等于+所以* +出栈，+入栈
abc*+	+(	(具有最高优先级，入栈
abc*+de	+(*	(只有遇到)才会弹出
abc*+de*f	+(+	+优先级小于*，*出栈，+入栈
abc*+de*f+	+	遇到)将斩重元素弹出直到(
abc*+de*f+g	+*	*优先级大于+所以*入栈
abc*+de*f+g*+		最后将栈中符号全部弹出

 

代码：

栈类

package cn.edu.tju.postfix;

public class Stack {
	
	private int maxSize;
	private int top;
	private char[] stack;
	
	public Stack(int maxSize){
		this.maxSize = maxSize;
		this.stack = new char[maxSize];
		this.top = -1;
	}
	
	public void push(char c){
		stack[++top] = c;
	}
	
	public char pop(){
		return stack[top--];
	}
	
	public boolean isEmpty(){
		return top == -1;
	}
	
	public char getTop(){
		return stack[top];
	}

}

 核心实现类

package cn.edu.tju.postfix;

public class InToPost {
	

	private String input;
	private String output = "";
	private Stack stack;
	
	public InToPost(String input){
		this.input = input;
		stack = new Stack(input.length());
	}
	
	public String doTrans(){
		for(int i = 0; i < input.length(); i ++){
			char ch = input.charAt(i);
			switch(ch){
			case '*':
			case '/':
				while(!stack.isEmpty() && (stack.getTop() == '*' || stack.getTop() == '/')){
					output += stack.pop();
				}
				stack.push(ch);
				break;
			case '+':
			case '-':
				while(!stack.isEmpty() && stack.getTop() != '('){
					output += stack.pop();
				}
				stack.push(ch);
				break;
			case '(':
				stack.push(ch);
				break;
			case ')':
				char temp;
				while(!stack.isEmpty() && ((temp = stack.pop()) != '(')){
					output += temp;	
				}
				break;
			default:
				output += ch;
				break;
			}
		}
		while(!stack.isEmpty()){
			output += stack.pop();
		}
		return output;
	}
	
	

}

 客户端调用类

package cn.edu.tju.postfix;

public class Client {

	public static void main(String[] args){

		String infix = "a+b*c+(d*e+f)*g";
		//infix = "a+b-c*d+e/f";
		InToPost ip = new InToPost(infix);
		String postfix = ip.doTrans();
		System.out.println(postfix);
	}
}