Solved exercise: stack and recursive expression evaluator in Python

Evaluate arithmetic expressions with nested parentheses using a queue and an explicit stack, then check the result against a recursive parser in Python.

Updated on November 5, 2026

Exam Code Python Data structures Exam level Tested code

Data Structures (CS2) · Midterm examQuestion 2 · 3.0 points · 30 min

A lab calculator receives integer arithmetic expressions written on a single line. They use the operators +, -, * and /, parentheses, and optional spaces between symbols. Numbers are non-negative integers with one or more digits. Multiplication and division bind more tightly than addition and subtraction, and all four operators are left-associative.

Write a program that reads an integer n from standard input on the first line, followed by n lines, each holding one expression. For each expression, the program prints one line containing the postfix (Reverse Polish) form, with tokens separated by single spaces, followed by = and the computed value. The format is exactly postfix = value.

Rules: (1) division is integer division truncated towards zero, as in C, so 7 / 2 is 3 and (0 - 7) / 2 is -3; (2) if the expression divides by zero, print ERROR instead of the value, but still print the postfix form; (3) if the line is empty or contains only spaces, print EMPTY; (4) you may assume that non-empty expressions are well formed and that there are no unary operators (a negative value is written as 0 - x).

You must use a queue (collections.deque) for the token list, a stack (a Python list) for the operators during the conversion, and another stack for the operands during the evaluation. In addition, implement a second, recursive function that evaluates the same expression by recursive descent. The program must check that both results agree and raise an exception if they do not (this should never happen).

Sample input

3
3 + 4 * 2
(3 + 4) * 2
10 - 4 - 3

Expected output

3 4 2 * + = 11
3 4 + 2 * = 14
10 4 - 3 - = 3

Correct tokenization of the input into a queue (multi-digit numbers, operators and parentheses)

0.5

Infix-to-postfix conversion with an operator stack, respecting precedence and left associativity

1.0

Postfix evaluation with an operand stack, including integer division truncated towards zero

0.75

Equivalent recursive version (recursive descent) that produces the same result

0.5

Edge cases: empty line, a single number and division by zero

0.25

Hints

Hint 1 · How do I separate multi-digit numbers from operators?

Walk through the string with an index. When the character is a digit, keep advancing while you still see digits and store the whole run as a single token. Any other non-blank character is a one-symbol token. Put the tokens in a deque so you can consume them from the left with popleft.

Hint 2 · When should an operator be popped during the postfix conversion?

When you read an operator, keep popping while the top of the stack is another operator (not an opening parenthesis) whose precedence is greater than or equal to the current one, and send each popped operator to the output. The equality case is what makes the operators left-associative. Then push the current operator. A closing parenthesis pops until it finds the matching opening one.

Hint 3 · How should the recursive version be structured?

Think of three functions that call each other: expression (sums and differences), term (products and quotients) and factor (a number or a parenthesised expression). The grammar mirrors the precedence, because each level calls the next, tighter-binding one. Watch the division: Python's // rounds towards negative infinity, not towards zero.

Solution

Explained solution

The solution splits the problem into four small pieces. tokenize builds the token queue, to_postfix converts it using the operator stack, eval_postfix computes the value with the operand stack, and eval_recursive solves the same problem with three mutually recursive functions. main reads the input, prints each line and verifies that both routes give the same value. If you have already built a stack by hand, the bracket-matching logic here is the same idea as in array-based stack and balanced brackets in C.

The trickiest detail is division. Python's // rounds towards negative infinity, so -7 // 2 is -4, while the statement requires -3. The helper divide computes the quotient on absolute values and then restores the sign. Division by zero is signalled with a custom exception, DivisionByZero, which main catches in order to print ERROR.

import sys
from collections import deque

PREC = {'+': 1, '-': 1, '*': 2, '/': 2}


class DivisionByZero(Exception):
    pass


def tokenize(line):
    queue = deque()
    i = 0
    n = len(line)
    while i < n:
        c = line[i]
        if c.isspace():
            i += 1
        elif c.isdigit():
            j = i
            while j < n and line[j].isdigit():
                j += 1
            queue.append(line[i:j])
            i = j
        else:
            queue.append(c)
            i += 1
    return queue


def divide(a, b):
    if b == 0:
        raise DivisionByZero()
    q = abs(a) // abs(b)
    return q if (a >= 0) == (b >= 0) else -q


def apply_op(op, a, b):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    return divide(a, b)


def to_postfix(tokens):
    queue = deque(tokens)
    output = []
    stack = []
    while queue:
        t = queue.popleft()
        if t.isdigit():
            output.append(t)
        elif t == '(':
            stack.append(t)
        elif t == ')':
            while stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and PREC[stack[-1]] >= PREC[t]:
                output.append(stack.pop())
            stack.append(t)
    while stack:
        output.append(stack.pop())
    return output


def eval_postfix(postfix):
    stack = []
    for t in postfix:
        if t.isdigit():
            stack.append(int(t))
        else:
            b = stack.pop()
            a = stack.pop()
            stack.append(apply_op(t, a, b))
    return stack[0]


def eval_recursive(tokens):
    queue = deque(tokens)

    def expression():
        value = term()
        while queue and queue[0] in ('+', '-'):
            op = queue.popleft()
            value = apply_op(op, value, term())
        return value

    def term():
        value = factor()
        while queue and queue[0] in ('*', '/'):
            op = queue.popleft()
            value = apply_op(op, value, factor())
        return value

    def factor():
        t = queue.popleft()
        if t == '(':
            value = expression()
            queue.popleft()
            return value
        return int(t)

    return expression()


def main():
    lines = sys.stdin.read().split('\n')
    n = int(lines[0].strip())
    result = []
    for k in range(1, n + 1):
        line = lines[k] if k < len(lines) else ''
        tokens = list(tokenize(line))
        if not tokens:
            result.append('EMPTY')
            continue
        postfix = to_postfix(tokens)
        text = ' '.join(postfix)
        try:
            value = eval_postfix(postfix)
            if value != eval_recursive(tokens):
                raise RuntimeError('the two evaluations disagree')
            result.append(text + ' = ' + str(value))
        except DivisionByZero:
            result.append(text + ' = ERROR')
    print('\n'.join(result))


main()

tokenize scans the line with the index i. Spaces are skipped. When it finds a digit, it advances j while digits continue and appends the whole slice to the queue, so 12 is a single token. Any other character (an operator or a parenthesis) becomes a one-symbol token. If the token list ends up empty, main prints EMPTY. That is exactly what happens in the test with a blank line and a line of spaces.

to_postfix is the classic operator-stack algorithm. Numbers go straight to output. A ( is pushed. A ) pops operators to the output until it reaches its partner, which is discarded. For an operator, the inner while pops as long as the top has greater or equal precedence, and that equality is what gives left associativity. This is why the example line 10 - 4 - 3 becomes 10 4 - 3 - and evaluates to 3, not 9. Once the queue is exhausted, the remaining operators are flushed from the stack.

eval_postfix uses a second stack that holds operands. For each operator it pops b first and then a, because the first pop is the right-hand operand, which matters for - and /. It then pushes apply_op(t, a, b). At the end exactly one value remains. divide handles truncation towards zero and raises DivisionByZero, which main catches. In the test 4 / (2 - 2) the program still prints the postfix 4 2 2 - /, followed by ERROR.

eval_recursive encodes precedence in the shape of the calls: expression calls term, and term calls factor. A factor is either a number or an opening parenthesis that calls expression again, and that is where the recursion lives. The inner functions share queue through their enclosing scope. Consuming with popleft lets every call advance through the input without passing indices around. main compares both values as an internal consistency check.

The tests cover the mixed example from the statement, a single number (its postfix form is the number itself, with or without parentheses), nested parentheses with multi-digit numbers, left associativity of / in 8 / 2 / 2, truncated division of a negative value built as 0 - 7, division by zero followed by a normal line, and blank input lines.

Code and tests on GitLab

Step-by-step trace · generated by running the code

Step	token	queue	stack	output
1	3	4		3
2	+	3	+	3
3	4	2	+	3 4
4	*	1	+*	3 4
5	2	0	+*	3 4 2
6	(	6	(
7	3	5	(	3
8	+	4	(+	3
9	4	3	(+	3 4
10	)	2		3 4 +
11	*	1	*	3 4 +
12	2	0	*	3 4 + 2
13	10	4		10
14	-	3	-	10
15	4	2	-	10 4
16	-	1	-	10 4 -
17	3	0	-	10 4 - 3

Test cases

Case	Input	Expected output	Actual output	Result
Mixed example	3 3 + 4 * 2 (3 + 4) * 2 10 - 4 - 3	3 4 2 * + = 11 3 4 + 2 * = 14 10 4 - 3 - = 3	3 4 2 * + = 11 3 4 + 2 * = 14 10 4 - 3 - = 3	OK
Single number	2 42 (7)	42 = 42 7 = 7	42 = 42 7 = 7	OK
Nested parentheses and multi-digit numbers	2 ((12 + 8) * (3 + 2)) - 100 / 4 2 * (3 + (4 * (5 - 1)))	12 8 + 3 2 + * 100 4 / - = 75 2 3 4 5 1 - * + * = 38	12 8 + 3 2 + * 100 4 / - = 75 2 3 4 5 1 - * + * = 38	OK
Left associativity and truncated division	3 8 / 2 / 2 (0 - 7) / 2 7 / 2 * 2	8 2 / 2 / = 2 0 7 - 2 / = -3 7 2 / 2 * = 6	8 2 / 2 / = 2 0 7 - 2 / = -3 7 2 / 2 * = 6	OK
Division by zero	2 4 / (2 - 2) 5 + 1	4 2 2 - / = ERROR 5 1 + = 6	4 2 2 - / = ERROR 5 1 + = 6	OK
Empty line and spaces	3 1+2	EMPTY EMPTY 1 2 + = 3	EMPTY EMPTY 1 2 + = 3	OK

Actual outputs: code compiled with Python 3.13.16 and run in an isolated container on 5 November 2026.

Complexity

Let m be the number of tokens in an expression, which is at most the number of characters. Tokenizing visits each character once, so it costs O(m). The conversion pushes and pops each token at most once: O(m). Evaluating the postfix form is another single pass: O(m). The recursive version consumes each token exactly once with popleft, which is O(1) on a deque, so it is O(m) as well. For n lines the total is linear in the size of the input.

Memory is O(m) for the queue, the output list and the two stacks in the worst case. The recursive version also uses the interpreter's call stack, whose depth grows with the nesting of parentheses. In the worst case, such as ((((1)))), that depth is O(m). Exam-sized inputs will not come near Python's default recursion limit of about a thousand frames, but you should know the limit exists and that the explicit-stack version does not have it.

Common mistakes

• Popping only on strictly greater precedence: 10 - 4 - 3 is then grouped as 10 - (4 - 3) and gives 9 instead of 3, because left associativity is lost.
• Using Python's // directly for division: with negative operands it rounds towards negative infinity, so (0 - 7) / 2 would give -4 instead of -3.
• Popping operands in the wrong order during evaluation: the first pop returns the right operand b. Swapping them breaks subtraction and division.
• Treating every character as a token, which splits 12 into 1 and 2, or using list.pop(0) as a queue, which degrades the cost to O(m²).
• Forgetting to flush the operator stack after the loop, so the last operators never reach the output.
• Not discarding the opening parenthesis when a closing one arrives, which leaves a ( in the stack or in the output and corrupts the postfix form.

Variants

Add exponentiation and unary minus

Introduce ^ with the highest precedence and right associativity. In the conversion, when the current operator is ^, pop only on strictly greater precedence. In the recursive version, add a power level between term and factor that calls itself for the exponent, which produces right-to-left grouping naturally. Unary minus belongs in factor: if the token is -, return -factor().

Evaluate without building the postfix form

Use two stacks at the same time, one for operands and one for operators. Whenever an incoming operator has lower or equal precedence than the top of the operator stack, pop that operator together with two operands, apply it and push the result. This is the two-stack algorithm. It computes the value in a single pass, but it never produces the intermediate postfix notation, which in this question is part of the required output.

What the professor will ask

“Why does the recursive version need three functions instead of a single one that looks at the operator and decides what to do?”

Because precedence is encoded in the structure of the calls. A single function that consumed operators one by one could not know whether to group a multiplication that appears later before doing the current addition. With expression → term → factor, each level handles only the operators of its own priority and delegates the tighter ones to the level below. In 3 + 4 * 2, term groups 4 * 2 before expression performs the sum. The explicit stack in the postfix conversion does the same thing with a precedence table: the recursive version uses the interpreter's call stack instead of a stack of its own.

On the syllabus

In the US, the syllabus of MIT's 6.006 Introduction to Algorithms describes the course as an introduction to the common algorithms, algorithmic paradigms and data structures used to solve computational problems (MIT 6.006 syllabus). Carnegie Mellon's 15-122 Principles of Imperative Computation lists recursive and mutually recursive functions among its topics (CMU 15-122 course page), which is exactly what expression, term and factor are. Stanford's CS107 includes a lecture on the stack and the heap (Stanford CS107), useful background for the call stack that the recursive version relies on.

Outside the US, the Data Structures syllabus of the Faculty of Sciences at UNAM in Mexico lists Recursion, Stacks and Queues as separate units (UNAM syllabus). These references only show that the topic belongs to those courses; the exercise on this page is original.

Opinion · Open question

The open question for me is whether students can explain why the two evaluators agree, not just observe that they do. The program asserts equality between an explicit stack and a recursive descent, and a passing test proves nothing about understanding. If a student cannot point to where the call stack plays the role of the operator stack, the next variant, with a right-associative operator, will break them. That is the real exam: changing one rule and knowing which line moves.

Related articles from LaRebelión

Solved Exercise: Validate and Extract Data with Regex in PythonSolved exercise: a TCP text protocol with a receive buffer in PythonSolved exercise: matrix transpose, diagonals and row sums in Python

• Programming exercises
• Solved exercise: array-based stack and balanced brackets in C
• Solved exercise: count, filter and summarize a log file in Bash

Produced with AI support and reviewed by the newsroom

Byline · Chief editor · English edition · London

“Two evaluators, one answer: the mark goes to the student who can say why they agree, not to the one who copied both.”