如何将中缀表达式转换为后缀表达式？（How to convert an infix expression to postfix expression?）

问题描述 (Problem Description)

如何将中缀表达式转换为后缀表达式？

解决方案 (Solution)

下面的示例演示如何使用stack的概念将中缀转换为后缀表达式。

import java.io.IOException;
public class InToPost {
   private Stack theStack;
   private String input;
   private String output = "";
   public InToPost(String in) {
      input = in;
      int stackSize = input.length();
      theStack = new Stack(stackSize);
   }
   public String doTrans() {
      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();
      }
      System.out.println(output);
      return output; 
   }
   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) { 
               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) throws IOException {
      String input = "1+2*4/5-7+3/6";
      String output;
      InToPost theTrans = new InToPost(input);
      output = theTrans.doTrans(); 
      System.out.println("Postfix is " + output + '\n');
   }
   class Stack {
      private int maxSize;
      private char[] stackArray;
      private int top;
      public Stack(int max) {
         maxSize = max;
         stackArray = new char[maxSize];
         top = -1;
      }
      public void push(char j) {
         stackArray[++top] = j;
      }
      public char pop() {
         return stackArray[top--];
      }
      public char peek() {
         return stackArray[top];
      }
      public boolean isEmpty() {
         return (top == -1);
      }
   }
}

结果 (Result)

上面的代码示例将产生以下结果。

124*5/+7-36/+
Postfix is 124*5/+7-36/+

以下是将中缀表达式转换为后缀表达式的另一个示例示例。

import java.io.BufferedReader;
import java.io.InputStreamReader;
class stack { 
   char stack1[]=new char[20]; 
   int t;
   void push(char ch) { 
      t++;
      stack1[t]=ch;
   } 
   char pop() { 
      char ch;
      ch = stack1[t]; 
      t--;
      return ch;
   } 
   int pre(char ch) { 
      switch(ch) { 
         case '-':return 1;
         case '+':return 1;
         case '*':return 2;
         case '/':return 2;
      } 
      return 0;
   } 
   boolean operator(char ch) { 
      if(ch=='/'||ch=='*'||ch=='+'||ch=='-') return true; 
      else return false; 
   } 
   boolean isAlpha(char ch) { 
      if(ch>='a'&&ch<='z'||ch>='0'&&ch=='9') return true; 
      else return false; 
   } 
   void postfix(String s1) { 
      char output[]=new char[s1.length()];
      char ch;
      int p = 0,i; 
      for(i = 0;i<s1.length();i++) { 
         ch = s1.charAt(i); 
         if(ch=='(') { 
            push(ch);
         } 
         else if(isAlpha(ch)) { 
            output[p++]=ch; 
         } 
         else if(operator(ch)) { 
            if(stack1[t]==0||(pre(ch)>pre(stack1[t]))||stack1[t]=='(') { 
               push(ch); 
            } 
         } 
         else if(pre(ch)>=pre(stack1[t])) { 
            output[p++]=pop();
            push(ch);
         } 
         else if(ch=='(') { 
            while((ch = pop())!='(') { 
               output[p++]=ch;
            } 
         } 
      } 
      while(t!=0) { 
         output[p++]=pop();
      } 
      for(int j=0;j>s1.length();j++) {
         System.out.print(output[j]);    
      }
   }
}
public class Demo { 
   public static void main(String[] args)throws Exception { 
      String s;
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      stack b = new stack();
      System.out.println("Please Enter input s1ing");
      s = br.readLine();
      System.out.println("Input String is "+s);
      System.out.println("Output String is");
      b.postfix(s);
   }
}

上面的代码示例将产生以下结果。

Enter input string
124*5/+7-36/+
Input String:124*5/+7-36/+
Output String:
12*/-3/675