使用 Java 的 DSA - 解析表达式

---

像 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) 转换为后缀表达式。

演示程序

现在我们将演示如何使用堆栈将中缀表达式转换为后缀表达式，然后计算后缀表达式。

堆栈.java

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