Problem · Stack
Stack Language Evaluator
Learn this problem● Medium
Retell AIFULLTIMEPHONE SCREEN
Retell AIFULLTIMEPHONE SCREENProblem 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.