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