如何将中缀表达式转换为后缀表达式（Java 版）

问题描述

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

解决方案

以下示例演示了如何使用堆栈的概念将中缀表达式转换为后缀表达式。

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);
      }
   }
}

结果

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

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