Vintage Calculator Tape
An old office calculator has no = key and no brackets. You type a number, press Enter, type another, and then press an operator, which combines the two most recent numbers into one. To work out (2 + 1) × 3 you type 2, 1, +, 3, *.
The calculator prints every key on a paper tape. A shop found a box of old tapes, and wants to know the final number each one produced.
Your task
Write replayTape(tokens). tokens is the tape: each entry is either an integer written as a string (it may be negative, like "-5") or one of the operators "+", "-", "*", "/". An operator takes the two most recent numbers, a (older) and b (newer), and replaces them with a op b. Return the one number left at the end.
Division keeps only the whole part and rounds toward zero: 7 / 2 is 3 and -7 / 2 is -3.
replayTape(tokens: string[]) → int
Examples
tokens = ["2", "1", "+", "3", "*"]
9
2 and 1 are typed. + combines them into 3. Then 3 is typed, and * combines the two numbers waiting, 3 and 3, into 9.
tokens = ["4", "13", "5", "/", "+"]
6
4, 13 and 5 wait. / combines the two newest: 13 / 5 = 2.6, cut to 2. Now 4 and 2 wait, and + gives 6. The 4 waited the whole time for its partner.
Constraints
- 1 ≤ tokens.length ≤ 10,000
- Every tape is valid: an operator always has two numbers to use, and exactly one number is left at the end.
- No division by zero. Every number, including intermediate results, is between -2,147,483,648 and 2,147,483,647.
Start with brute force
Scan the tape for the first spot where two numbers are followed by an operator, replace those three tokens with the result, and start the scan again. Repeat until one number is left.
Each scan finds one operation and the list shrinks by only two tokens, so a tape of 10,000 tokens needs about 5,000 scans of up to 10,000 tokens each, around 50 million steps. A stack does the whole tape in one pass.
Hints
0 of 4 shown- Hint 1
In
["4", "13", "5", "/", "+"], the/uses 13 and 5, not 4. Which numbers does an operator always use? - Hint 2
An operator always takes the two numbers typed or produced most recently. The result then becomes the newest number, ready for the next operator.
- Hint 3
"The most recent one comes out first" is the rule of a stack. Also mind the order: the first number you pop is
b, the right-hand side. - Hint 4
Walk the tokens. Push numbers. On an operator, pop
b, then popa, pusha op b. For division, truncate toward zero (Math.truncin JavaScript,int(a / b)in Python). The answer is the last number on the stack.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Numbers wait until an operator arrives, and the operator always takes the newest two. That is a stack: push numbers, and let each operator pop two and push one.
Trace 4 13 5 / +:
4,13,5: push each. Stack:[4, 13, 5]./: pop b = 5, pop a = 13. 13 / 5 = 2.6, truncated to 2. Push it. Stack:[4, 2].+: pop b = 2, pop a = 4. Push 6. Stack:[6].
The tape is over and one number is left: 6.
Two traps. First, pop order: the first pop is the right operand, so 3 10 - is 3 - 10 = -7. Second, Python's // rounds down, so -7 // 2 is -4; the task wants -3, which int(-7 / 2) gives. Also check for operators by exact match, so a token like "-5" is read as a number.
function replayTape(tokens) {
const nums = [];
for (const t of tokens) {
if (t === '+' || t === '-' || t === '*' || t === '/') {
const b = nums.pop(); // newest number is the right-hand side
const a = nums.pop();
if (t === '+') nums.push(a + b);
else if (t === '-') nums.push(a - b);
else if (t === '*') nums.push(a * b);
else nums.push(Math.trunc(a / b)); // round toward zero
} else {
nums.push(Number(t));
}
}
return nums[0];
}def replay_tape(tokens):
nums = []
for t in tokens:
if t in ('+', '-', '*', '/'):
b = nums.pop() # newest number is the right-hand side
a = nums.pop()
if t == '+':
nums.append(a + b)
elif t == '-':
nums.append(a - b)
elif t == '*':
nums.append(a * b)
else:
nums.append(int(a / b)) # round toward zero, unlike //
else:
nums.append(int(t))
return nums[0]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.