After last weeks blog post, What is a Stack and how to Create one in Java, I figured it would be nice to give a practical example of using a stack in Java.
Reverse Polish Notation (also known as Postfix Notation) is a different way to write mathematical expressions. Normally, we use Infix notation to write algebraic expressions, where operators are between operands. While RPN expressions may be difficult to understand at first, they simplify algebraic expressions due to RPN doing away with parenthesis and the order of operations.
In RPN, the operators follow the operands. For example 3 + 2 becomes 3 2 +, 5 / 3 becomes 5 3 /, and so on. If we have 3 + 5 * 2 [written more clearly with parenthesis as 3 + (5 * 2)], can be written in RPN as 3 5 2 * +. The following shows the flow of solving this RPN expression.
Is it clear why a stack would come in handy when solving this programmatically? Consider how we are solving this — starting from the left, look for the first operator, then apply that operation to the two numbers preceding it. This animation will show you step by step how a stack is used to solve it:
Implementing the Solution in Java
This solution follows exactly the same logic as the explanation above, with the addition of parsing the input string. Note that I am using my own stack, but you can use Java’s stack in its place.
This calls the operate method. This helper returns the result of a two operand expression. This could have been a switch, but I find this way cleaner.
Then I made a small CLI so that we can test the calculator:
Here you can see me input the same expression as above, plus a few more to test the app:
Hopefully this post showed you how helpful stacks can be when solving problems.
You can find all source code here. Thanks for reading.