1. WIKI教程
2. Java示例
3. 如何将中缀表达式转换为后缀表达式？(How to convert an infix expression to postfix expression?)

如何将中缀表达式转换为后缀表达式？(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