Coding Interview Questions | Reverse Polish Notation

January 13th, 2024

Reverse Polish Notation Problem Introduction:

This summary will talk about my solution to the reverse polish notation problem as seen on leetcode here.

How do you solve the Reverse Polish Notation Problem using a Stack?

Solution:

const evaluateExpression = (a: number, b: number, operator: string) => {
  if (operator === "/") {
    return Math.trunc(a / b);
  }

  if (operator === "*") {
    return a * b;
  }

  if (operator === "+") {
    return a + b;
  }

  return a - b;
};

function evalRPN(tokens: string[]): number {
  const operatorSet = new Set(["/", "*", "+", "-"]);
  const numberStack: number[] = [];

  for (const token of tokens) {
    // Token is a number
    if (!operatorSet.has(token)) {
      numberStack.push(parseInt(token));
      continue;
    }

    const secondNumber = numberStack.pop()!;
    const firstNumber = numberStack.pop()!;

    const total = evaluateExpression(firstNumber, secondNumber, token);
    numberStack.push(total);
  }

  return numberStack.pop()!;
}

Reverse Polish Notation Solution Summary:

Below is a breakdown of the key aspects of the provided solution:

1. Expression Evaluation Function: The solution defines an evaluateExpression function responsible for performing arithmetic operations based on the provided operator. It handles addition, subtraction, multiplication, and division, ensuring proper handling of division by truncating towards zero.

2. Stack-Based Evaluation: The main evalRPN function utilizes a stack to process the given array of tokens representing a Reverse Polish Notation expression. It iterates through the tokens, pushing numbers onto the stack and performing operations when encountering operators.

3. Operand and Operator Handling: When a number is encountered, it is converted to an integer and pushed onto the stack. For operators, the top two numbers are popped from the stack, and the result of the operation is pushed back onto the stack.

4. Final Result Retrieval: The final result is obtained by popping the last element from the stack, representing the evaluated value of the Reverse Polish Notation expression.

Complexities

1. Time Complexity: The time complexity of the solution is O(n), where n is the number of tokens in the input array.
2. Space Complexity: The space complexity is O(m), where m is the maximum size of the stack during the evaluation process. The stack holds numeric values, and its size depends on the number of operands and operators in the input expression.