Java实现中缀表达式转换为后缀表达式
实现中缀表达式转换为后缀表达式主要包含三个类，一个主函数，一个自定义栈的类，还有一个就是核心类，实现其转换。
一、自定义栈的类

package date0617;/** *@author TonyJ *@time 2011-6-17 下午02:24:47 */public class MyStack {private int maxSize;//栈的最大容量private char[] ch;//栈的数据private int top;//栈头标记public MyStack(int s) {maxSize = s;ch = new char[s];top = -1;}public void push(char c) {//入栈ch[++top] = c;}public char pop() {//出栈return ch[top--];}public char peek() {return ch[top];}public boolean isEmpty() {return top == -1;}public boolean isFull() {return top == (maxSize - 1);}public int size() {return top + 1;}public char get(int index) {return ch[index];}public void display(String str) {System.out.print(str);System.out.print(" Stack (bottom-->top): ");for (int i = 0; i < size(); i++) {System.out.print(get(i)+" ");}System.out.println();}}

二、核心实现类

package date0617;/** *@author TonyJ *@time 2011-6-17 下午02:43:48 */public class InToPost {private MyStack ms;//自定义栈private String input;//输入中缀表达式private String output="";//输出的后缀表达式public InToPost(String input) {this.input = input;int size = input.length();ms = new MyStack(size);}public String doTrans() {//转换为后缀表达式方法for (int i = 0; i < input.length(); i++) {char ch = input.charAt(i);ms.display("for " + ch + " ");switch (ch) {case '+':case '-':getOper(ch, 1);break;case '*':case '/':getOper(ch, 2);break;case '(':ms.push(ch);break;case ')':getParent(ch);break;default:output = output + ch;break;}//end switch }//end forwhile(!ms.isEmpty()){ms.display("While ");output=output+ms.pop();}ms.display("end while!!");return output;}/** * @param ch * 获得上一级字符串 */public void getParent(char ch) {while(!ms.isEmpty()){char chx=ms.pop();if(chx=='('){break;}else{output=output+chx;}}}/** * @param ch 操作符 * @param prec1 操作符的优先级 * 根据操作符的优先级判断是否入栈，及入栈的顺序 */public void getOper(char ch, int prec1) {while (!ms.isEmpty()) {//判断栈是否为空char operTop = ms.pop();if (operTop == '(') {ms.push(operTop);break;} else {int prec2;if (operTop == '+' || operTop == '-') {prec2 = 1;} else {prec2 = 2;}if (prec2 <prec1) {ms.push(operTop);break;} else {output = output + operTop;}}}// end whilems.push(ch);}}

三、主类代码

package date0617;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/** *@author TonyJ *@time 2011-6-17 下午03:44:49 */public class InfixMain {public static void main(String[] args) {String input, output;while (true) {input = getString();if ("".equals(input) || input == null) {break;}InToPost itp = new InToPost(input);output = itp.doTrans();System.out.println("Profix is " + output + "\n");}}public static String getString() {String output = "";BufferedReader br = new BufferedReader(new InputStreamReader(System.in));try {System.out.println("请输入算术表达式：");output = br.readLine();} catch (IOException e) {e.printStackTrace();}return output;}}

输入的表达式为：A*(B+C)-D/(E+F)
执行的结果如下：
请输入算术表达式：
A*(B+C)-D/(E+F)
for A Stack (bottom-->top):
for * Stack (bottom-->top):
for ( Stack (bottom-->top): *
for B Stack (bottom-->top): * (
for + Stack (bottom-->top): * (
for C Stack (bottom-->top): * ( +
for ) Stack (bottom-->top): * ( +
for - Stack (bottom-->top): *
for D Stack (bottom-->top): -
for / Stack (bottom-->top): -
for ( Stack (bottom-->top): - /
for E Stack (bottom-->top): - / (
for + Stack (bottom-->top): - / (
for F Stack (bottom-->top): - / ( +
for ) Stack (bottom-->top): - / ( +
While Stack (bottom-->top): - /
While Stack (bottom-->top): -
end while!! Stack (bottom-->top):
Profix is ABC+*DEF+/-