0146MediumArrayMathStack

Postfix Tape Total

Tracked in this browser only

Trains the technique from

LeetCode 150Evaluate Reverse Polish Notation

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A machinist's paper-tape calculator writes its keystrokes in postfix order: values are typed first, and an operator key is pressed only once both values it will work on already sit on the tape. The finished tape arrives as tokens, one keystroke per entry. An entry is either a whole number in decimal, possibly carrying a minus sign, or one of the four keys "+", "-", "*", "/".

Replay the tape and report the single value that remains when the last keystroke has been handled.

An operator key takes the two most recently produced values. The one produced earlier is its left operand.
The divide key drops the fractional part and pulls the quotient toward zero, so a quotient of -3.7 lands on -3.
Every tape you are given is well formed: each operator key finds two values waiting, no divide key ever meets a zero on its right, and every value produced along the way fits in a signed 32-bit register.

Examples

Example 1

Input: tokens = ["5", "2", "-"]
Output: 3

The minus key takes 5 as its left operand and 2 as its right, leaving 3 on the tape.

Example 2

Input: tokens = ["-7", "2", "/"]
Output: -3

A true quotient of -3.5 is pulled toward zero, so the tape keeps -3 rather than -4.

Example 3

Input: tokens = ["8", "3", "+", "2", "*", "5", "-"]
Output: 17

The tape builds 11, doubles it to 22, then subtracts 5.

Constraints

1 <= tokens.length <= 10^4
Each entry of tokens is one of "+", "-", "*", "/", or a whole number from -200 through 200.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def eval_r_p_n(tokens: list[str]) -> int:

Java

public int evalRPN(String[] tokens)

The intended approach

Time O(n)Space O(n)

Push each value onto a stack as it is read. An operator key pops its right operand first and its left operand second, combines them, and pushes the result back, which is exactly the order the tape implies. Division is done on magnitudes and re-signed so the quotient leans toward zero.

Pythonentry point: eval_r_p_n

def eval_r_p_n(tokens):
    keys = {'+', '-', '*', '/'}
    stack = []
    for tok in tokens:
        if tok in keys:
            right = stack.pop()
            left = stack.pop()
            if tok == '+':
                stack.append(left + right)
            elif tok == '-':
                stack.append(left - right)
            elif tok == '*':
                stack.append(left * right)
            else:
                size = abs(left) // abs(right)
                stack.append(size if (left < 0) == (right < 0) else -size)
        else:
            stack.append(int(tok))
    return stack[-1]

The obvious version

Read the tape backwards with a recursive descent: the last keystroke is the outermost operation, and each operator recursively claims its right subtree and then its left. No stack of values is ever maintained.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_replay_tape(tokens):
    keys = ('+', '-', '*', '/')
    cursor = [len(tokens) - 1]

    def take():
        tok = tokens[cursor[0]]
        cursor[0] -= 1
        if tok not in keys:
            return int(tok)
        right = take()
        left = take()
        if tok == '+':
            return left + right
        if tok == '-':
            return left - right
        if tok == '*':
            return left * right
        size = abs(left) // abs(right)
        return size if (left < 0) == (right < 0) else -size

    return take()

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in