Stack Language Evaluator
Updated
Problem statement
Evaluate program, a whitespace-separated sequence of tokens, using an initially empty integer stack. Read tokens from left to right:
- An integer token pushes that integer. Its grammar is an optional minus sign followed by one or more decimal digits, so
-5is a number while-is an operator. - Each of
+,-,*and/pops the top value as the right operand, then pops the next value as the left operand, and pushes the arithmetic result. Integer division truncates toward zero. duppushes a copy of the current top value.swapexchanges the top two values.popanddropboth discard the top value without producing output..removes the top value and appends it to the output sequence.
Return only the values emitted by ., in encounter order. Values left on the stack at the end are not output automatically. An empty or whitespace-only program returns an empty array.
Programs are valid: each operator has enough stack operands, every token is recognized, and no division uses a zero divisor. There are no variables, branches or loops.
Function
evaluateStackProgram(program: String) → long[]Examples
Example 1
program = "1 2 swap . ."return = [1,2]The stack is initially [1, 2], from bottom to top. After swap it is [2, 1]. The two output tokens remove 1 and then 2.
Example 2
program = "-5 3 + ."return = [-2]The token -5 pushes a negative integer. Adding 3 produces -2, which the dot token emits and removes.
Constraints
0 <= program.length <= 20000and there are at most2000tokens.- Token separators are ASCII spaces, tabs, line feeds or carriage returns; leading, trailing and repeated separators are allowed.
- Every literal and every intermediate stack value is in
[-10^12, 10^12]. - Every operation satisfies its operand and nonzero-divisor requirements.
More Retell AI Phone Screen questions
Similar questions at other companies
- Adjacent Pair and Run RemovalWhatNot · PHONE SCREENWhatNot interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Multiline Text Editor with Cursor MovementDatologyAI · PHONE SCREEN
- Run a Stack Language InterpreterJane Street · PHONE SCREENJane Street interview questions
- Trace Nested Object Destruction OrderArista Networks · PHONE SCREENArista Networks interview questions
- Text Editor, Part 2: Undo and RedoOpenAI · PHONE SCREENOpenAI interview questions
- Text Document HistoryNotion · PHONE SCREEN · ONSITE INTERVIEWNotion interview questions
- One-Dimensional Candy CrushBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Trace Events from Stable Whole-Stack StatesAnthropic · ONSITE INTERVIEWAnthropic interview questions
- Most Frequent Call Path in Interleaved LogsRoblox · ONSITE INTERVIEWRoblox interview questions