LeetCode- Evaluate Reverse Polish Notation (Java)

Tags: , , ,

[LeetCode] Evaluate Reverse Polish Notation (RPN)

 Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

Analysis

Evaluate RPN is the second step to build a calculator. Once we have converted the infix expression into the RPN,  we need to evaluate RPN to get the result. 

The basic idea to evaluate reverse polish notation is to use a stack to process the strings.

We scan the array of the RPN expression.

  1. If the current element is a number, then push it to the stack
  2. It the current element is an operator, then pop the top two elements from the stack, calculate the value, the push it back again to the stack. 
  3. Be careful, when do pop from the stack, the first pop is the right operand, the second pop is the left operand. 

The last element in the stack is the solution for the arithmetic expression. 

See the following implementation in Java.