Module assignment: Stack and queue toolkit in Python

Why this assignment

The module taught stacks for the newest unfinished work, queues for arrival order, monotonic stacks for one-pass answers, and circular queues and deques for control over both ends and memory. This assignment uses all of them in one program, so the skill being tested is choosing the right one for each job.

Your program reads commands from the Input box, one per line, and answers each one. A working version teaches you to read a spec carefully, to split a problem into parts, to test each part on its own, and to combine them without breaking the parts that already work. Those habits matter more to a working programmer than any single algorithm.

Compare your output with the examples below. Speed matters too, as the rubric explains, but correctness comes first.

The specification

Your program reads commands from standard input. Standard input is the Input box when you run the program on this site, and it is the keyboard when you run it in a terminal. The program reads until the input ends. Every command prints exactly one line, as the table shows.

Each command starts with a word in capital letters. The word is followed, in some cases, by a space and more text. The table lists every command.

Command	What it does	What it prints
`CHECK <text>`	checks the brackets in `<text>`	`OK`, or `BAD <index>`
`RPN <tokens>`	evaluates a postfix expression of integers and `+ - *`	the integer result, or `ERROR`
`ENQUEUE <name>`	adds a name to the back of a service queue	`OK`
`SERVE`	removes the name at the front of the service queue	the name, or `EMPTY`
`PUSH <n>`	pushes the integer `n` onto a number stack	`OK`
`POP`	removes the top number	the number, or `EMPTY`
`MIN`	reports the smallest number on the number stack	the number, or `EMPTY`

Some rules apply to every command.

Blank lines are skipped. They print nothing.
A command word that is not in the table prints UNKNOWN.
Output lines appear in the same order as their commands.
A PUSH value is a whole number. RPN works with whole numbers too, so its intermediate values can be large.

The rules for the first two commands need careful reading, so here they are in full.

CHECK. The text is everything after the single space that follows CHECK. The text may contain letters, digits, spaces and punctuation. Only the six brackets ( ) [ ] { } count for the check. Every other character is ignored by the check, but it still has a position. Positions start at 0 and count every character of the text, including the ignored ones. The command prints OK when the brackets are balanced. Otherwise it prints BAD followed by one index:

If a closing bracket arrives while nothing is open, or it does not match the most recent open bracket, the index is the position of that closing bracket.
If the text ends with brackets still open, the index is the position of the earliest one that never closed.

RPN. The tokens are separated by spaces. Each token is an integer, which may be negative, or one of +, - and *. The rules are the postfix rules from the second lesson. The command prints the final value when the expression is well formed. It prints ERROR when any of these holds: there are no tokens, an operator finds fewer than two values, a token is not a number or an operator, or the stack does not hold exactly one value at the end.

The other commands are simpler. SERVE is first in, first out. MIN must answer in constant time, which means it cannot scan the stack each time. Think about why, and read the checklist before you start.

Python note. Python's int type has no fixed size. A result that is larger than 64 bits is still exact in Python, and it does not wrap around to a smaller number the way a fixed-size integer does. For every input that fits in 64 bits, the answers are the ones the spec lists.

Sample input and output

Type this into the Input box and run your program. This is the sample that every submission must pass.

CHECK f(a[1], {b})
CHECK (]
CHECK ((x)
RPN 3 4 + 2 *
RPN 1 +
RPN 5 1 2 + 4 * + 3 -
ENQUEUE ann
ENQUEUE ben
SERVE
SERVE
SERVE
PUSH 5
PUSH 2
PUSH 7
MIN
POP
MIN
POP
MIN
POP
POP

The output must be exactly these 21 lines:

OK
BAD 1
BAD 0
14
ERROR
14
OK
OK
ann
ben
EMPTY
OK
OK
OK
2
7
2
2
5
5
EMPTY

Check a few lines by hand, so that you know what each rule means. CHECK (] has an opener at position 0 and a closer at position 1 that does not match it, so the answer is BAD 1. CHECK ((x) has two openers. The closer at position 3 matches the opener at position 1, and the opener at position 0 never closes, so the answer is BAD 0. The letter x is ignored, but it still takes up position 2.

RPN 3 4 + 2 * is (3 + 4) * 2, which is 14. RPN 1 + has an operator with only one value before it, so the answer is ERROR.

For the minimum commands: after pushing 5, 2 and 7, the smallest value is 2. Popping 7 leaves 5 and 2, and the smallest is still 2. Popping 2 leaves only 5, so MIN returns 5.

A second sample checks duplicates. Duplicate values matter, because a minimum that is removed must still leave the other copy visible.

PUSH 3
PUSH 3
POP
MIN
POP
MIN

The correct output is:

OK
OK
3
3
3
EMPTY

After two pushes of 3, one pop removes one copy, so MIN still reports 3. The second pop removes the other copy, and then MIN reports EMPTY.

Requirements checklist

Work through this list before you call the program finished. Each line is a single test you can run. Tick a box only after you have run the test and seen the expected output.

Grading rubric

Your grade depends on how many of the behaviours above work. The rubric describes three typical results. It is not a checklist to copy, and each level assumes the levels below it.

A 60% solution handles the bracket and postfix commands correctly on the sample, including their error cases. It may fail on the queue and the number stack. It should still read input until the end and print one line per command.

An 80% solution also handles ENQUEUE, SERVE, PUSH, POP and MIN on the sample, and on simple cases with no duplicate minimums. The MIN answer may scan the stack, which is slow but correct. The program prints EMPTY on empty structures.

A 100% solution passes the sample and both duplicate tests, and every item on the checklist. The MIN command runs in constant time because it uses a second stack. The code is split into functions or classes with one job each, and the comments explain the structure of each one. The program also handles blank lines and unknown commands, and it prints nothing for them.

Marks are lost quickly when a program is slow on large input, such as one with 100000 lines, because it re-reads the stack or rebuilds lists in a loop. Keep the work of each command small. In Python, the most common cause is list.pop(0), which is covered in Part 3.

Build it in four parts

The program is large, so build it in four parts. Each part below is a complete program. Run it on the input shown, and check the output before you move to the next part. When all four parts work, combine them into one program that handles every command. The combined version is the reference solution at the end of this assignment, and you should write your own first.

Each part reads standard input with for line in sys.stdin:. That loop reads one line at a time and stops at the end of the input.

Part 1: the bracket checker

The CHECK command needs one stack, of positions. A Python list works as a stack. append pushes an item onto the end, pop removes the last item, and [-1] looks at the last item without removing it. The last item is the top of the stack.

Every opener is pushed as its position in the text, not as the character. A closer pops the top and compares the bracket it found there with the closer. When the text ends, the list holds the positions of the openers that never closed. The earliest one is at index 0, the bottom of the list, so open_positions[0] is the answer for a missing closer.

Type this into the Input box:

CHECK f(a[1], {b})
CHECK (]
CHECK ((x)

import sys
 
PAIRS = {")": "(", "]": "[", "}": "{"}
 
 
def check(text):
    open_positions = []
    for i, ch in enumerate(text):
        if ch in "([{":
            open_positions.append(i)
        elif ch in PAIRS:
            if not open_positions:
                return f"BAD {i}"
            at = open_positions.pop()
            if text[at] != PAIRS[ch]:
                return f"BAD {i}"
    if open_positions:
        return f"BAD {open_positions[0]}"
    return "OK"
 
 
for line in sys.stdin:
    cmd, _, rest = line.strip().partition(" ")
    if cmd == "CHECK":
        print(check(rest))

OK
BAD 1
BAD 0

Some details in this code:

enumerate(text) gives the position and the character for each step of the loop. i is the position.
ch in "([{" checks whether ch is one of the characters in the string. Python has no separate character type, so a one-character string does this job.
PAIRS is a dictionary. It maps each closing bracket to the opening bracket it needs. PAIRS[ch] gives the opener for the closer ch.
line.strip().partition(" ") splits the line at the first space. For CHECK f(a[1], {b}) it gives "CHECK", a space, and "f(a[1], {b})". For a line that is only CHECK, the rest is an empty string, so the answer is OK.

Trace ((x) by hand. Position 0 is (, so the list becomes [0]. Position 1 is (, so the list becomes [0, 1]. Position 2 is x, which is ignored. Position 3 is ). It pops 1, which is the ( at position 1, so it matches and the list is [0]. The text ends with [0] still in the list, so the answer is BAD 0.

Part 2: the postfix calculator

The RPN command is the postfix evaluator from the second lesson, with two extra checks. The first check stops an operator from popping an empty list. The second check stops the program from accepting an expression that leaves more than one value.

The check for a valid number uses a regular expression, which is a pattern for matching text. The pattern -?[0-9]+ means an optional minus sign followed by one or more digits. Python's int() alone would also accept +3 and 1_000, and the spec does not list those forms. NUMBER.fullmatch(t) returns a match only when the whole token has the spec form.

Type this into the Input box:

RPN 3 4 + 2 *
RPN 1 +
RPN 5 1 2 + 4 * + 3 -

import re
import sys
 
NUMBER = re.compile(r"-?[0-9]+")
 
 
def rpn(expr):
    tokens = expr.split()
    if not tokens:
        return "ERROR"
    stack = []
    for t in tokens:
        if t in ("+", "-", "*"):
            if len(stack) < 2:
                return "ERROR"
            b = stack.pop()
            a = stack.pop()
            if t == "+":
                stack.append(a + b)
            elif t == "-":
                stack.append(a - b)
            else:
                stack.append(a * b)
        elif NUMBER.fullmatch(t):
            stack.append(int(t))
        else:
            return "ERROR"
    if len(stack) != 1:
        return "ERROR"
    return str(stack[0])
 
 
for line in sys.stdin:
    cmd, _, rest = line.strip().partition(" ")
    if cmd == "RPN":
        print(rpn(rest))

14
ERROR
14

Read the ERROR case closely. The line RPN 1 + has one number and then an operator. When the operator arrives, the list holds only one value, so the check len(stack) < 2 returns ERROR before any pop happens. Without that check, the second stack.pop() would raise an error on an empty list:

IndexError: pop from empty list

Python stops the program when an error is not handled. The check prevents that.

Add a test of your own: RPN 4 5 leaves two values and no operator. The final check len(stack) != 1 catches it and prints ERROR.

Note that expr.split() with no arguments splits on any run of spaces and returns an empty list for an empty string. That is why the if not tokens check handles RPN with nothing after it.

Part 3: the service queue

ENQUEUE and SERVE need a queue. The name is everything after the first space, so ENQUEUE ann smith queues the name ann smith. SERVE takes the front of the queue, or prints EMPTY when there is no one waiting.

A queue needs two ends: one for adding and one for removing. Python's collections.deque (read: "deck") is built for this. append adds at the back, and popleft removes from the front. A list can also hold a queue, but list.pop(0) moves every remaining item one place to the left each time it runs. That gets slower as the queue gets longer. deque.popleft() does not move the other items.

Type this into the Input box:

ENQUEUE ann
ENQUEUE ben
SERVE
SERVE
SERVE

import sys
from collections import deque
 
desk = deque()
 
for line in sys.stdin:
    cmd, _, rest = line.strip().partition(" ")
    if cmd == "ENQUEUE":
        desk.append(rest)
        print("OK")
    elif cmd == "SERVE":
        if desk:
            print(desk.popleft())
        else:
            print("EMPTY")

OK
OK
ann
ben
EMPTY

The check if desk: happens before popleft(). An empty deque is false in a condition, so the program prints EMPTY and does not try to remove anything. If the check were missing, the program would stop with this error:

IndexError: pop from an empty deque

The import line from collections import deque takes the deque class from the standard library, which is the set of modules that ships with Python.

Part 4: the number stack with a minimum

The MIN command is the interesting part. The simple answer scans the whole list for its smallest value. That works, but it is slow: a stack of 100000 numbers would take 100000 steps for each MIN. The better answer keeps a second stack. Whenever a value is pushed, and it is at most the current minimum, it is also pushed onto the second stack. The top of the second stack is always the current minimum.

When a value is popped, check whether it is the top of the second stack too. If it is, pop the second stack as well. The check uses <= on push, not <. That keeps duplicates, so that a second copy of the minimum survives when the first copy is popped. This is the trap that the second sample checks.

When the number stack is empty, the minimum list is empty too. While the number stack has items, the minimum list has at least one item. That is why mins[-1] is safe inside POP after the empty check.

Type this into the Input box:

PUSH 5
PUSH 2
PUSH 7
MIN
POP
MIN
POP
MIN
POP
POP

import sys
 
values = []
mins = []
 
for line in sys.stdin:
    cmd, _, rest = line.strip().partition(" ")
    if cmd == "PUSH":
        x = int(rest)
        values.append(x)
        if not mins or x <= mins[-1]:
            mins.append(x)
        print("OK")
    elif cmd == "POP":
        if not values:
            print("EMPTY")
        else:
            x = values.pop()
            if x == mins[-1]:
                mins.pop()
            print(x)
    elif cmd == "MIN":
        if mins:
            print(mins[-1])
        else:
            print("EMPTY")

OK
OK
OK
2
7
2
2
5
5
EMPTY

Trace the second stack carefully. After PUSH 5, the minimum list holds [5]. PUSH 2 is smaller, so the list becomes [5, 2]. PUSH 7 is not smaller than 2, so it is not added to the minimum list. MIN reads the last item, which is 2. POP removes 7, and 7 is not the last item of the minimum list, so nothing else changes. The next MIN still reads 2. The following POP removes 2, which is the last item of the minimum list, so that list pops too. MIN now reads 5, and the last POP removes 5 and empties both lists.

The line if x == mins[-1] compares two whole numbers with ==. Python compares the values, so this check is correct without any extra care. Java programmers should note this, because Java compares boxed Integer objects by identity with ==, which is a common bug.

Hints

Use these only when you are stuck. Try the next step on your own first.

Hint for CHECK

Push the position i, not the character. When a closer arrives, look up the character at the popped position with text[at]. A list of positions gives you the index of the problem for free, both for a mismatch and for openers that never close.

Hint for CHECK with an unmatched opener

After the loop, the list holds every opener that never closed. The earliest one was appended first, so it sits at index 0. open_positions[0] returns it.

Hint for RPN

Split the expression with split(), which handles any number of spaces. Check the operator case before the number case. Before each operator, check that the list holds at least two values. At the end, check that exactly one value remains.

Hint for MIN

Keep a second list. Append to it when a new value is less than or equal to the current minimum. When popping the main list, pop the second list too if the popped value equals its last item. Use <= so that duplicates stay.

Hint for the whole program

Read every line with for line in sys.stdin:, then split off the first word with partition(" "). Use an if or match statement on the command word, with one branch per command and an else or case _ branch that prints UNKNOWN. Keep one structure for each kind of command, so the lists and deques never share a name.

Reference solution

Try your own version before you read this. The solution is the four parts combined, with a match statement on the command word, a default case for unknown commands and one class for the number stack. The match statement needs Python 3.10 or later.

import re
import sys
from collections import deque
 
PAIRS = {")": "(", "]": "[", "}": "{"}
NUMBER = re.compile(r"-?[0-9]+")
 
 
# CHECK: a list of positions of open brackets, used as a stack.
# A position is stored, not a character, so an error index is easy to report.
def check(text):
    open_positions = []
    for i, ch in enumerate(text):
        if ch in "([{":
            open_positions.append(i)
        elif ch in PAIRS:
            if not open_positions:
                return f"BAD {i}"
            at = open_positions.pop()
            if text[at] != PAIRS[ch]:
                return f"BAD {i}"
    if open_positions:
        return f"BAD {open_positions[0]}"
    return "OK"
 
 
# RPN: a list of values used as a stack. An operator pops two and pushes one.
def rpn(expr):
    tokens = expr.split()
    if not tokens:
        return "ERROR"
    stack = []
    for t in tokens:
        if t in ("+", "-", "*"):
            if len(stack) < 2:
                return "ERROR"
            b = stack.pop()
            a = stack.pop()
            if t == "+":
                stack.append(a + b)
            elif t == "-":
                stack.append(a - b)
            else:
                stack.append(a * b)
        elif NUMBER.fullmatch(t):
            stack.append(int(t))
        else:
            return "ERROR"
    if len(stack) != 1:
        return "ERROR"
    return str(stack[0])
 
 
# PUSH, POP and MIN: a stack of numbers plus a second stack of minimums.
# The last item of mins is always the smallest value in values.
class NumberStack:
    def __init__(self):
        self.values = []
        self.mins = []
 
    def push(self, x):
        self.values.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)
 
    def pop(self):
        if not self.values:
            return None
        x = self.values.pop()
        if x == self.mins[-1]:
            self.mins.pop()
        return x
 
    def minimum(self):
        if not self.mins:
            return None
        return self.mins[-1]
 
 
def main():
    desk = deque()  # ENQUEUE and SERVE: first in, first out
    numbers = NumberStack()  # PUSH, POP and MIN
    for raw in sys.stdin:
        line = raw.strip()
        if not line:
            continue
        cmd, _, rest = line.partition(" ")
        match cmd:
            case "CHECK":
                print(check(rest))
            case "RPN":
                print(rpn(rest))
            case "ENQUEUE":
                desk.append(rest)
                print("OK")
            case "SERVE":
                if desk:
                    print(desk.popleft())
                else:
                    print("EMPTY")
            case "PUSH":
                numbers.push(int(rest))
                print("OK")
            case "POP":
                x = numbers.pop()
                print("EMPTY" if x is None else x)
            case "MIN":
                m = numbers.minimum()
                print("EMPTY" if m is None else m)
            case _:
                print("UNKNOWN")
 
 
if __name__ == "__main__":
    main()

The last two lines run main() only when the file is started directly, for example with python3 toolkit.py. If another file imports this one, main() does not start by itself. This is the usual Python way to write a program file.

print writes to standard output. When the output goes to a file or a pipe, Python keeps it in a buffer and writes it in blocks, so the program does not wait on the screen for every line.

Testing your program

Test in this order. Each step shows one kind of mistake, so you can stop as soon as a step fails. Save your program as toolkit.py and the sample input as sample.txt, then run the program with the file as its input:

python3 toolkit.py < sample.txt

Run the sample at the start of this assignment. The output must match all 21 lines exactly. A single extra space or a missing line is a failure.
Run the duplicate sample. If the output differs at the MIN lines, your second stack is not handling equal values.
Run each command on its own. Start with SERVE on an empty queue, and POP on an empty stack. These empty cases are where most lost marks come from.
Test the error cases of RPN: a lone operator, two values with no operator, an empty line after RPN, and a token such as abc.
Test a long input, such as 100000 PUSH commands followed by 100000 MIN commands. The program should finish, and the last line should match the smallest value you pushed.

What to hand in

Submit the final program, the output for the sample input, and the answer to one question: which command would break if the second stack used < instead of <=, and what input would show it? The answer is PUSH 3, PUSH 3, POP, MIN, POP. With <, the second 3 is not pushed onto the minimum list. The first POP removes the 3 from the main list and the 3 from the minimum list, so MIN prints EMPTY where the correct answer is 3. The second POP then tries to read mins[-1] from an empty list, and the program stops with an IndexError.

Summary of this module

A stack is last in, first out. A queue is first in, first out. A Python list works as a stack with append, pop and [-1], and collections.deque works as a queue with append and popleft.
A bracket checker uses a stack of positions. The stack remembers which opener is waiting, which a counter cannot do.
A postfix calculator pushes numbers and, at each operator, pops two and pushes the result.
A monotonic stack finds the next greater element for every item in one pass, with amortized constant work per item.
A minimum that must answer in constant time uses a second stack that stays in step with the first.

Module assignment: Stack and queue toolkit in Python

Why this assignment

The specification

Sample input and output

Requirements checklist

Grading rubric

Build it in four parts

Part 1: the bracket checker

Part 2: the postfix calculator

Part 3: the service queue

Part 4: the number stack with a minimum

Hints

Hint for CHECK

Hint for CHECK with an unmatched opener

Hint for RPN

Hint for MIN

Hint for the whole program

Reference solution

Testing your program

What to hand in

Summary of this module

Stuck? Ask the tutor