Java 实例 - 利用堆栈将中缀表达式转换成后缀表达式

以下实例演示了如何使用堆栈进行表达式的堆栈将中缀（Infix）表达式转换成后缀（postfix）表达式：

InToPost.java 文件

  1. import java.io.IOException;
  3. public class InToPost {
  4.    private Stack theStack;
  5.    private String input;
  6.    private String output = "";
  7.    public InToPost(String in) {
  8.       input = in;
  9.       int stackSize = input.length();
  10.       theStack = new Stack(stackSize);
  11.    }
  12.    public String doTrans() {
  13.       for (int j = 0; j < input.length(); j++) {
  14.          char ch = input.charAt(j);
  15.          switch (ch) {
  16.             case '+': 
  17.             case '-':
  18.             gotOper(ch, 1); 
  19.             break; 
  20.             case '*': 
  21.             case '/':
  22.             gotOper(ch, 2); 
  23.             break; 
  24.             case '(': 
  25.             theStack.push(ch);
  26.             break;
  27.             case ')': 
  28.             gotParen(ch); 
  29.             break;
  30.             default: 
  31.             output = output + ch; 
  32.             break;
  33.          }
  34.       }
  35.       while (!theStack.isEmpty()) {
  36.          output = output + theStack.pop();
  37.       }
  38.       System.out.println(output);
  39.       return output; 
  40.    }
  41.    public void gotOper(char opThis, int prec1) {
  42.       while (!theStack.isEmpty()) {
  43.          char opTop = theStack.pop();
  44.          if (opTop == '(') {
  45.             theStack.push(opTop);
  46.             break;
  47.          }
  48.          else {
  49.             int prec2;
  50.             if (opTop == '+' || opTop == '-')
  51.             prec2 = 1;
  52.             else
  53.             prec2 = 2;
  54.             if (prec2 < prec1) { 
  55.                theStack.push(opTop);
  56.                break;
  57.             }
  58.             else
  59.             output = output + opTop;
  60.          }
  61.       }
  62.       theStack.push(opThis);
  63.    }
  64.    public void gotParen(char ch){ 
  65.       while (!theStack.isEmpty()) {
  66.          char chx = theStack.pop();
  67.          if (chx == '(') 
  68.          break; 
  69.          else
  70.          output = output + chx; 
  71.       }
  72.    }
  73.    public static void main(String[] args) 
  74.    throws IOException {
  75.       String input = "1+2*4/5-7+3/6";
  76.       String output;
  77.       InToPost theTrans = new InToPost(input);
  78.       output = theTrans.doTrans(); 
  79.       System.out.println("Postfix is " + output + '\n');
  80.    }
  81.    class Stack {
  82.       private int maxSize;
  83.       private char[] stackArray;
  84.       private int top;
  85.       public Stack(int max) {
  86.          maxSize = max;
  87.          stackArray = new char[maxSize];
  88.          top = -1;
  89.       }
  90.       public void push(char j) {
  91.          stackArray[++top] = j;
  92.       }
  93.       public char pop() {
  94.          return stackArray[top--];
  95.       }
  96.       public char peek() {
  97.          return stackArray[top];
  98.       }
  99.       public boolean isEmpty() {
  100.          return (top == -1);
  101.      }
  102.    }
  103. }

以上代码运行输出结果为：

  1. 124*5/+7-36/+
  2. Postfix is 124*5/+7-36/+