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

演示程序

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

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

   //将项目推送到堆栈顶部
   public void push(int data) {
      if(!isFull()){
         //将顶部增加 1 并插入数据
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

    //从堆栈顶部弹出项目
    public int pop() {
        //检索数据并将顶部减 1
        return intArray[top--];
    }
    
    //查看堆栈顶部的数据
    public int peek() {
        //从顶部检索数据
        return intArray[top];
    }
    
    //如果堆栈已满，则返回 true
    public boolean isFull(){
        return (top == size-1);
    }
    
    //如果堆栈为空，则返回 true
    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;
   }   

      //从输入中获取运算符
      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);
   }

   //从输入中获取运算符
   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