Python says my formula has too many nested parentheses

New to functions? Open the quick recap. It takes about two minutes.

Quick recapFunctions in two minutes· 2 min

def makes a function. Parameters name the values it’s given, and return hands a value back. Call it with brackets.

def add_tax(price, percent):
    return price + price * percent // 100

add_tax(200, 20)    # 240

See the problem

Your shop app lets owners write price rules. Each rule is saved as steps for a stack, like an old calculator: ["2", "3", "+"] means 2 + 3. To run a rule, the app turns the steps back into Python text, then hands it to eval():

def run_steps(steps):
    stack = []
    for step in steps:
        if step in ("+", "-", "*", "//"):
            right = stack.pop()
            left = stack.pop()
            stack.append(f"({left} {step} {right})")
        else:
            stack.append(step)
    return eval(stack.pop())    # eval("(2 + (3 * 4))")

print(run_steps(["2", "3", "4", "*", "+"]))    # 14

It works for months. Then an owner saves a rule that adds 1, three hundred times. The app crashes before it works out anything:

SyntaxError: too many nested parentheses

Adding 1 three hundred times is easy. So what is Python complaining about, and why didn’t any of it run?

Define the task

Write run_steps(steps).

• Input: steps, a list of text. Each step is a whole number, like "12" or "-3", or one of "+", "-", "*" and "//". There can be a million steps. They always make sense, and never divide by zero.
• How they run: a number goes on top of a stack. An operator takes the top two off, works them out, and puts the answer on top. The one that went on first is on the left: ["7", "2", "-"] is 7 - 2. // rounds down, as in Python.
• Output: the one number left at the end, as an int.

Example: run_steps(["2", "3", "4", "*", "+"]) gives 14. 3 * 4 is 12, then 2 + 12 is 14.

Pause and think

⏸ Pause and think

eval() turns text into a running program. What does it have to do with the text before it can work out even 1 + 1?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

eval() reads text the way Python reads your file: it splits it into words and symbols, checks the brackets and the grammar, and compiles it. That reader allows 200 brackets inside each other at most.

Hint 2 of 3

You don’t need text at all. Keep the numbers themselves on the stack, and work out each step as it comes.

Hint 3 of 3

Calling eval() for each step works, but it reads and compiles a little text every time. The operator module has a function for each operator: operator.add(7, 2) is 9.

Understand the idea

Python reads your whole file before it runs any of it. When you run python shop.py, CPython, the usual Python:

1. Splits the text into tokens: names, numbers, operators and brackets.
2. Parses the tokens into a tree, checking the grammar. A mistake in step 1 or 2 is a SyntaxError, and nothing in the file runs, not even line 1.
3. Compiles the tree into bytecode: small instructions for a stack.
4. Runs the bytecode, one instruction at a time, in a loop called the interpreter. An error here, like NameError, stops at its line, after the lines before it have run.

print("Starting")
total = (2 + 3

This prints nothing, just SyntaxError: '(' was never closed. But this prints Starting first, then stops with NameError: name 'price' is not defined:

print("Starting")
total = price + 3

That’s the long rule’s problem. eval() does steps 1 to 4 on its text. The tokenizer, which splits the text for the parser, allows 200 brackets inside each other at most. So the rule failed while it was being read, and none of it ran.

★Compiled or interpreted? Both

CPython compiles your code to bytecode, then its interpreter runs the bytecode. Bytecode isn’t machine code for your CPU: it’s for Python’s own loop. That loop does a little work for each instruction, which is why a loop in Python is slower than the same loop inside a built-in like sum().

Bytecode is steps for a stack. The dis module shows it. dis.dis("total = price * qty + tip") shows, simplified:

LOAD_NAME      price
LOAD_NAME      qty
BINARY_OP      *
LOAD_NAME      tip
BINARY_OP      +
STORE_NAME     total

LOAD_NAME looks up a name and pushes its value on the stack. BINARY_OP takes the top two off and pushes the answer. STORE_NAME takes the top value off and names it. It’s the rule’s idea exactly: price qty * tip +. Watch a line run, then try your own expression and values:

How Python runs a line

⤢ Full view

Names

a	7
b	2
c	3

The stack is empty.

Step 1 of 7. Before any of line 2 runs, Python compiles it into 6 instructions for a stack. a, b and c already hold 7, 2 and 3.

◀ BackPlayNext ▶Reset Ask me first Show as text

1a, b, c = 7, 2, 3
2x = (a + b) * c
3# Python 3.14 runs line 2 as:
4LOAD_NAME      a
5LOAD_NAME      b
6BINARY_OP      +
7LOAD_NAME      c
8BINARY_OP      *
9STORE_NAME     x

Try your own input

Expressiona, b, cShow it

Python works out what it can while compiling. x = a * (2 + 3) compiles to LOAD_NAME a, LOAD_SMALL_INT 5 (LOAD_CONST 5 before Python 3.14), BINARY_OP *: the 2 + 3 is already done. But 5 // 0 waits for the run, where it raises ZeroDivisionError.

An imported module’s bytecode is saved. When shop.py runs import prices, Python saves the bytecode of prices.py in __pycache__/prices.cpython-314.pyc (the number is your Python’s version). Next time, while prices.py is unchanged, it skips steps 1 to 3. The file you run isn’t saved, only what it imports. A .pyc loads faster; it doesn’t run faster. Many Docker images set PYTHONDONTWRITEBYTECODE=1, which turns the saving off.

An import runs the module’s code, once. import prices runs prices.py from the top, then keeps the module in sys.modules. The next import prices, anywhere in the program, finds it there and runs nothing:

prices.py

print("loading prices")
TAX = 20

shop.py

import prices
import prices
print(prices.TAX)    # loading prices, then 20: prices.py ran once

__name__ says how a file is being used. The file you run gets __name__ == "__main__". A file that’s imported gets its own name, like "prices". So code under if __name__ == "__main__": runs when you run the file, and not when another file imports it. Put a module’s demo or quick self-test there.

A function’s body runs when it’s called. def compiles the body and makes the function, but runs none of it. So a NameError inside a function shows up only when the function is called.

Climb the ladder

All three give 14 for ["2", "3", "4", "*", "+"]. What changes is how much reading and compiling each one asks Python to do.

Okay

Turn the steps into text, then eval() it

The idea: Build the sum as Python text, with brackets, and let eval() work it out.

Short, and Python does the sums with its own rules, // included.

def run_steps(steps: list[str]) -> int:
    # Turn the steps back into Python text, then let Python run it.
    stack: list[str] = []
    for step in steps:
        if step in ("+", "-", "*", "//"):
            right = stack.pop()
            left = stack.pop()
            stack.append(f"({left} {step} {right})")
        else:
            stack.append(step)
    return eval(stack.pop())

Time

O(n²)

Space

O(n²)

Why

Each operator copies the text built so far into a longer text, and a long rule’s text is long.

Where it breaks: Python’s tokenizer allows 200 brackets inside each other at most, so a rule 300 steps deep raises SyntaxError: too many nested parentheses before any of it runs. And eval() runs whatever Python the text holds: a step saved as __import__("os").getcwd() would run as code.

Better

Numbers on the stack, eval() for each step

The idea: Keep the numbers themselves on the stack. For each operator, eval() just the one small sum.

The waste in Okay: it rebuilds the whole rule as text, so one deep rule is one deep text.

Each eval() sees a short text like "7 - 2", so nothing gets deep. And int(step) turns each number step into a number, so a step with code in it raises ValueError instead of running.

Highlighted lines are new in this rung.

def run_steps(steps: list[str]) -> int:
    # Keep numbers on a stack, and let Python work out each sum.
    stack: list[int] = []
    for step in steps:
        if step in ("+", "-", "*", "//"):
            right = stack.pop()
            left = stack.pop()
            stack.append(eval(f"{left} {step} {right}"))
        else:
            stack.append(int(step))
    return stack.pop()

Time

O(n)

Space

O(n)

Why

One pass over the n steps; the stack holds at most n numbers.

What changed from the previous rung

def run_steps(steps: list[str]) -> int:
    # Turn the steps back into Python text, then let Python run it.
    stack: list[str] = []
    # Keep numbers on a stack, and let Python work out each sum.
    stack: list[int] = []
    for step in steps:
        if step in ("+", "-", "*", "//"):
            right = stack.pop()
            left = stack.pop()
            stack.append(f"({left} {step} {right})")
            stack.append(eval(f"{left} {step} {right}"))
        else:
            stack.append(step)
    return eval(stack.pop())
            stack.append(int(step))
    return stack.pop()

Where it breaks: each eval() splits, parses and compiles its text before it runs it: dozens of times the work of the sum itself. A million steps, with 500,000 sums, take several seconds in the browser.

Best

A stack loop, like Python’s own

The idea: A dict from each operator to its function, like operator.add. Pop the right value, then the left, and push the answer.

The waste in Better: it compiles a tiny program for every sum.

OPS[step] finds the function once, and op(left, right) calls it. There’s no text to read, so there’s nothing to compile: this is the loop Python itself runs for BINARY_OP.

Highlighted lines are new in this rung.

from operator import add, floordiv, mul, sub

# Each operator's own function, looked up once per step: no text to compile.
OPS = {"+": add, "-": sub, "*": mul, "//": floordiv}


def run_steps(steps: list[str]) -> int:
    stack: list[int] = []
    for step in steps:
        op = OPS.get(step)
        if op is None:
            stack.append(int(step))
        else:
            right = stack.pop()
            left = stack.pop()
            stack.append(op(left, right))
    return stack.pop()

Time

O(n)

Space

O(n)

Why

One pass; each step is one push, or two pops and a push.

What changed from the previous rung

from operator import add, floordiv, mul, sub

# Each operator's own function, looked up once per step: no text to compile.
OPS = {"+": add, "-": sub, "*": mul, "//": floordiv}


def run_steps(steps: list[str]) -> int:
    # Keep numbers on a stack, and let Python work out each sum.
    stack: list[int] = []
    for step in steps:
        if step in ("+", "-", "*", "//"):
        op = OPS.get(step)
        if op is None:
            stack.append(int(step))
        else:
            right = stack.pop()
            left = stack.pop()
            stack.append(eval(f"{left} {step} {right}"))
        else:
            stack.append(int(step))
            stack.append(op(left, right))
    return stack.pop()

When Best isn’t best: when the formula comes as plain text, like "2 + 3 * 4", it first has to become steps. That’s practice problems 1 and 2. For one short formula you wrote yourself, eval() is fine. Never eval() text from users.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it fails the deep rule with Python’s own SyntaxError.

Run the stack steps

Ctrl + Enter runs

def run_steps(steps: list[str]) -> int: # Each step is a whole number, or one of + - * //. # A number goes on the stack; an operator takes the top two # (the first one on goes on the left) and pushes the answer. return 0

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: run_steps(['2', '3', '+']) → 5
2. ○Not run yet: run_steps(['7', '2', '-']) → 5
3. ○Not run yet: run_steps(['2', '3', '4', '*', '+']) → 14
4. ○Not run yet: run_steps(['7', '-2', '//']) → -4
5. ○Not run yet: Extra test
6. ○Not run yet: A rule 300 steps deep: 1 + 1 + … + 1 → 301
7. ○Not run yet: Speed test: a million steps, with 500,000 sums → 0

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

run_steps()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: the steps as text, one eval()	O(n²)	O(n²)	Short	Fails past 200 brackets; runs any code in a step	Never for saved rules
Better: eval() for each step	O(n)	O(n)	Any depth, and safe	Compiles a tiny program per sum: slow	A few steps, written by you
Best: a stack loop with operator	O(n)	O(n)	Fast, safe, any depth	A few more lines	Running steps, always

Common mistakes and edge cases

!eval() and exec() run any code

eval() runs any expression, and exec() any code, with all the power of your program. Never give them text from a user, a file or a request. To read a value written as text, like "[1, 2, 3]", use ast.literal_eval(): it reads plain values, like numbers, text, lists, tuples, dicts, sets, True and None, and refuses everything else.

• A SyntaxError on the last line stops line 1. Python compiles the whole file first, so a missing bracket at the end means nothing runs.
• Two modules that import each other see each other half run. Say main.py imports shop, shop.py starts with import prices, and prices.py runs from shop import helper. shop.py is still at its first line, so helper doesn’t exist yet: ImportError: cannot import name 'helper'. Move the shared code into a third module.
• Your random.py hides Python’s. A file named like a standard module, in the folder you run from, is found first. random.randint then raises AttributeError. Rename your file.
• Changing a module’s file doesn’t change a running program. The module is already in sys.modules. Restart, or call importlib.reload(prices).
• __pycache__ is safe to delete. Python makes the .pyc files again. Leave it out of git.
• A call chain is 1,000 calls deep at most, by default. Going deeper raises RecursionError. Practice problem 3 runs into it.

Say it in the interview

Questions to ask first

• Can a rule be broken, like too few numbers or an unknown operator? What should happen then?
• What about dividing by zero?
• Should // round down, as Python does, or toward zero, as many other languages do?
• How long can a rule be?

A 60-second walkthrough

“I’d run the steps on a stack, the way Python’s own interpreter runs bytecode. A number is pushed. An operator pops the right value, then the left, and pushes the result, using a dict from each operator to its function, like operator.add. That’s one pass: O(n) time, and O(n) space for the stack. I wouldn’t build text for eval(). Python’s tokenizer refuses more than 200 nested brackets, each eval() compiles before it runs, and eval() runs whatever code the text holds.”

Likely follow-ups

• Is Python compiled or interpreted? Both. CPython compiles to bytecode, and its interpreter loop runs the bytecode.
• What’s a .pyc file? An imported module’s saved bytecode, in __pycache__, used while the source hasn’t changed.
• What does if __name__ == "__main__": do? Its code runs when you run the file, and not when it’s imported.
• What happens when two files import the same module? It runs once; the second import finds it in sys.modules.

Practice

Four problems, from easy to hard. Each has hints, tests you can run here, and its own Okay, Better and Best answers. Try before you open them.

1. Split a formula into tokens (easy)

Python’s first step splits your code into tokens. Write split_formula(formula): the tokens of a formula, in order. A token is a name, a whole number, one of +, -, * and //, or a bracket. A name is letters, digits and _, not starting with a digit. Spaces only separate tokens, and they may be missing.

Example: split_formula("price*qty + 12") gives ["price", "*", "qty", "+", "12"].

Hint 1 of 3

formula.split() splits only at spaces: "price*qty" stays one token.

Hint 2 of 3

Go character by character: letters, digits and _ build up a word, anything else ends it. But // is two characters and one token.

Hint 3 of 3

Python’s tokenizer always takes the longest token it can, so // wins over /. A regular expression does that for you: re.findall(r"\w+|//|[-+*()]", formula).

Split a formula into tokens

Ctrl + Enter runs

def split_formula(formula: str) -> list[str]: # The names, whole numbers, operators (+ - * //) and brackets # in the formula, in order. Spaces only separate them. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: split_formula('price * qty + tip') → ['price', '*', 'qty', '+', 'tip']
2. ○Not run yet: split_formula('price*qty') → ['price', '*', 'qty']
3. ○Not run yet: split_formula('(a + 12) * b') → ['(', 'a', '+', '12', ')', '*', 'b']
4. ○Not run yet: split_formula('total // 2') → ['total', '//', '2']
5. ○Not run yet: split_formula(' x1+y_2 ') → ['x1', '+', 'y_2']
6. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

split_formula()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Split at the spaces

The idea: formula.split()

Right when every token has spaces around it.

def split_formula(formula: str) -> list[str]:
    # Every token is between spaces.
    return formula.split()

Time

O(n)

Space

O(n)

Why

One pass over the n characters.

Where it breaks: "price*qty" has no spaces, so it comes back as one token. So does "(a".

Better

Character by character

The idea: Letters, digits and _ build up a word. Anything else ends the word, and is a token itself unless it’s a space.

The waste in Okay: it depends on spaces the formula doesn’t have to have.

Highlighted lines are new in this rung.

def split_formula(formula: str) -> list[str]:
    tokens: list[str] = []
    word = ""
    for ch in formula:
        if ch.isalnum() or ch == "_":
            word += ch  # part of a name or a number
            continue
        if word:
            tokens.append(word)
            word = ""
        if ch != " ":
            tokens.append(ch)  # an operator or a bracket
    if word:
        tokens.append(word)
    return tokens

Time

O(n)

Space

O(n)

Why

One pass over the n characters.

What changed from the previous rung

def split_formula(formula: str) -> list[str]:
    # Every token is between spaces.
    return formula.split()
    tokens: list[str] = []
    word = ""
    for ch in formula:
        if ch.isalnum() or ch == "_":
            word += ch  # part of a name or a number
            continue
        if word:
            tokens.append(word)
            word = ""
        if ch != " ":
            tokens.append(ch)  # an operator or a bracket
    if word:
        tokens.append(word)
    return tokens

Where it breaks: // is two characters, so it comes back as two tokens: "total // 2" gives ["total", "/", "/", "2"].

Best

The longest token first, like Python’s tokenizer

The idea: re.findall(r"\w+|//|[-+*()]", formula): a word, or //, or a one-character operator or bracket.

The waste in Better: it decides one character at a time, so it can’t see that two make one token.

The pattern tries \w+ first, then //, then a single character. So // is taken whole before a lone / could match. Spaces match nothing, so they’re skipped.

Highlighted lines are new in this rung.

import re

# Longest match first, as Python's own tokenizer does: // before a single /.
TOKEN = re.compile(r"\w+|//|[-+*()]")


def split_formula(formula: str) -> list[str]:
    return TOKEN.findall(formula)

Time

O(n)

Space

O(n)

Why

The regular expression reads each character once.

What changed from the previous rung

import re

# Longest match first, as Python's own tokenizer does: // before a single /.
TOKEN = re.compile(r"\w+|//|[-+*()]")


def split_formula(formula: str) -> list[str]:
    tokens: list[str] = []
    word = ""
    for ch in formula:
        if ch.isalnum() or ch == "_":
            word += ch  # part of a name or a number
            continue
        if word:
            tokens.append(word)
            word = ""
        if ch != " ":
            tokens.append(ch)  # an operator or a bracket
    if word:
        tokens.append(word)
    return tokens
    return TOKEN.findall(formula)

When Best isn’t best: for real Python code, use the tokenize module. It also knows strings, comments, decimals like 1.5e3, and indentation.

2. Turn a formula into stack steps (medium)

Python’s compiler turns a + b * c into the steps a b c * +. Write to_steps(tokens): the steps for a formula’s tokens, like those from problem 1. * and // come before + and -; operators of the same kind go left to right; and brackets come first of all.

Example: to_steps(["a", "+", "b", "*", "c"]) gives ["a", "b", "c", "*", "+"].

Hint 1 of 3

Putting each operator after the next value works for a + b, but not for a + b * c: the * has to run first.

Hint 2 of 3

Keep the operators waiting on a stack. Before you push one, move the waiting ones that bind as tightly or more into the steps. As tightly matters: a - b - c is (a - b) - c.

Hint 3 of 3

A ( waits on the operator stack too, and nothing moves past it. A ) moves operators into the steps until it reaches its (, then drops both.

Turn a formula into stack steps

Ctrl + Enter runs

def to_steps(tokens: list[str]) -> list[str]: # The stack steps for the formula: values in order, each # operator after the two values it works on. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: to_steps(['a', '+', 'b']) → ['a', 'b', '+']
2. ○Not run yet: to_steps(['a', '+', 'b', '*', 'c']) → ['a', 'b', 'c', '*', '+']
3. ○Not run yet: to_steps(['a', '-', 'b', '-', 'c']) → ['a', 'b', '-', 'c', '-']
4. ○Not run yet: to_steps(['(', 'a', '+', 'b', ')', '*', 'c']) → ['a', 'b', '+', 'c', '*']
5. ○Not run yet: to_steps(['a', '*', '(', 'b', '-', 'c', ')', '//', 'd']) → ['a', 'b', 'c', '-', '*', 'd', '//']
6. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

to_steps()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Each operator after the next value

The idea: Hold the last operator, and add it to the steps right after the value that follows it.

Right when the formula only runs left to right, like a + b - c.

def to_steps(tokens: list[str]) -> list[str]:
    # Left to right: each operator goes after the value that follows it.
    steps: list[str] = []
    waiting = ""
    for token in tokens:
        if token in ("+", "-", "*", "//"):
            waiting = token
        else:
            steps.append(token)
            if waiting:
                steps.append(waiting)
                waiting = ""
    return steps

Time

O(n)

Space

O(n)

Why

One pass over the n tokens.

Where it breaks: it ignores which operator binds tighter. a + b * c comes out as a b + c *, which is (a + b) * c. And a bracket is treated as a value.

Better

Operators wait on a stack

The idea: Push each operator, but first move into the steps the waiting ones that bind as tightly or more.

The waste in Okay: it writes + before it has seen whether a * comes next.

>= is what makes a - b - c come out as a b - c -: the first - goes before the second is pushed.

Highlighted lines are new in this rung.

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "//": 2}


def to_steps(tokens: list[str]) -> list[str]:
    steps: list[str] = []
    ops: list[str] = []  # operators waiting for their right-hand value
    for token in tokens:
        if token in PRECEDENCE:
            # Anything waiting that binds as tightly or more goes first: left to right.
            while ops and PRECEDENCE[ops[-1]] >= PRECEDENCE[token]:
                steps.append(ops.pop())
            ops.append(token)
        else:
            steps.append(token)
    while ops:
        steps.append(ops.pop())
    return steps

Time

O(n)

Space

O(n)

Why

Each operator is pushed once and moved once.

What changed from the previous rung

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "//": 2}


def to_steps(tokens: list[str]) -> list[str]:
    # Left to right: each operator goes after the value that follows it.
    steps: list[str] = []
    waiting = ""
    ops: list[str] = []  # operators waiting for their right-hand value
    for token in tokens:
        if token in ("+", "-", "*", "//"):
            waiting = token
        if token in PRECEDENCE:
            # Anything waiting that binds as tightly or more goes first: left to right.
            while ops and PRECEDENCE[ops[-1]] >= PRECEDENCE[token]:
                steps.append(ops.pop())
            ops.append(token)
        else:
            steps.append(token)
            if waiting:
                steps.append(waiting)
                waiting = ""
    while ops:
        steps.append(ops.pop())
    return steps

Where it breaks: brackets. (a + b) * c puts ( and ) in the steps as if they were values.

Best

Brackets wait on the stack too

The idea: Push (. On ), move operators into the steps until the (, then drop it. Nothing moves past a waiting (.

The waste in Better: it already has a stack that waits, but doesn’t let a ( wait on it.

This is the shunting-yard algorithm. Compare its steps with dis: for (a + b) * c, Python loads a and b, adds, loads c, then multiplies.

Highlighted lines are new in this rung.

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "//": 2}


def to_steps(tokens: list[str]) -> list[str]:
    steps: list[str] = []
    ops: list[str] = []  # operators and open brackets, waiting
    for token in tokens:
        if token == "(":
            ops.append(token)
        elif token == ")":
            while ops[-1] != "(":
                steps.append(ops.pop())
            ops.pop()  # the "(" itself
        elif token in PRECEDENCE:
            while ops and ops[-1] != "(" and PRECEDENCE[ops[-1]] >= PRECEDENCE[token]:
                steps.append(ops.pop())
            ops.append(token)
        else:
            steps.append(token)
    while ops:
        steps.append(ops.pop())
    return steps

Time

O(n)

Space

O(n)

Why

Each token is pushed and moved at most once.

What changed from the previous rung

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "//": 2}


def to_steps(tokens: list[str]) -> list[str]:
    steps: list[str] = []
    ops: list[str] = []  # operators waiting for their right-hand value
    ops: list[str] = []  # operators and open brackets, waiting
    for token in tokens:
        if token in PRECEDENCE:
            # Anything waiting that binds as tightly or more goes first: left to right.
            while ops and PRECEDENCE[ops[-1]] >= PRECEDENCE[token]:
        if token == "(":
            ops.append(token)
        elif token == ")":
            while ops[-1] != "(":
                steps.append(ops.pop())
            ops.pop()  # the "(" itself
        elif token in PRECEDENCE:
            while ops and ops[-1] != "(" and PRECEDENCE[ops[-1]] >= PRECEDENCE[token]:
                steps.append(ops.pop())
            ops.append(token)
        else:
            steps.append(token)
    while ops:
        steps.append(ops.pop())
    return steps

When Best isn’t best: Python itself first parses the tokens into a tree, then compiles the tree. A tree is easier to check, and to fold constants in, like 2 + 3. For a formula language with more rules, use a parser, or Python’s ast module when the formula is Python.

3. Flatten a nested list (medium)

Write flatten(items). items is a list of numbers and lists, and those lists can hold numbers and lists too, as deep as you like. Give back one flat list of all the numbers, in order. Don’t change items.

Example: flatten([1, [2, 3], [4, [5]]]) gives [1, 2, 3, 4, 5].

Hint 1 of 3

A function that calls itself for each list inside is the natural shape. But flat = flat + part builds a new list each time, with everything so far in it.

Hint 2 of 3

Keep one list for the answer and append to it, from a helper that calls itself. Now each number is added once. But each list inside is one more call in progress, and Python allows about 1,000 at once.

Hint 3 of 3

Keep your own stack instead of calls: a stack of iter() places, one for each list you’re inside. Take the next item from the top one; for a list, push its iter() and go in; when the top one runs out, pop it.

Flatten a nested list

Ctrl + Enter runs

def flatten(items: list) -> list: # All the numbers in items, in order, in one flat list. # items can hold lists, which can hold lists, at any depth. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: flatten([1, [2, 3], [4, [5]]]) → [1, 2, 3, 4, 5]
2. ○Not run yet: flatten([]) → []
3. ○Not run yet: flatten([[], [[]], 7]) → [7]
4. ○Not run yet: flatten([1, [2, [3, [4, [5]]]]]) → [1, 2, 3, 4, 5]
5. ○Not run yet: Extra test
6. ○Not run yet: A list 1,200 deep: [[[ … [1] … ]]] → [1]
7. ○Not run yet: Speed test: 100,000 numbers, none nested

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

flatten()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Call itself, and add the lists

The idea: For a list inside, flatten it by calling flatten; add each part to the answer with +.

Short, and the shape of the problem: a list holds numbers and smaller lists of the same kind.

def flatten(items: list) -> list:
    flat = []
    for item in items:
        part = flatten(item) if isinstance(item, list) else [item]
        flat = flat + part  # a new list: everything so far, then part
    return flat

Time

O(n²)

Space

O(n)

Why

Each + copies the answer so far into a new list, once for every item.

Where it breaks: flat + part makes a new list every time, so 100,000 numbers copy billions of items. And each list inside is a call in progress: 1,200 deep raises RecursionError.

Better

One answer list, filled by a helper

The idea: A helper walks a list, calls itself for each list inside, and appends each number to one shared answer.

The waste in Okay: it copies the answer again for every item.

append() adds to the one list, so 100,000 numbers take a few milliseconds.

Highlighted lines are new in this rung.

def flatten(items: list) -> list:
    flat = []

    def walk(level: list) -> None:
        for item in level:
            if isinstance(item, list):
                walk(item)
            else:
                flat.append(item)

    walk(items)
    return flat

Time

O(n)

Space

O(n)

Why

Each number is appended once; the calls in progress grow with the depth.

What changed from the previous rung

def flatten(items: list) -> list:
    flat = []
    for item in items:
        part = flatten(item) if isinstance(item, list) else [item]
        flat = flat + part  # a new list: everything so far, then part

    def walk(level: list) -> None:
        for item in level:
            if isinstance(item, list):
                walk(item)
            else:
                flat.append(item)

    walk(items)
    return flat

Where it breaks: Python allows about 1,000 calls in progress, and a list 1,200 deep needs 1,200 of them: RecursionError: maximum recursion depth exceeded.

Best

Your own stack of places

The idea: A stack of iter() places, one per list you’re inside. Read from the top one; push a list’s iter() to go in, pop it when it runs out.

The waste in Better: it keeps its place in each list as a call in progress, and Python caps those.

The stack is a plain list, so it can grow as deep as memory allows. It does what the calls did: remember where to continue in each list you’re inside. Python runs your code on a stack in the same way.

Highlighted lines are new in this rung.

def flatten(items: list) -> list:
    flat = []
    stack = [iter(items)]  # one place in each list we're inside
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))  # go in; come back here after
                break
            flat.append(item)
        else:
            stack.pop()  # that list is done
    return flat

Time

O(n)

Space

O(n)

Why

Each item is read once; the stack holds one place per level, in a list, not in calls.

What changed from the previous rung

def flatten(items: list) -> list:
    flat = []

    def walk(level: list) -> None:
        for item in level:
    stack = [iter(items)]  # one place in each list we're inside
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                walk(item)
            else:
                flat.append(item)

    walk(items)
                stack.append(iter(item))  # go in; come back here after
                break
            flat.append(item)
        else:
            stack.pop()  # that list is done
    return flat

When Best isn’t best: for lists you make yourself, a few levels deep, Better is shorter and just as fast. Pick Best when you don’t control how deep the nesting goes, as with data a user sends you.

4. The order imports run in (hard)

Write import_order(imports, main). imports[name] lists the modules that name imports, in order, on its first lines. Every module’s last line prints its name. Give the names in the order they’re printed when you run main, as Python does it. Python runs a module the first time it’s imported, and puts it in sys.modules before running it. An import of a module already there, even one still running, does nothing. Nothing imports main.

Example: import_order({"main": ["a", "b"], "a": ["c"], "b": ["c"], "c": []}, "main") gives ["c", "a", "b", "main"]: c runs once.

Hint 1 of 3

A function that runs a module, calls itself for each import, then adds the module’s name: that’s the shape. But it runs c twice, and a circle of imports never ends.

Hint 2 of 3

Remember the modules that have run. Note when a module counts as run: if it’s only once it finishes, a circle still never ends.

Hint 3 of 3

Python adds a module to sys.modules before it runs any of it. Do the same: mark it at the start, and skip any module already marked.

The order imports run in

Ctrl + Enter runs

def import_order(imports: dict[str, list[str]], main: str) -> list[str]: # The names in the order they're printed when main runs. # Each module imports imports[name] in order, then prints its name. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: import_order({'main': ['a'], 'a': []}, 'main') → ['a', 'main']
2. ○Not run yet: import_order({'main': ['a', 'b'], 'a': ['c'], 'b': ['c'], 'c': []}, 'main') → ['c', 'a', 'b', 'main']
3. ○Not run yet: import_order({'main': ['b', 'a'], 'a': [], 'b': ['a']}, 'main') → ['a', 'b', 'main']
4. ○Not run yet: import_order({'main': ['a'], 'a': ['b'], 'b': ['a']}, 'main') → ['b', 'a', 'main']
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 40 layers of 2 modules, each importing both in the layer below (how many, the first 3, the last 3) → [81, ['m39a', 'm39b', 'm38a'], ['m0a', 'm0b', 'main']]

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

import_order()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Run every import

The idea: Run a module: run each module it imports, then add its own name.

Right when no module is imported twice.

def import_order(imports: dict[str, list[str]], main: str) -> list[str]:
    printed: list[str] = []

    def run(name: str) -> None:
        for module in imports[name]:
            run(module)  # each import runs that module's code
        printed.append(name)  # its last line prints its name

    run(main)
    return printed

Time

O(2ⁿ)

Space

O(n)

Why

A module imported from k places runs k times, and a layer that imports both modules below it doubles the runs.

Where it breaks: a module imported from two places runs twice: c is printed twice. A circle of imports never ends and raises RecursionError. And 40 layers that each import both modules below them mean over two million million runs.

Better

Skip modules that have finished

The idea: Keep a set of modules that have run, add each one when it finishes, and skip those already in it.

The waste in Okay: it runs a module again although its code already ran.

Highlighted lines are new in this rung.

def import_order(imports: dict[str, list[str]], main: str) -> list[str]:
    printed: list[str] = []
    done: set[str] = set()  # modules that have finished running

    def run(name: str) -> None:
        for module in imports[name]:
            if module not in done:
                run(module)
        done.add(name)
        printed.append(name)

    run(main)
    return printed

Time

O(n + e)

Space

O(n)

Why

Each of the n modules runs once, and each of the e imports is checked once.

What changed from the previous rung

def import_order(imports: dict[str, list[str]], main: str) -> list[str]:
    printed: list[str] = []
    done: set[str] = set()  # modules that have finished running

    def run(name: str) -> None:
        for module in imports[name]:
            run(module)  # each import runs that module's code
        printed.append(name)  # its last line prints its name
            if module not in done:
                run(module)
        done.add(name)
        printed.append(name)

    run(main)
    return printed

Where it breaks: a circle. a imports b, and b imports a. While a is still running, it isn’t in the set, so b runs a again, which runs b again, until RecursionError.

Best

Mark a module before it runs, like sys.modules

The idea: Add the module to the set first, then run its imports, skipping any module already in the set.

The waste in Better: it waits for a module to finish before it counts as loaded, so it can’t see a circle.

This is exactly why a circular import gives you a half-run module: b finds a in sys.modules, but only a’s first lines have run.

Highlighted lines are new in this rung.

def import_order(imports: dict[str, list[str]], main: str) -> list[str]:
    printed: list[str] = []
    loaded: set[str] = set()  # like sys.modules: added before the code runs

    def run(name: str) -> None:
        loaded.add(name)
        for module in imports[name]:
            if module not in loaded:  # even a module still running counts
                run(module)
        printed.append(name)

    run(main)
    return printed

Time

O(n + e)

Space

O(n)

Why

Each of the n modules runs once, and each of the e imports is checked once.

What changed from the previous rung

def import_order(imports: dict[str, list[str]], main: str) -> list[str]:
    printed: list[str] = []
    done: set[str] = set()  # modules that have finished running
    loaded: set[str] = set()  # like sys.modules: added before the code runs

    def run(name: str) -> None:
        loaded.add(name)
        for module in imports[name]:
            if module not in done:
            if module not in loaded:  # even a module still running counts
                run(module)
        done.add(name)
        printed.append(name)

    run(main)
    return printed

When Best isn’t best: a chain of more than about 1,000 imports, each importing the next, would hit Python’s recursion limit. Keep your own stack of modules to run instead of calling the function in itself. Real programs never get that deep.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Predict the outputThis is all of shop.py. What does python shop.py print?

   print("Starting")
   total = (2 + 3

   Starting, then a SyntaxErrorOnly a SyntaxErrorStarting, then 5Starting, then a NameError

   Check answer
2. Predict the outputprices.py prints "loading prices" on its first line. What does this print?

   import prices
   import prices
   print("done")

   loading prices, then doneloading prices twice, then donedoneAn ImportError

   Check answer
3. Multiple choicex = a - b runs as LOAD_NAME a, LOAD_NAME b, BINARY_OP -. With a = 7 and b = 2, what does BINARY_OP push?

   5-572

   Check answer
4. Spot the bugA calculator app runs formulas that users type. What's the real problem?

   def calculate(formula: str) -> int:
       return eval(formula)

   eval() is slow for one formulaeval() runs any Python in the text, so a user can run their own codeeval() can’t do // with negative numberseval() needs the formula split into tokens first

   Check answer
5. Multiple choiceWhen does the code under if __name__ == "__main__" run?

   Every time the file is importedWhen you run the file itself, not when it’s importedOnly the first time Python sees the fileOnly in a .pyc file

   Check answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1What happens between pressing Run and seeing output?Show answer
• Card 2Is Python compiled or interpreted?Show answer
• Card 3What's in __pycache__?Show answer
• Card 4What does import do the second time?Show answer
• Card 5Why does a circular import give you a half-run module?Show answer

Add 5 cards to my review deck

Cheat sheet

• Run means: split into tokens, parse into a tree, compile to bytecode, then run the bytecode in the interpreter loop.
• A SyntaxError anywhere means nothing runs. Other errors stop at their line.
• dis.dis(code) shows bytecode: LOAD_NAME pushes, BINARY_OP pops two and pushes one, STORE_NAME pops and names.
• Imported modules’ bytecode is saved in __pycache__/*.pyc. Safe to delete.
• import m runs m once, then keeps it in sys.modules.
• if __name__ == "__main__": runs only when the file is run, not imported.
• Never eval() or exec() text you didn’t write. ast.literal_eval() reads values safely.

Go deeper

• In the Python docs: dis, the bytecode disassembler, the import system, __main__ and ast.literal_eval.
• Draw your own: the stack picture on the Python visualizer.
• Next on the Python roadmap: I changed my copy, and the original changed too, on what a name really holds.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Say what happens between pressing Run and seeing output
• Tell a SyntaxError, where nothing runs, from an error while running
• Read simple bytecode with dis, and run stack steps yourself
• Explain .pyc files, why a module runs once, and if __name__ == "__main__"

✓Mark as completeI already know this

Status: Not started