Scenario
We are used to writing mathematical expressions in the form of 1 + 2 * 3. This type of notation is called an infix. Using infix notation, an operator is always in between two operators. There is a different notation called postfix, where the operator is after the operands. Examples of such expressions are shown in the following table:
| Infix expression | Postfix expression |
| 1 + 2 | 1 2 + |
| 1 + 2 * 3 | 1 2 3 * + |
| (1 + 2) * 3 | 1 2 + 3 * |
| 5 + 4 / 2 * 3 | 5 4 2 / 3 * + |
Aim
Implement an algorithm that accepts a postfix string, evaluates it, and returns the result.
Prerequisites
- Implement the following method in the class which is available on the
GitHub repository for the book at the following path:
https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson2/activity/postfix/EvalPostfix.java
public double evaluate(String postfix)
- Assume the operator and operands are always separated by a space, such as "5 2 +". The input string will look like the examples shown in the preceding table.
If you have your project set up, you can run the unit test for this activity by running the following command:
gradlew test --tests com.packt.datastructuresandalg.lesson2.activity.postfix*
The solution becomes a lot simpler if you use one of the data structures we studied in this section.
gradlew test --tests com.packt.datastructuresandalg.lesson2.activity.postfix*
The solution becomes a lot simpler if you use one of the data structures we studied in this section.
Steps for Completion
- Use the stack data structure to solve this problem
- Start processing the expression from left to right
- If you encounter a numeric operand, push it on the stack
- If you encounter an operator, pop two items from the stack and perform the operation accordingly (addition, subtraction, and so on) and push the result back on the stack
- Once you have processed the entire expression, the result should be the on the top of the stack