Algorithm/Insights
Reverse Polish notation (RPN) is a mathematical notation in which every operator is placed after its operands. For example, x + y (in infix notation) is expressed in RPN as x y +
It is also known as postfix notation.
The expression can be evaluated using a stack as described below:
1. If the array has only 1 element, then return the element.
2. Traverse the string array for elements i = 0 to length of array:
a. If the element at index i is an operand, then parse it to get the value.
b. Else, pop two elements from the stack (say x and y) and perform the operation specified by the operator (for example, +) on the 2 elements in the below order and store it as the value:
y = s.pop()
x = s.pop()
value = x + y
c. We will get a value from steps a OR b, push the value on to the stack.
3. Finally, only 1 integer element is left on the stack, return it.
Example:
String Array: 5 1 2 + 4 * + 3 -
1. Initialize empty stack.
2. Since 5 is an operand, add it to the stack.
3. 1 and 2 are also operands, so add these to the stack too.
4. Next we have + operator,
5. Push the value onto the stack.
6. Next we have 4, which is an operand, so push it to the stack
7. Next we have * operator,
8. Push the value onto the stack
9. Next we have + operator,
10. Push the value 17 onto the stack
11. Next element is an operand 3, push it to the stack
12. Last, we have - operator,
Finally, all the array elements are processed, and we have 14 as the result.