Quick Overview

Interpret signed integers, stack manipulation commands, arithmetic, output operations, and explicit failure states in one token stream. This problem tests operand order, negative-number parsing, underflow, division by zero, and preservation of output produced before an error.

Evaluate a Small Stack-Based Integer Language

Company: Retell

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

# Evaluate a Small Stack-Based Integer Language Implement `runStackProgram(tokens)`, an interpreter for a small integer stack language. Process tokens from left to right. The top of the stack is its final element. The function returns output values and any first error as an array of strings. Decimal output values use their ordinary base-10 form. If an error occurs, append its marker after any earlier output and stop immediately. ## Instructions - An integer token, including a negative integer such as `-5`, pushes that value. - `.` and `pop` each remove the top value and append its decimal representation to the output. - `drop` removes the top value without producing output. - `dup` pushes a second copy of the top value. - `swap` exchanges the top two values. - `+`, `-`, `*`, and `/` remove the top value as `b`, remove the next value as `a`, and push `a op b`. - Integer division truncates toward zero. ## Error Semantics - If `.`, `pop`, `drop`, or `dup` has no available value, append `ERROR:UNDERFLOW` and stop. - If `swap` or an arithmetic instruction has fewer than two values, append `ERROR:UNDERFLOW` and stop. - If `/` receives `b = 0`, append `ERROR:DIVISION_BY_ZERO` and stop after removing neither operand. - If a token is neither a valid signed decimal integer nor a listed instruction, append `ERROR:INVALID_TOKEN` and stop. ## Constraints - `1 <= tokens.length <= 200,000` - Every token has length from 1 to 30. - All parsed integers and successful arithmetic results fit in a signed 64-bit integer. - The stack state left after the final token is not part of the return value. ## Example 1 ```text Input: tokens = ["10", "3", "4", "+", "-", "."] Output: ["3"] ``` The addition produces `7`; subtracting it from `10` produces `3`, which `.` emits. ## Example 2 ```text Input: tokens = ["-5", "3", "+", ".", "7", "0", "/"] Output: ["-2", "ERROR:DIVISION_BY_ZERO"] ``` The negative integer is parsed as data. The later division stops execution after the earlier output has been retained.

Overview: Interpret signed integers, stack manipulation commands, arithmetic, output operations, and explicit failure states in one token stream. This problem tests operand order, negative-number parsing, underflow, division by zero, and preservation of output produced before an error.

Read the full Retell Software Engineer interview experience this question came from

Process tokens from left to right in a stack whose top is its final element. A valid signed decimal integer pushes its value. The instructions . and pop remove and emit the top value; drop removes it; dup copies it; and swap exchanges the top two values. The arithmetic instructions +, -, *, and / remove b from the top and then a, and push a op b; integer division truncates toward zero. Return emitted decimal values and any first error as an array of strings. If an instruction lacks the required values, append ERROR:UNDERFLOW and stop. For division by zero, append ERROR:DIVISION_BY_ZERO and stop without removing either operand. For any other token, append ERROR:INVALID_TOKEN and stop. Output produced before an error is retained, and the final un-emitted stack is not returned.

Constraints

  • 1 <= tokens.length <= 200,000
  • 1 <= tokens[i].length <= 30
  • All parsed integers and successful arithmetic results fit in a signed 64-bit integer.
  • Integer division truncates toward zero.
  • The final stack state is not part of the return value.

Examples

Input: (['10', '3', '4', '+', '-', '.'],)

Expected Output: ['3']

Explanation: The first source example adds three and four, subtracts from ten, and emits three.

Input: (['-5', '3', '+', '.', '7', '0', '/'],)

Expected Output: ['-2', 'ERROR:DIVISION_BY_ZERO']

Explanation: The second source example preserves earlier output before division by zero stops execution.

Hints

  1. Check an instruction’s required stack size before changing the stack.
  2. Division by zero is checked without removing either operand.
  3. The first error stops execution, but output emitted earlier remains in the returned array.

Loading coding console...

Show the approach

Approach

Maintain a stack of exact signed 64-bit integers and an output string list. For each token, first recognize signed decimal integers and push them. Handle each stack instruction with its required arity check before mutation. For division, inspect both operands and test the divisor before removing either one, which preserves the specified zero-division behavior. Apply arithmetic in a minus b order and use truncation toward zero. Emitting instructions convert the removed value to its ordinary base-10 string. On the first underflow, zero divisor, or invalid token, append the exact marker and stop; otherwise continue through all tokens. Each successful instruction performs exactly the stack transformation in the statement, so an induction over processed tokens shows that the maintained stack and output equal the language state. The explicit stop paths then preserve every earlier output and append exactly the required first error.

Time complexity:
O(T), where T is the total number of characters across all tokens.
Space complexity:
O(n + o), where n is the token count and o is the returned output size.