Evaluate Reverse Polish Notation (opens in a new tab) Unknown

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example

Input: tokens = ["2", "1", "+", "3", "*"]

Output: 9

Explanation: ((2 + 1) * 3) = 9

Summary

To solve this problem, we can iterate through the input tokens and use a stack to store the numbers. When we encounter an operator, we pop two numbers from the stack, apply the operator, and push the result back onto the stack. At the end, the result should be the only item left on the stack.

Solution

In TypeScript

type OperatorFn = (a: number, b: number) => number;
 
function evalRPN(tokens: string[]): number {
	const stack: number[] = [];
	const operators: Record<string, OperatorFn> = {
		'+': (a, b) => a + b,
		'-': (a, b) => a - b,
		'*': (a, b) => a * b,
		'/': (a, b) => Math.trunc(a / b),
	};
 
	for (const token of tokens) {
		if (operators[token]) {
			const b = stack.pop();
			const a = stack.pop();
			const result = operators[token](a, b);
			stack.push(result);
		} else {
			stack.push(+token);
		}
	}
 
	return stack.pop();
}

In Python

def evalRPN(self, tokens: List[str]) -> int:
	stack = []
	operators = {
		'+': lambda a, b: a + b,
		'-': lambda a, b: a - b,
		'*': lambda a, b: a * b,
		'/': lambda a, b: int(a / b),
	}
 
	for token in tokens:
		if token in operators:
			b = stack.pop()
			a = stack.pop()
			result = operators[token](a, b)
			stack.append(result)
		else:
			stack.append(int(token))
 
	return stack.pop()

Step-by-step explanation

1. Declare a type alias OperatorFn for a function that takes two numbers as arguments and returns a number. This is used to represent the operator functions in the operators object.

type OperatorFn = (a: number, b: number) => number;

2. Create an empty stack array of type number[]. This stack will be used to store numbers while evaluating the expression.

const stack: number[] = [];

3. Define an object operators with keys as operator symbols and values as corresponding OperatorFn functions. For example, the key '+' maps to the function (a, b) => a + b, which adds two numbers.

const operators: Record<string, OperatorFn> = {
	'+': (a, b) => a + b,
	'-': (a, b) => a - b,
	'*': (a, b) => a * b,
	'/': (a, b) => Math.trunc(a / b),
};

4. Iterate through the tokens array using a for-of loop. For each token:

   a. If the token is an operator symbol (i.e., it exists as a key in the operators object), then:

   i. Pop the last two numbers from the stack, and store them as b and a.
   ii. Compute the result of applying the operator function to a and b using operators[token](a, b).
   iii. Push the computed result back onto the stack.

   b. If the token is not an operator symbol (i.e., it is a number), then:

   i. Convert the token to a number using the unary plus operator (+token) and push it onto the stack.

5. After the loop, the stack should contain only one number, which is the final result of the expression. Pop and return that number as the output.

This solution is based on the idea that the Reverse Polish Notation can be evaluated using a stack, where we store numbers until we encounter an operator, then perform the corresponding operation and store the result back on the stack. By following this process, we can evaluate the entire expression in a single pass through the tokens array.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input tokens. We iterate through the input tokens once, pushing numbers onto the stack and applying operators as we go.

Space Complexity

The space complexity of this solution is O(n), as we are using a stack to store the numbers. In the worst case, the stack will store n/2 numbers, which is O(n) in terms of space complexity.