首页 » Java »
网站地图

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

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

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

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

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