[Leetcode] 150. Evaluate Reverse Polish Notation

150. Evaluate Reverse Polish Notation

You are given an array of strings tokensthat represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.

Each operand may be an integer or another expression.

The division between two integers always truncates toward zero.

There will not be any division by zero.

The input represents a valid arithmetic expression in a reverse polish notation.

The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

1 <= tokens.length <= 10``4

tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

How to understand?

Reverse Polish Notation is the notation without parenthesises.

From the start to end of its input tokens array, 2 numbers are ahead of 1 operator, and the operator will be used to operate the 2 numbers ahead. that's the key point.

See the operators among the integers, the solution will use it one by one to operate the operands in order.

Division is needed attention to operate, since it is going to be truncated towards zero in negative and positive result.

How to approach?

Non stack

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a / b),
            "*": lambda a, b: a * b,
        }

        current_position = 0

        while len(tokens) > 1:

            # Move the current position pointer to the next operator.
            while tokens[current_position] not in "+-*/":
                current_position += 1

            # Extract the operator and numbers from the list.
            operator = tokens[current_position]
            number_1 = int(tokens[current_position - 2])
            number_2 = int(tokens[current_position - 1])

            # Calculate the result to overwrite the operator with.
            operation = operations[operator]
            tokens[current_position] = operation(number_1, number_2)

            # Remove the numbers and move the pointer to the position
            # after the new number we just added.
            tokens.pop(current_position - 2)
            tokens.pop(current_position - 2)
            current_position -= 1

        return int(tokens[0])

using lambda function for operations.

create the current_position as 0

and while condition checking if the tokens length is longer than 1.

when the token in the tokens is a number then, move the current_position to the right side.

when it is a operator, then extract number_1, number_2 and operator using current_position.

and then use lambda function to calculate the numbers using operator.

replace the current_position as the result.

and pop the 2 number elements in tokens array.

current_position will be decremented by 1 to move it to the left side since the array length is shortened.

lastly return the first element in tokens array.

Stack

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a / b),
            "*": lambda a, b: a * b,
        }

        stack = []
        for token in tokens:
            if token in operations:
                number_2 = stack.pop()
                number_1 = stack.pop()
                operation = operations[token]
                stack.append(operation(number_1, number_2))
            else:
                stack.append(int(token))
        return stack.pop()

use lambda function for operations.

create a stack to store the numbers to operate using operators in tokens.

In for loop, use the case of if the token is the operator or number.

if it is number then append those in the stack as integer.

if it is operator, pop the 2 items from stack, the first poped item is the later number in tokens so it would have name of number_2, and the second popped item will be number_1.

this is important for the division and subtraction cases since the order of operands matter in those.

and take the operator from operations dictionary and do the math.

append the executed result to stack for later operations.

After the iteration, lastly return the stack's left element.