Solution: Evaluate Reverse Polish Notation

Statement#

Given an arithmetic expression in a Reverse Polish Notation (RPN) as an array of strings, tokens, your task is to evaluate and return the value of the given expression.

Points to consider:

• Valid operators are +, -, *, and /.

• Each operand can be an integer or another expression.

• The division between two integers should truncate toward zero.

The given Reverse Polish Notation expression is guaranteed to be valid. This ensures that the expression always evaluates to a result and that there are no division-by-zero operations.

Constraints:

• $1 \leq$ tokens.length $\leq 10^4$

• tokens[i] is either an operator (+, -, *, or /) or an integer in the range $[-200, 200]$.

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

A naive approach to solving this problem involves a sequential iteration through the array of given tokens. We use a pointer to traverse the array, and whenever an operator is encountered, it is applied to the two preceding operand values. Subsequently, the two operands and one operator are replaced in the tokens array by the result value. This process is repeated until only one token remains, representing the expression’s final result.

However, this approach has its drawbacks. It repeatedly modifies the array, which can result in inefficient time complexity, particularly in cases with a large number of tokens. The time complexity can be quadratic, $O(n^2)$, where $n$ represents the number of elements in the tokens array. Additionally, the space complexity remains constant, $O(1)$.

Optimized approach using stacks#

Evaluating an arithmetic expression in Reverse Polish Notation involves systematically processing operators and operands to compute the final result. This is accomplished by utilizing a stack data structure, which facilitates the storage and retrieval of intermediate values during the evaluation process.

We begin by creating an empty stack to store operands and intermediate results. This stack acts as a temporary storage area for values that are used in the ongoing calculation. As we iterate through the tokens array, we encounter both operators and operands. Each token plays a significant role in forming the sequence of operations that lead to the ultimate result.

When an operator token is encountered, it signifies that a mathematical operation must be performed on the operands. The use of a stack ensures that the order of the operands for each operation is preserved, aligning with the principles of Reverse Polish Notation. By popping the two most recently added operands and appending the result back into the stack, we capture the interim result and maintain the sequential evaluation. Here, we pop number2 before number1 to ensure that the order of operands for subtraction and division is as specified by Reverse Polish Notation. This order preserves the correctness of the arithmetic operation.

In our calculations, when we divide one number by another, we need to make sure that the result is a whole number. If it’s not, we have to remove any extra decimal parts. To do this, we use the math.trunc() function. This ensures that our division follows the truncate rule specified in the problem statement, making our calculations accurate and in line with the problem’s requirements.

The systematic stacking of interim results ensures that the final value residing on the stack accurately represents the outcome of the expression. This value is ready to be popped and returned as the final evaluation result.

In essence, the proficient utilization of a stack effectively manages the sequence of operations as dictated by Reverse Polish Notation. Each step; pushing operands, executing arithmetic operations, and popping outcomes contributes cohesively to attaining the final result.

Let’s look at the following illustration to get a better understanding of the solution:

Solution summary#

The algorithm can be summarized in the following steps:

• Initialize an empty stack and start iterating through the tokens array from left to right.

• For operands, convert them to integers and push them onto stack.

• When an operator is encountered, pop the top two elements from stack, perform the operation, and push the result back onto stack.

• Continue processing tokens until the final result remains on stack, representing the expression’s outcome.

Time complexity#

The time complexity is $O(n)$, where $n$ is the number of elements in the input tokens.

Space complexity#

The space complexity of this solution is $O(n)$, where $n$ is the space required by stack.