## 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.