Hand-Write a Stack-Based Interpreter That Evaluates Arithmetic Formulas

Design and hand-write a stack interpreter: a small program that uses a stack to carry out basic calculator operations and evaluate the numeric value of the formulas it is given. The exercise is plain coding written from scratch, and its expected scope is smaller than a full infix calculator with operator precedence and parentheses. The report does not give the exact input format, the set of operations or the error rules, so settle them with the interviewer first. A typical form is a postfix formula such as `3 4 + 2 *`, which evaluates to 14, or an equivalent list of stack instructions. ```hint Order of operands When an operation pops two values, decide which one is the left operand before you write subtraction and division. ``` ```hint Keep operations out of the loop Think about how you would add a new operation later without editing the evaluation loop itself. ``` ### Clarifying Questions - Is the input a postfix formula, a list of instructions such as push and add, or something else? Is it one formula or a program of several lines? - Which operations are required beyond addition, subtraction, multiplication and division, for example negation, duplicating the top value or swapping the top two? - Are numbers integers or decimals, and how should division round, especially with negative operands? - What should happen on malformed input: too few operands for an operation, values left over at the end, an unknown token, or division by zero? - Is the result the single value left on the stack, or should the whole stack be returned? ### What a Strong Answer Covers - A precise statement of the agreed input format and of each operation's effect on the stack - A correct single-pass evaluation loop with the right operand order for subtraction and division - Clear errors for stack underflow, leftover values, unknown tokens and division by zero, instead of crashes or silent wrong answers - A structure that adds operations through a table or registry rather than a growing chain of conditionals - Time and space complexity, and tests covering negative numbers, a lone value and every error path ### Follow-up Questions - How would you add variables, so that a formula can store a value and read it back later? - How would you accept ordinary infix formulas with precedence and parentheses while reusing this interpreter? - How would you report the position of the token that caused an error? - How would you support operations that take a different number of operands, such as unary negation or a three-operand conditional?