Calculator with two stacks in Python

Why this matters

A calculator app has to take text such as (7 + 3) / 2 - 1 and return a number. The user types the expression in the order people write it, and the program must follow the usual rules: brackets first, then * and /, then + and -. A spreadsheet cell that holds a formula does the same job.

The previous lesson turned that text into postfix order. Postfix can then be evaluated with a single stack. This lesson skips the postfix step. It reads the expression once, from left to right, and keeps two stacks at the same time: one for numbers and one for operators. The method is often called Dijkstra's two-stack algorithm, after the same person who described the shunting-yard method.

The idea: two piles

A stack is a pile where you add and remove items only at the top. In Python, a plain list does this job. append adds an item to the top, and pop() removes the top item and returns it. The top is the last item in the list.

Picture two piles of cards on a table.

The value pile holds numbers. These are numbers that have been read but not yet combined.
The operator pile holds operators such as + or * that are waiting for their right-hand number.

Read the expression one token at a time. A token is one number, one operator, or one bracket. Each token either adds to the piles or combines what is already there.

Start with the simplest case, 2 + 3:

Read 2. It is a number, so put it on the value pile.
Read +. It is an operator, and the operator pile is empty, so put it on the operator pile.
Read 3. Put it on the value pile.
The input has ended. Take the top operator, +. Take the top two values, 3 and 2. Add them to get 5. Put 5 back on the value pile.

The value pile now holds one number, 5, and the operator pile is empty. The answer is 5.

The two piles keep one promise at all times. The value pile holds results of parts that are finished. The operator pile holds operators whose right-hand side is not yet known.

Applying an operator

An operator is applied in three steps:

Pop the operator from the operator pile.
Pop the top value. Call it b, because it is the right-hand number.
Pop the next value. Call it a, because it is the left-hand number.

Then push the result of a op b back on the value pile.

The order matters for - and /. Take 10 - 3. The value pile holds 10 below 3, so 3 is popped first and becomes b. The result is a - b, which is 10 - 3, or 7. If you swap the two pops, you get 3 - 10, which is -7. The Python program below uses the order that gives 7, and a later section shows what the wrong order looks like.

The rules

The program uses these rules. The worked examples below show each rule in use.

Number: read all the digits in a row as one number, and push it on the value pile.
Open bracket (: push it on the operator pile.
Operator: before pushing it, apply every operator on top of the operator pile that is not ( and has the same or higher precedence. Then push the new operator. Precedence is the same table as in the previous lesson: * and / are 2, and + and - are 1.
Close bracket ): apply operators until the top of the operator pile is (. Then pop that ( and throw it away.
End of input: apply every operator left on the operator pile.

Rule 3 is the same test as in the shunting-yard method. The difference is that the operator is applied right away, instead of being sent to an output list. Rule 4 makes the brackets work, because everything inside them is applied before anything outside.

After the last rule runs, exactly one number should remain on the value pile. If zero or several are left, the expression was not well formed.

Worked example 1: `2 + 3 * 4`

Work through the expression one token at a time. The top of each pile is written first.

Token	Value pile	Operator pile	What happens
`2`	`2`	empty	number, push
`+`	`2`	`+`	pile is empty, push
`3`	`3`, `2`	`+`	number, push
`*`	`3`, `2`	`*`, `+`	`*` binds tighter than `+`, so nothing is applied; push
`4`	`4`, `3`, `2`	`*`, `+`	number, push
end	`14`	empty	apply ``: 3 4 = 12; apply `+`: 2 + 12 = 14

The * waits on the operator pile because it has to be done before the +. The value pile then holds 4, 3 and 2. At the end, * takes 3 and 4 and leaves 12. Then + takes 2 and 12 and leaves 14.

Worked example 2: `(7 + 3) / 2 - 1`

This example has brackets and two operators of the same precedence in a row.

Token	Value pile	Operator pile	What happens
`(`	empty	`(`	open bracket, push
`7`	`7`	`(`	number, push
`+`	`7`	`+`, `(`	top is `(`, so nothing is applied; push
`3`	`3`, `7`	`+`, `(`	number, push
`)`	`10`	empty	apply `+`: 7 + 3 = 10; pop `(`
`/`	`10`	`/`	pile is empty, push
`2`	`2`, `10`	`/`	number, push
`-`	`5`	`-`	`/` has higher precedence than `-`, so apply it: 10 / 2 = 5; push `-`
`1`	`1`, `5`	`-`	number, push
end	`4`	empty	apply `-`: 5 - 1 = 4

At the ), the + is applied. Its two numbers are 7 and 3, so the bracket leaves 10 on the value pile. The ( is then removed, so the / that follows is not affected by the bracket.

At the -, the / on the operator pile is applied first. The / takes 10 and 2. This is the precedence rule: / binds more tightly than -, so it is done first.

Worked example 3: `3 + 4 * 2 / (1 - 5)`

This is the same expression as the last lesson. Here is the real trace from the Python program below. Each line shows the token, the value pile and the operator pile, with the top on the left. The program prints each list with the top first.

3    value stack=[3]  op stack=[]
+    value stack=[3]  op stack=['+']
4    value stack=[4, 3]  op stack=['+']
*    value stack=[4, 3]  op stack=['*', '+']
2    value stack=[2, 4, 3]  op stack=['*', '+']
/    value stack=[8, 3]  op stack=['/', '+']
(    value stack=[8, 3]  op stack=['(', '/', '+']
1    value stack=[1, 8, 3]  op stack=['(', '/', '+']
-    value stack=[1, 8, 3]  op stack=['-', '(', '/', '+']
5    value stack=[5, 1, 8, 3]  op stack=['-', '(', '/', '+']
)    value stack=[-4, 8, 3]  op stack=['/', '+']
result: 1

Read the / line. Before / is pushed, the top of the operator pile is *. It has precedence 2, the same as /, so it is applied first. Its numbers are 4 and 2, so the value pile becomes 8 on top of 3. The + below is not applied, because its precedence is lower than /.

Read the ) line. The - is applied to 1 and 5, giving -4. The ( is then removed. The value pile is now -4, 8, 3, and the operator pile holds / and +.

The program does not print the last two steps. At the end, / takes 8 and -4, which gives -2. Then + takes 3 and -2, which gives 1. That matches the result: 1 line.

Worked example 4: nested brackets

The last example has brackets inside brackets, and a division after a subtraction. The expression is ((1 + 2) * (3 + 4)) - 10 / (4 - 2). Here is the real trace from the program:

(    value stack=[]  op stack=['(']
(    value stack=[]  op stack=['(', '(']
1    value stack=[1]  op stack=['(', '(']
+    value stack=[1]  op stack=['+', '(', '(']
2    value stack=[2, 1]  op stack=['+', '(', '(']
)    value stack=[3]  op stack=['(']
*    value stack=[3]  op stack=['*', '(']
(    value stack=[3]  op stack=['(', '*', '(']
3    value stack=[3, 3]  op stack=['(', '*', '(']
+    value stack=[3, 3]  op stack=['+', '(', '*', '(']
4    value stack=[4, 3, 3]  op stack=['+', '(', '*', '(']
)    value stack=[7, 3]  op stack=['*', '(']
)    value stack=[21]  op stack=[]
-    value stack=[21]  op stack=['-']
10   value stack=[10, 21]  op stack=['-']
/    value stack=[10, 21]  op stack=['/', '-']
(    value stack=[10, 21]  op stack=['(', '/', '-']
4    value stack=[4, 10, 21]  op stack=['(', '/', '-']
-    value stack=[4, 10, 21]  op stack=['-', '(', '/', '-']
2    value stack=[2, 4, 10, 21]  op stack=['-', '(', '/', '-']
)    value stack=[2, 10, 21]  op stack=['/', '-']
result: 16

The first ) after 4 applies the + inside (3 + 4), which leaves 7. The * is still on the operator pile, because the ) only applies operators down to the nearest (. The second ) then applies * to 3 and 7, which leaves 21, and removes the outer (.

The - after that finds an empty operator pile, so it is pushed without anything being applied. The / arrives next. The - on top has precedence 1, which is lower than the /, so the / waits on top of it. The (4 - 2) brackets then leave 2 on the value pile.

At the end, the / takes 10 and 2 to give 5. The - takes 21 and 5 to give 16. The / is applied first because it binds more tightly, and the 21 waits on the value pile until the - needs it.

The Python program

The program follows the rules above. It has four parts.

PRECEDENCE is a dictionary. A dictionary maps each key to a value, here an operator to its precedence number. precedence looks up a key with .get, which returns 0 for anything that is not an operator instead of raising an error.
divide and apply do one arithmetic step. apply raises ZeroDivisionError before it divides by zero. The next section explains why divide exists.
reduce pops one operator and its two numbers, applies the operator, and pushes the result. It also checks that there are two numbers to use.
evaluate reads the text and follows the five rules. When trace is True, it prints a line after each token.

The trace prints each list with values[::-1]. The [::-1] part is a slice. It makes a reversed copy of the list, so the top item is printed first. The list itself is not changed.

Whole-number division

Python has two division operators, and they behave differently with negative numbers.

/ always gives a number with a decimal point (a float). -7 / 2 is -3.5.
// drops the fraction and rounds toward negative infinity. -7 // 2 is -4.

A calculator that keeps whole numbers should round toward zero, so that -7 / 2 gives -3. The divide function does that. It divides the absolute values with //, then puts the sign back. apply calls divide for /, so the program never uses Python's / operator.

Save the code as calculator.py. It needs no input, so run it with:

python3 calculator.py

Python · editable

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

def precedence(op):
    return PRECEDENCE.get(op, 0)

def divide(a, b):
    # Python's // rounds toward negative infinity, so -7 // 2 is -4.
    # This helper rounds toward zero, which gives -3.
    quotient = abs(a) // abs(b)
    if (a < 0) == (b < 0):
        return quotient
    return -quotient

def apply(a, op, b):
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    if op == "/":
        if b == 0:
            raise ZeroDivisionError("division by zero")
        return divide(a, b)
    raise ValueError(f"unknown operator {op}")

def reduce(values, ops):
    op = ops.pop()
    if len(values) < 2:
        raise ValueError(f"missing a number before '{op}'")
    b = values.pop()
    a = values.pop()
    values.append(apply(a, op, b))

def evaluate(text, trace=False):
    values = []  # the value pile; the top is the last item
    ops = []  # the operator pile; the top is the last item
    i = 0
    while i < len(text):
        c = text[i]
        if c.isspace():
            i += 1
            continue
        if "0" <= c <= "9":
            number = 0
            while i < len(text) and "0" <= text[i] <= "9":
                number = number * 10 + int(text[i])
                i += 1
            values.append(number)
            if trace:
                print(f"{number:<4} value stack={values[::-1]}  op stack={ops[::-1]}")
            continue
        if c == "(":
            ops.append(c)
        elif c == ")":
            while ops and ops[-1] != "(":
                reduce(values, ops)
            if not ops:
                raise ValueError("unmatched ')'")
            ops.pop()
        elif c in PRECEDENCE:
            while ops and ops[-1] != "(" and precedence(ops[-1]) >= precedence(c):
                reduce(values, ops)
            ops.append(c)
        else:
            raise ValueError(f"unknown character '{c}' at position {i}")
        if trace:
            print(f"{c:<4} value stack={values[::-1]}  op stack={ops[::-1]}")
        i += 1
    while ops:
        if ops[-1] == "(":
            raise ValueError("unmatched '('")
        reduce(values, ops)
    if len(values) != 1:
        raise ValueError("malformed expression")
    return values.pop()

def main():
    print("Trace:")
    print(f"result: {evaluate('3 + 4 * 2 / (1 - 5)', trace=True)}")
    print()
    examples = [
        "(2 + 3) * (4 - 1) / 3",
        "8 - 3 - 2",
        "8 / 4 / 2",
        "100 - (20 + 30) * 2",
        "7 / 0",
        "1 +",
        "5 3",
        "-3",
        "2 * (3 + 4",
        "7 + x",
    ]
    for e in examples:
        try:
            print(f"{e}  =  {evaluate(e)}")
        except (ZeroDivisionError, ValueError) as ex:
            print(f"{e}  ->  error: {ex}")
    print(2147483647 + 1)
    print(evaluate("2147483647 + 1"))
    print(divide(-7, 2))
    print(-7 // 2)

if __name__ == "__main__":
    main()

The real output with Python 3.14 is:

Trace:
3    value stack=[3]  op stack=[]
+    value stack=[3]  op stack=['+']
4    value stack=[4, 3]  op stack=['+']
*    value stack=[4, 3]  op stack=['*', '+']
2    value stack=[2, 4, 3]  op stack=['*', '+']
/    value stack=[8, 3]  op stack=['/', '+']
(    value stack=[8, 3]  op stack=['(', '/', '+']
1    value stack=[1, 8, 3]  op stack=['(', '/', '+']
-    value stack=[1, 8, 3]  op stack=['-', '(', '/', '+']
5    value stack=[5, 1, 8, 3]  op stack=['-', '(', '/', '+']
)    value stack=[-4, 8, 3]  op stack=['/', '+']
result: 1
 
(2 + 3) * (4 - 1) / 3  =  5
8 - 3 - 2  =  3
8 / 4 / 2  =  1
100 - (20 + 30) * 2  =  0
7 / 0  ->  error: division by zero
1 +  ->  error: missing a number before '+'
5 3  ->  error: malformed expression
-3  ->  error: missing a number before '-'
2 * (3 + 4  ->  error: unmatched '('
7 + x  ->  error: unknown character 'x' at position 4
2147483648
2147483648
-3
-4

The last four lines show things about Python numbers that you need to know. They are covered in the mistakes section.

The last two lines of the file call main only when the file is run directly. If another file imports calculator, main does not run. This is a common habit in Python programs.

Common mistakes

Popping the two numbers in the wrong order. A common error is to pop the left-hand number first. Here is the reduce step written the wrong way round, in a copy of the program:

a = values.pop()
b = values.pop()

With this change, 10 - 3 gives the wrong answer. In a copy of the program with only those two lines changed, evaluate("10 - 3") returns:

-7

The top of the value pile is the right-hand number, so it must be popped first. In the program, b is the right-hand number and is popped first.

Using > instead of >=. The rule says to apply operators of the same precedence. If the check uses >, the operators pile up, and the expression is evaluated in the wrong order. A copy of the program with > in place of >= gives:

8 - 3 - 2  =  7
8 / 4 / 2  =  4

The correct values are 3 and 1. The first result is 8 - (3 - 2), and the second is 8 / (4 / 2). Both are the right-to-left order that the rule is meant to prevent.

Forgetting the check for enough numbers. The reduce function checks that there are two numbers before it pops them. Without that check, an input such as 1 + would try to pop from an empty value pile. Python then stops with an error. This output is from a copy of the program with the check removed. The lines that show the file and line numbers are left out:

IndexError: pop from empty list

The check turns this into a message that names the operator, which is much easier to act on.

Division by zero. 7 / 0 is valid text but an invalid calculation. apply checks for zero first and raises ZeroDivisionError with the message division by zero. Python would raise the same error on its own for 7 // 0, so the check does not change what happens. It keeps the rule next to the other operators, and it gives a message that names the calculation.

Comparing with is instead of ==. is checks whether two names point to the same object. == checks whether two values are equal. For whole numbers, is can give the wrong answer. This snippet creates two equal numbers at run time:

a = int("1000")
b = int("1000")
print("1000 == 1000:", a == b)
print("1000 is 1000:", a is b)

1000 == 1000: True
1000 is 1000: False

CPython, the standard Python implementation, keeps one shared object for each whole number from -5 to 256. So is looks right for small numbers. For int("256") is int("256") the result is True, and for int("257") is int("257") it is False. These results depend on the Python version, so do not rely on them. Use == to compare values.

Python also warns about is with a literal. This line compiles, but Python 3.14 prints a warning:

op = "+"
if op is "+":
    print("plus")

SyntaxWarning: "is" with 'str' literal. Did you mean "=="?
  if op is "+":
plus

The file name and line number before the warning are left out.

Integer size and rounding. Python whole numbers have no fixed size limit. In Java, an int wraps around after 2147483647, but in Python 2147483647 + 1 is 2147483648. The program prints that value. Python has no wrap-around, so the calculator does not need a special check for it.

For division, / gives a float: -7 / 2 is -3.5. // gives -4. The divide function gives -3, which is the answer a calculator that keeps whole numbers should show.

Storing values in a list. Python lists hold any kind of object. A list of numbers and a list of one-character strings need no special type. A one-character string such as "+" stands in for a character, because Python has no separate character type.

Practice

Exercise 1. Evaluate 6 + 2 * 5 by hand. Write the value pile and the operator pile after each token.

Show the answer

The result is 16. After * is pushed on top of +, the numbers 2 and 5 are applied first, giving 10. Then + takes 6 and 10 to give 16.

Exercise 2. Evaluate 20 / 3 * 3. Be careful about the order.

Show the answer

The result is 18, not 20. The two operators have the same precedence, so the left one is applied first. 20 / 3 is 6 with the divide function, and 6 * 3 is 18.

Exercise 3. Evaluate 2 * (3 + (4 - 1)) * 2. This one has brackets inside brackets.

Show the answer

The result is 24. The innermost brackets give 4 - 1, which is 3. The next brackets give 3 + 3, which is 6. Then 2 * 6 is 12, and 12 * 2 is 24.

Exercise 4. What does the calculation of 7 / (3 - 3) produce? Which check stops it?

Show the answer

The calculation stops with a ZeroDivisionError whose message is division by zero. The inside of the brackets is 3 - 3, which is 0. The apply function checks for a zero divisor before it divides. When main catches the error, it prints the message after error:.

Exercise 5. Describe what happens to the two piles for the input 10 - 4 - 3. Give the final value, and explain why the first - is applied before the second one is pushed.

Show the answer

The first - is on the operator pile when the second - is read. Both have precedence 1, so rule 3 applies the first - to 10 and 4, which leaves 6. The second - is then pushed, and at the end it takes 6 and 3. The final value is 3. If the first - were not applied, the result would be 10 - (4 - 3), which is 9.

Summary

Keep two piles: one for numbers and one for operators. In Python, each pile is a list.
Before an operator is pushed, every operator on top of the operator pile with equal or higher precedence is applied.
The right-hand number is popped first, so the pop order decides the answer for - and /.
A ( stops the operators inside it from being applied too early, and a ) applies them.
Check at the end that exactly one number is left, and treat any other count as an error.

Calculator with two stacks in Python

Why this matters

The idea: two piles

Applying an operator

The rules

Worked example 1: 2 + 3 * 4

Worked example 2: (7 + 3) / 2 - 1

Worked example 3: 3 + 4 * 2 / (1 - 5)

Worked example 4: nested brackets

The Python program

Whole-number division

Common mistakes

Practice

Summary

Stuck? Ask the tutor

Worked example 1: `2 + 3 * 4`

Worked example 2: `(7 + 3) / 2 - 1`

Worked example 3: `3 + 4 * 2 / (1 - 5)`