Dsa Using Java 简明教程

DSA using Java - Parsing Expressions

像 2*(3*4) 这样的普通算术表达式对于人类来说更容易解析，但对于算法来说，解析这种表达式はかなり困难。为了解决这个困难，算法可以使用两步法来解析算术表达式。

  1. 将提供的算术表达式转换为后缀表示。

  2. Evaluate the postfix notation.

.

Infix Notation

普通的算术表达式遵循中缀表示法，其中运算符位于操作数之间。例如，A+B 其中 A 是第一个操作数，B 是第二个操作数，+ 是作用于这两个操作数的运算符。

Postfix Notation

后缀表示法不同于普通算术表达式或中缀表示法，其中运算符位于操作数后面。例如，考虑以下示例：

Sr.No

Infix Notation

Postfix Notation

1

A+B

AB+

2

(A+B)*C

AB+C*

3

A*(B+C)

ABC+*

4

A/B+C/D

AB/CD/+

5

(A+B)*(C+D)

AB+CD+*

6

((A+B)*C)-D

AB+C*D-

Infix to PostFix Conversion

在研究将中缀转换为后缀表示法的方法之前，我们需要考虑中缀表达式求值的基本原理。

  1. 中缀表达式的求值从左到右开始。

  2. 记住优先级，例如 * 的优先级高于 +。 例如

2+3*4 = 2+12.2+3*4 = 14。

  1. 使用括号覆盖优先权，例如

(2+3)*4 = 5*4。(2+3)*4= 20。

现在让我们手动将一个简单の中缀表达式 A+B*C 转换成一个后缀表达式。

Step

Character read

到目前为止解析的中缀表达式

到目前为止开发了后缀表达式

Remarks

1

A

A

A

2

+

A+

A

3

B

A+B

AB

4

*

A+B*

AB

+ 无法复制，因为 * 的优先级更高。

5

C

A+B*C

ABC

6

A+B*C

ABC*

复制 * 因为有两个操作数 B 和 C

7

A+B*C

ABC*+

复制 + 因为有两个操作数 BC 和 A

现在，让我们使用栈将上述中缀表达式 A+B*C 转换为后缀表达式。

Step

Character read

到目前为止解析的中缀表达式

到目前为止开发了后缀表达式

Stack Contents

Remarks

1

A

A

A

2

+

A+

A

+

将 + 运算符压入栈中。

3

B

A+B

AB

+

4

*

A+B*

AB

+*

运算符 * 的优先级高于 。将 * 运算符压入栈中。否则， 会弹出。

5

C

A+B*C

ABC

+*

6

A+B*C

ABC*

+

没有更多的操作数，弹出 * 运算符。

7

A+B*C

ABC*+

Pop the + operator.

现在让我们看另一个示例，通过使用栈将中缀表达式 A*(B+C) 转换为后缀表达式。

Step

Character read

到目前为止解析的中缀表达式

到目前为止开发了后缀表达式

Stack Contents

Remarks

1

A

A

A

2

*

A*

A

*

将 * 运算符压入栈中。

3

(

A*(

A

*(

将 ( 压入栈中。

4

B

A*(B

AB

*(

5

+

A*(B+

AB

*(+

将 + 压入栈中。

6

C

A*(B+C

ABC

*(+

7

)

A*(B+C)

ABC+

*(

Pop the + operator.

8

A*(B+C)

ABC+

*

Pop the ( operator.

9

A*(B+C)

ABC+*

弹出其余运算符。

Demo program

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

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