Java 資料結構與演算法 - 表示式解析

像 2*(3*4) 這樣的普通算術表示式，人類很容易解析，但對於演算法來說，解析這樣的表示式就比較困難了。為了簡化這個難度，可以使用兩步法來解析算術表示式。

• 將提供的算術表示式轉換為字尾表示法。

• 評估字尾表示法。

中綴表示法

普通的算術表示式遵循中綴表示法，其中運算子位於運算元之間。例如 A+B，其中 A 是第一個運算元，B 是第二個運算元，+ 是作用於這兩個運算元的運算子。

字尾表示法

字尾表示法與普通的算術表示式或中綴表示法不同，運算子位於運算元之後。例如，考慮以下示例

中綴轉字尾轉換

在研究將中綴轉換為字尾表示法的方法之前，我們需要考慮中綴表示式求值的基本知識。

• 中綴表示式的求值從左到右開始。

• 記住優先順序，例如 * 的優先順序高於 +。例如

  • 2+3*4 = 2+12.

  • 2+3*4 = 14.

• 使用括號覆蓋優先順序，例如

  • (2+3)*4 = 5*4.

  • (2+3)*4= 20.

現在讓我們手動將簡單的中綴表示式 A+B*C 轉換為字尾表示式。

現在讓我們使用棧將上述中綴表示式 A+B*C 轉換為字尾表示式。

現在讓我們看另一個例子，使用棧將中綴表示式 A*(B+C) 轉換為字尾表示式。

演示程式

現在我們將演示使用棧將中綴表示式轉換為字尾表示式，然後評估字尾表示式。

package com.tutorialspoint.expression;

public class Stack {

   private int size;           
   private int[] intArray;     
   private int top;            

   //Constructor
   public Stack(int size){
      this.size = size;           
      intArray = new int[size];   
      top = -1;                   
   }

   //push item on the top of the stack
   public void push(int data) {
      if(!isFull()){
         //increment top by 1 and insert data
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

   //pop item from the top of the stack
   public int pop() {
      //retrieve data and decrement the top by 1
      return intArray[top--];        
   }

   //view the data at top of the stack
   public int peek() {       
      //retrieve data from the top
      return intArray[top];
   }

   //return true if stack is full
   public boolean isFull(){
      return (top == size-1);
   }

   //return true if stack is empty
   public boolean isEmpty(){
      return (top == -1);
   }
}

InfixToPostFix.java

package com.tutorialspoint.expression;

public class InfixToPostfix {
   private Stack stack;
   private String input = "";
   private String output = "";

   public InfixToPostfix(String input){
      this.input = input;
      stack = new Stack(input.length());
   }

   public String translate(){
      for(int i=0;i<input.length();i++){
         char ch = input.charAt(i);
            switch(ch){
               case '+':
               case '-':
                  gotOperator(ch, 1);
                  break;
               case '*':
               case '/':
                  gotOperator(ch, 2);
                  break;
               case '(':
                  stack.push(ch);
                  break;
               case ')':
                  gotParenthesis(ch);
                  break;
               default:
                  output = output+ch;            
                  break;
          }
      }

      while(!stack.isEmpty()){
         output = output + (char)stack.pop();
      }       

      return output;
   }   

      //got operator from input
      public void gotOperator(char operator, int precedence){
      while(!stack.isEmpty()){
         char prevOperator = (char)stack.pop();
         if(prevOperator == '('){
            stack.push(prevOperator);
            break;
         }else{
            int precedence1;
            if(prevOperator == '+' || prevOperator == '-'){
               precedence1 = 1;
            }else{
               precedence1 = 2;
            }

            if(precedence1 < precedence){
               stack.push(Character.getNumericValue(prevOperator));
               break;                        
            }else{
               output = output + prevOperator;
            }                
         }   
      }
      stack.push(operator);
   }

   //got operator from input
   public void gotParenthesis(char parenthesis){
      while(!stack.isEmpty()){
         char ch = (char)stack.pop();
         if(ch == '('){                
            break;
         }else{
            output = output + ch;               
         }   
      }        
   } 
}

PostFixParser.java

package com.tutorialspoint.expression;

public class PostFixParser {
private Stack stack;
private String input;

public PostFixParser(String postfixExpression){
   input = postfixExpression;
   stack = new Stack(input.length());
}

   public int evaluate(){
      char ch;
      int firstOperand;
      int secondOperand;
      int tempResult;

      for(int i=0;i<input.length();i++){
         ch = input.charAt(i);

         if(ch >= '0' && ch <= '9'){
            stack.push(Character.getNumericValue(ch));
         }else{
            firstOperand = stack.pop();
            secondOperand = stack.pop();
            switch(ch){
               case '+':
                  tempResult = firstOperand + secondOperand;
                  break;
               case '-':
                  tempResult = firstOperand - secondOperand;
                  break;
               case '*':
                  tempResult = firstOperand * secondOperand;
                  break;
               case '/':
                  tempResult = firstOperand / secondOperand;
                  break;   
               default:
                  tempResult = 0;
            }
            stack.push(tempResult);
         }
      }
      return stack.pop();
   }       
}

PostFixDemo.java

package com.tutorialspoint.expression;

public class PostFixDemo {
   public static void main(String args[]){
      String input = "1*(2+3)";
      InfixToPostfix translator = new InfixToPostfix(input);
      String output = translator.translate();
      System.out.println("Infix expression is: " + input);
      System.out.println("Postfix expression is: " + output);

      PostFixParser parser = new PostFixParser(output);
      System.out.println("Result is: " + parser.evaluate());
   }
}

如果我們編譯並執行上述程式，它將產生以下結果：

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5