Intermediate Level

Implement the evaluateRpnExpression method that evaluates an arithmetic expression written in Reverse Polish Notation.

You are given tokens of an arithmetic expression in Reverse Polish Notation. Each token is either an integer or one of the operators +, -, *, and /.

Return the evaluated integer result. Division should truncate toward zero.

Example 1
Input:
tokens (string[]) = [2,1,+,3,*]
size (int) = 5
Return:
(int) 9
Example 2
Input:
tokens (string[]) = [4,13,5,/,+]
size (int) = 5
Return:
(int) 6
Example 3
Input:
tokens (string[]) = [10,6,9,3,+,-11,*,/,*,17,+,5,+]
size (int) = 13
Return:
(int) 22

Use a stack to store numbers.

When a number is found, push it onto the stack. When an operator is found, pop the last two numbers, apply the operator in the correct order, and push the result back. At the end, the stack contains the final answer.

Reverse Polish Notation does not need parentheses because the operator position defines evaluation order.

Pseudocode:

function evaluateRpnExpression(tokens, size):
    stack = empty stack
    for each token in tokens:
        if token is a number:
            push number into stack
        else:
            right = pop stack
            left = pop stack
            result = apply token to left and right
            push result into stack
    return top of stack
Run your code to see the result.