<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P062-expression-calculator/ | updated: 2026-10-14 -->

# P062 Expression calculator

Expressions typed the usual way - + - * /, whole powers with ^, brackets and minus signs - turned into postfix by Dijkstra's shunting-yard algorithm and worked out on a stack, both shown step by step, in exact fractions; postfix can be typed directly too.

EML-P project `projects/expression-calculator` in the EML language repo: 3 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/expression-calculator` runs it and `eml project verify projects/expression-calculator` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: rpn-evaluator (https://efficientnewlanguage.org/cases/093-rpn-evaluator/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
1

2
(1 + 2
2
1 + 2)
2
2 $ 3
2
1.2.3
2
2 +
2
2 3
2
1 / (2 - 2)
2
2 ^ 0.5
2
2 ^ 21
2
0 ^ -1
2
()
2
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3
3 +
3
1 x
3

4
```

Screen:

```text
== Expression calculator ==
Exact fractions: + - * /, ^ for whole powers, brackets and minus signs, like (1 + 2) * -3 / 4.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 0
Pick a number from 1 to 4.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> x
Pick a number from 1 to 4.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 1
expression> 
Cancelled.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> (1 + 2
Not an expression: a ( that is never closed.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 1 + 2)
Not an expression: a ) with no ( before it.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 2 $ 3
Cannot read the character $.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 1.2.3
Cannot read the number 1.2.3.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 2 +
Cannot be worked out: + without two numbers to work on.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 2 3
Cannot be worked out: numbers with no operator between them.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 1 / (2 - 2)
Cannot be worked out: division by zero.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 2 ^ 0.5
Cannot be worked out: a power that is not a whole number: 1/2.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 2 ^ 21
Cannot be worked out: a power above 20.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 0 ^ -1
Cannot be worked out: zero to a negative power.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> ()
There is nothing to work out.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Keep an expression to 80 characters.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 3
postfix, tokens with spaces between (neg for a minus sign)> 3 +
Postfix: 3 +
Stack - each postfix token, then the stack:
  3     3
Cannot be worked out: + without two numbers to work on.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 3
postfix, tokens with spaces between (neg for a minus sign)> 1 x
Not a number or an operator: x.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 3
postfix, tokens with spaces between (neg for a minus sign)> 
Cancelled.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 4
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
(1 + 2) * -3 / 4
1
2 ^ 3 ^ 2
2
1/3 + 1/6
2
-2^2 + (-2)^2
2
10 / 4 - 0.5
2
1/3
3
3 4 + 2 *
4
```

Screen:

```text
== Expression calculator ==
Exact fractions: + - * /, ^ for whole powers, brackets and minus signs, like (1 + 2) * -3 / 4.

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 1
expression> (1 + 2) * -3 / 4
Postfix: 1 2 + 3 neg * 4 /
Shunting yard - each token, then the output so far and the operators waiting:
  (                                  | (
  1     1                            | (
  +     1                            | ( +
  2     1 2                          | ( +
  )     1 2 +                        |
  *     1 2 +                        | *
  neg   1 2 +                        | * neg
  3     1 2 + 3                      | * neg
  /     1 2 + 3 neg *                | /
  4     1 2 + 3 neg * 4              | /
Stack - each postfix token, then the stack:
  1     1
  2     1 2
  +     3
  3     3 3
  neg   3 -3
  *     -9
  4     -9 4
  /     -9/4
= -9/4 = -2.25

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 1
expression> 2 ^ 3 ^ 2
Postfix: 2 3 2 ^ ^
Shunting yard - each token, then the output so far and the operators waiting:
  2     2                            |
  ^     2                            | ^
  3     2 3                          | ^
  ^     2 3                          | ^ ^
  2     2 3 2                        | ^ ^
Stack - each postfix token, then the stack:
  2     2
  3     2 3
  2     2 3 2
  ^     2 9
  ^     512
= 512

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 1/3 + 1/6
= 1/2 = 0.5

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> -2^2 + (-2)^2
= 0

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 10 / 4 - 0.5
= 2

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 2
expression> 1/3
= 1/3 = ~0.333333

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 3
postfix, tokens with spaces between (neg for a minus sign)> 3 4 + 2 *
Postfix: 3 4 + 2 *
Stack - each postfix token, then the stack:
  3     3
  4     3 4
  +     7
  2     7 2
  *     14
= 14

1) step by step  2) just the answer  3) type postfix  4) quit
choice> 4
Bye.
```

## Modules

### main.eml

```eml
# P062 expression calculator: type an expression the usual way - with + - *
# /, ^ for whole powers, brackets and minus signs - and see it turned into
# postfix order by the shunting-yard algorithm and worked out on a stack,
# step by step, in exact fractions. Postfix can be typed directly too.
import expr
import frac

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def words(s):
    [] => out
    "" => word
    for c in s + " ":
        if c == " ":
            if word != "":
                out + [word] => out
            "" => word
        else:
            word + c => word
    return out

def joined(ts):
    "" => s
    for t in ts:
        if s != "":
            s + " " => s
        s + expr.shown(t) => s
    return s

def numbers(xs):
    "" => s
    for x in xs:
        if s != "":
            s + " " => s
        s + frac.text(x) => s
    return s

def padded(s, width):
    while len(s) < width:
        s + " " => s
    return s

def answer(x):
    # 7/2 = 3.5; a whole number as it is; a long decimal rounded, marked ~.
    if x[1] == 1:
        return frac.text(x)
    frac.decimal(x, 6) => d
    if len(d) > 6 and d[0:6] == "about ":
        "~" + d[6:len(d)] => d
    return frac.text(x) + " = " + d

def show_steps(postfix_steps, eval_steps):
    if len(postfix_steps) > 0:
        "Shunting yard - each token, then the output so far and the operators waiting:" ^0
        for s in postfix_steps:
            "  " + padded(expr.shown(s[0]), 6) + padded(joined(s[1]), 28) + " |" => line
            if len(s[2]) > 0:
                line + " " + joined(s[2]) => line
            line ^0
    "Stack - each postfix token, then the stack:" ^0
    for s in eval_steps:
        ("  " + padded(expr.shown(s[0]), 6) + numbers(s[1])) ^0

def work_out(steps):
    trim(input("expression> ")) => s
    if s == "":
        "Cancelled." ^0
        return
    if len(s) > 80:
        "Keep an expression to 80 characters." ^0
        return
    expr.tokens(s) => ts
    if len(ts) > 0 and ts[0][0] == "bad":
        ("Cannot read " + ts[0][1] + ".") ^0
        return
    expr.to_postfix(ts) => p
    if p[2] != "":
        ("Not an expression: " + p[2] + ".") ^0
        return
    if len(p[0]) == 0:
        "There is nothing to work out." ^0
        return
    run(p[0], p[1], steps)

def run(postfix, postfix_steps, steps):
    expr.evaluate(postfix) => r
    if steps:
        ("Postfix: " + joined(postfix)) ^0
        show_steps(postfix_steps, r[1])
    if r[2] != "":
        ("Cannot be worked out: " + r[2] + ".") ^0
        return
    ("= " + answer(r[0])) ^0

def postfix_input():
    words(trim(input("postfix, tokens with spaces between (neg for a minus sign)> "))) => ws
    if len(ws) == 0:
        "Cancelled." ^0
        return
    [] => ts
    for w in ws:
        if w == "+" or w == "-" or w == "*" or w == "/" or w == "^" or w == "neg":
            ts + [["op", w]] => ts
        else:
            frac.parse(w) => x
            if len(x) == 0:
                ("Not a number or an operator: " + w + ".") ^0
                return
            ts + [["num", x]] => ts
    run(ts, [], True)

"== Expression calculator ==" ^0
"Exact fractions: + - * /, ^ for whole powers, brackets and minus signs, like (1 + 2) * -3 / 4." ^0
True => running
while running:
    "" ^0
    "1) step by step  2) just the answer  3) type postfix  4) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        work_out(True)
    elif choice == "2":
        work_out(False)
    elif choice == "3":
        postfix_input()
    elif choice == "4":
        False => running
    else:
        "Pick a number from 1 to 4." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import expr
import frac

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def words(s):
    out = []
    word = ""
    for c in s + " ":
        if c == " ":
            if word != "":
                out = out + [word]
            word = ""
        else:
            word = word + c
    return out

def joined(ts):
    s = ""
    for t in ts:
        if s != "":
            s = s + " "
        s = s + expr.shown(t)
    return s

def numbers(xs):
    s = ""
    for x in xs:
        if s != "":
            s = s + " "
        s = s + frac.text(x)
    return s

def padded(s, width):
    while len(s) < width:
        s = s + " "
    return s

def answer(x):
    if x[1] == 1:
        return frac.text(x)
    d = frac.decimal(x, 6)
    if len(d) > 6 and d[0:6] == "about ":
        d = "~" + d[6:len(d)]
    return frac.text(x) + " = " + d

def show_steps(postfix_steps, eval_steps):
    if len(postfix_steps) > 0:
        print("Shunting yard - each token, then the output so far and the operators waiting:")
        for s in postfix_steps:
            line = "  " + padded(expr.shown(s[0]), 6) + padded(joined(s[1]), 28) + " |"
            if len(s[2]) > 0:
                line = line + " " + joined(s[2])
            print(line)
    print("Stack - each postfix token, then the stack:")
    for s in eval_steps:
        print("  " + padded(expr.shown(s[0]), 6) + numbers(s[1]))

def work_out(steps):
    s = trim(input("expression> "))
    if s == "":
        print("Cancelled.")
        return
    if len(s) > 80:
        print("Keep an expression to 80 characters.")
        return
    ts = expr.tokens(s)
    if len(ts) > 0 and ts[0][0] == "bad":
        print("Cannot read " + ts[0][1] + ".")
        return
    p = expr.to_postfix(ts)
    if p[2] != "":
        print("Not an expression: " + p[2] + ".")
        return
    if len(p[0]) == 0:
        print("There is nothing to work out.")
        return
    run(p[0], p[1], steps)

def run(postfix, postfix_steps, steps):
    r = expr.evaluate(postfix)
    if steps:
        print("Postfix: " + joined(postfix))
        show_steps(postfix_steps, r[1])
    if r[2] != "":
        print("Cannot be worked out: " + r[2] + ".")
        return
    print("= " + answer(r[0]))

def postfix_input():
    ws = words(trim(input("postfix, tokens with spaces between (neg for a minus sign)> ")))
    if len(ws) == 0:
        print("Cancelled.")
        return
    ts = []
    for w in ws:
        if w == "+" or w == "-" or w == "*" or w == "/" or w == "^" or w == "neg":
            ts = ts + [["op", w]]
        else:
            x = frac.parse(w)
            if len(x) == 0:
                print("Not a number or an operator: " + w + ".")
                return
            ts = ts + [["num", x]]
    run(ts, [], True)

print("== Expression calculator ==")
print("Exact fractions: + - * /, ^ for whole powers, brackets and minus signs, like (1 + 2) * -3 / 4.")
running = True
while running:
    print("")
    print("1) step by step  2) just the answer  3) type postfix  4) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        work_out(True)
    elif choice == "2":
        work_out(False)
    elif choice == "3":
        postfix_input()
    elif choice == "4":
        running = False
    else:
        print("Pick a number from 1 to 4.")
print("Bye.")
```

### expr.eml

```eml
# P062 expression calculator - tokens, the shunting-yard conversion from the
# usual (infix) order to postfix, and the stack that works postfix out.
# A token is ["num", fraction], ["op", "+"], ["(", ""] or [")", ""]. The
# operators: + - * / and ^ (a whole-number power), and "neg", a minus sign
# in front of a number or a bracket.
import frac

def precedence(op):
    if op == "+" or op == "-":
        return 1
    if op == "*" or op == "/":
        return 2
    if op == "neg":
        return 3
    return 4

def right_assoc(op):
    # 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2), and - - 3 is -(-3); the rest group left.
    return op == "^" or op == "neg"

def tokens(s):
    # The tokens of s, or [["bad", why]].
    [] => out
    0 => i
    while i < len(s):
        s[i] => c
        if c == " ":
            i + 1 => i
        elif (c >= "0" and c <= "9") or c == ".":
            i => j
            while j < len(s) and ((s[j] >= "0" and s[j] <= "9") or s[j] == "."):
                j + 1 => j
            frac.parse(s[i:j]) => x
            if len(x) == 0:
                return [["bad", "the number " + s[i:j]]]
            out + [["num", x]] => out
            j => i
        elif c == "+" or c == "-" or c == "*" or c == "/" or c == "^":
            # A minus with nothing, an operator or "(" before it is a sign.
            if c == "-" and (len(out) == 0 or out[len(out) - 1][0] == "op" or out[len(out) - 1][0] == "("):
                out + [["op", "neg"]] => out
            else:
                out + [["op", c]] => out
            i + 1 => i
        elif c == "(" or c == ")":
            out + [[c, ""]] => out
            i + 1 => i
        else:
            return [["bad", "the character " + c]]
    return out

def shown(t):
    if t[0] == "num":
        return frac.text(t[1])
    if t[0] == "op":
        if t[1] == "neg":
            return "neg"
        return t[1]
    return t[0]

def to_postfix(ts):
    # Dijkstra's shunting yard. Numbers go straight to the output; an
    # operator first moves to the output every operator on the stack that
    # binds tighter (or as tight, when it groups left), then waits on the
    # stack; "(" waits, and ")" moves operators out until its "(". Returns
    # [postfix tokens, steps, problem]: each step [token, output, stack].
    [] => output
    [] => stack
    [] => steps
    "" => problem
    for t in ts:
        if t[0] == "num":
            output + [t] => output
        elif t[0] == "op":
            True => moving
            while moving and len(stack) > 0 and stack[len(stack) - 1][0] == "op" and t[1] != "neg":
                stack[len(stack) - 1][1] => top
                if precedence(top) > precedence(t[1]) or (precedence(top) == precedence(t[1]) and not right_assoc(t[1])):
                    output + [stack[len(stack) - 1]] => output
                    stack[0:len(stack) - 1] => stack
                else:
                    False => moving
            stack + [t] => stack
        elif t[0] == "(":
            stack + [t] => stack
        else:
            while len(stack) > 0 and stack[len(stack) - 1][0] != "(":
                output + [stack[len(stack) - 1]] => output
                stack[0:len(stack) - 1] => stack
            if len(stack) == 0:
                "a ) with no ( before it" => problem
                return [output, steps, problem]
            stack[0:len(stack) - 1] => stack
        steps + [[t, output, stack]] => steps
    while len(stack) > 0:
        if stack[len(stack) - 1][0] == "(":
            "a ( that is never closed" => problem
            return [output, steps, problem]
        output + [stack[len(stack) - 1]] => output
        stack[0:len(stack) - 1] => stack
    return [output, steps, problem]

def power(x, n):
    # x to a whole power n, exactly; the caller has checked x != 0 when n < 0.
    [1, 1] => r
    abs(n) => k
    for i in [1:k]:
        frac.times(r, x) => r
    if n < 0:
        return frac.over([1, 1], r)
    return r

def apply(op, a, b):
    # [value, problem] for a op b.
    if op == "+":
        return [frac.plus(a, b), ""]
    if op == "-":
        return [frac.minus(a, b), ""]
    if op == "*":
        return [frac.times(a, b), ""]
    if op == "/":
        if frac.is_zero(b):
            return [[0, 1], "division by zero"]
        return [frac.over(a, b), ""]
    if b[1] != 1:
        return [[0, 1], "a power that is not a whole number: " + frac.text(b)]
    if abs(b[0]) > 20:
        return [[0, 1], "a power above 20"]
    if frac.is_zero(a) and b[0] < 0:
        return [[0, 1], "zero to a negative power"]
    return [power(a, b[0]), ""]

def evaluate(postfix):
    # The corpus case rpn-evaluator's stack: push numbers; an operator pops
    # what it needs - two, or one for neg - and pushes its result. Returns
    # [value, steps, problem]: each step [token, stack after].
    [] => stack
    [] => steps
    for t in postfix:
        if t[0] == "num":
            stack + [t[1]] => stack
        elif t[1] == "neg":
            if len(stack) < 1:
                return [[0, 1], steps, "a minus sign with no number after it"]
            frac.minus([0, 1], stack[len(stack) - 1]) => stack[len(stack) - 1]
        else:
            if len(stack) < 2:
                return [[0, 1], steps, t[1] + " without two numbers to work on"]
            stack[len(stack) - 2] => a
            stack[len(stack) - 1] => b
            stack[0:len(stack) - 2] => stack
            apply(t[1], a, b) => res
            if res[1] != "":
                return [[0, 1], steps, res[1]]
            stack + [res[0]] => stack
        steps + [[t, stack[0:len(stack)]]] => steps
    if len(stack) != 1:
        return [[0, 1], steps, "numbers with no operator between them"]
    return [stack[0], steps, ""]
```

Python projection of expr.eml:

```python
import frac

def precedence(op):
    if op == "+" or op == "-":
        return 1
    if op == "*" or op == "/":
        return 2
    if op == "neg":
        return 3
    return 4

def right_assoc(op):
    return op == "^" or op == "neg"

def tokens(s):
    out = []
    i = 0
    while i < len(s):
        c = s[i]
        if c == " ":
            i = i + 1
        elif c >= "0" and c <= "9" or c == ".":
            j = i
            while j < len(s) and (s[j] >= "0" and s[j] <= "9" or s[j] == "."):
                j = j + 1
            x = frac.parse(s[i:j])
            if len(x) == 0:
                return [["bad", "the number " + s[i:j]]]
            out = out + [["num", x]]
            i = j
        elif c == "+" or c == "-" or c == "*" or c == "/" or c == "^":
            if c == "-" and (len(out) == 0 or out[len(out) - 1][0] == "op" or out[len(out) - 1][0] == "("):
                out = out + [["op", "neg"]]
            else:
                out = out + [["op", c]]
            i = i + 1
        elif c == "(" or c == ")":
            out = out + [[c, ""]]
            i = i + 1
        else:
            return [["bad", "the character " + c]]
    return out

def shown(t):
    if t[0] == "num":
        return frac.text(t[1])
    if t[0] == "op":
        if t[1] == "neg":
            return "neg"
        return t[1]
    return t[0]

def to_postfix(ts):
    output = []
    stack = []
    steps = []
    problem = ""
    for t in ts:
        if t[0] == "num":
            output = output + [t]
        elif t[0] == "op":
            moving = True
            while moving and len(stack) > 0 and stack[len(stack) - 1][0] == "op" and t[1] != "neg":
                top = stack[len(stack) - 1][1]
                if precedence(top) > precedence(t[1]) or precedence(top) == precedence(t[1]) and not right_assoc(t[1]):
                    output = output + [stack[len(stack) - 1]]
                    stack = stack[0:len(stack) - 1]
                else:
                    moving = False
            stack = stack + [t]
        elif t[0] == "(":
            stack = stack + [t]
        else:
            while len(stack) > 0 and stack[len(stack) - 1][0] != "(":
                output = output + [stack[len(stack) - 1]]
                stack = stack[0:len(stack) - 1]
            if len(stack) == 0:
                problem = "a ) with no ( before it"
                return [output, steps, problem]
            stack = stack[0:len(stack) - 1]
        steps = steps + [[t, output, stack]]
    while len(stack) > 0:
        if stack[len(stack) - 1][0] == "(":
            problem = "a ( that is never closed"
            return [output, steps, problem]
        output = output + [stack[len(stack) - 1]]
        stack = stack[0:len(stack) - 1]
    return [output, steps, problem]

def power(x, n):
    r = [1, 1]
    k = abs(n)
    for i in range(1, k+1):
        r = frac.times(r, x)
    if n < 0:
        return frac.over([1, 1], r)
    return r

def apply(op, a, b):
    if op == "+":
        return [frac.plus(a, b), ""]
    if op == "-":
        return [frac.minus(a, b), ""]
    if op == "*":
        return [frac.times(a, b), ""]
    if op == "/":
        if frac.is_zero(b):
            return [[0, 1], "division by zero"]
        return [frac.over(a, b), ""]
    if b[1] != 1:
        return [[0, 1], "a power that is not a whole number: " + frac.text(b)]
    if abs(b[0]) > 20:
        return [[0, 1], "a power above 20"]
    if frac.is_zero(a) and b[0] < 0:
        return [[0, 1], "zero to a negative power"]
    return [power(a, b[0]), ""]

def evaluate(postfix):
    stack = []
    steps = []
    for t in postfix:
        if t[0] == "num":
            stack = stack + [t[1]]
        elif t[1] == "neg":
            if len(stack) < 1:
                return [[0, 1], steps, "a minus sign with no number after it"]
            stack[len(stack) - 1] = frac.minus([0, 1], stack[len(stack) - 1])
        else:
            if len(stack) < 2:
                return [[0, 1], steps, t[1] + " without two numbers to work on"]
            a = stack[len(stack) - 2]
            b = stack[len(stack) - 1]
            stack = stack[0:len(stack) - 2]
            res = apply(t[1], a, b)
            if res[1] != "":
                return [[0, 1], steps, res[1]]
            stack = stack + [res[0]]
        steps = steps + [[t, stack[0:len(stack)]]]
    if len(stack) != 1:
        return [[0, 1], steps, "numbers with no operator between them"]
    return [stack[0], steps, ""]
```

### frac.eml

```eml
# P062 expression calculator - exact fractions, from P007 (calculator) by
# way of P038, P044, P056 and P060.
# A number is a list [n, d]: n / d in lowest terms with d > 0. Integers have
# no size limit, but EML has no //, and a / b goes through a float that cannot
# hold a large quotient exactly, so whole-number division is written out.

def quotient(a, b):
    # a // b for whole numbers a >= 0 and b > 0, exact at any size. Long
    # division by doubling: take away the largest b * 2^k that still fits.
    0 => q
    while a >= b:
        b => m
        1 => k
        while m + m <= a:
            m + m => m
            k + k => k
        a - m => a
        q + k => q
    return q

def gcd(a, b):
    while b != 0:
        a % b => r
        b => a
        r => b
    return a

def make(n, d):
    # n / d in lowest terms with a positive denominator (d != 0).
    if d < 0:
        0 - n => n
        0 - d => d
    abs(n) => a
    gcd(a, d) => g
    if n < 0:
        return [0 - quotient(a, g), quotient(d, g)]
    return [quotient(a, g), quotient(d, g)]

def plus(x, y):
    return make(x[0] * y[1] + y[0] * x[1], x[1] * y[1])

def minus(x, y):
    return make(x[0] * y[1] - y[0] * x[1], x[1] * y[1])

def times(x, y):
    return make(x[0] * y[0], x[1] * y[1])

def over(x, y):
    # x / y; the caller has checked that y is not zero.
    return make(x[0] * y[1], x[1] * y[0])

def is_zero(x):
    return x[0] == 0

def digits_value(s):
    # The value of a string of 1 to 9 digits, otherwise -1.
    if s == "" or len(s) > 9:
        return -1
    0 => n
    for c in s:
        if not (c in "0123456789"):
            return -1
        n * 10 + int(c) => n
    return n

def parse(s):
    # "3", "-2", "3/4", "-0.25" as a fraction; [] if it is not a number.
    1 => sign
    if len(s) > 0 and s[0] == "-":
        -1 => sign
        s[1:len(s)] => s
    0 => k
    while k < len(s) and s[k] != "/" and s[k] != ".":
        k + 1 => k
    if k == len(s):
        digits_value(s) => n
        if n < 0:
            return []
        return make(sign * n, 1)
    digits_value(s[0:k]) => whole
    s[k + 1:len(s)] => rest
    digits_value(rest) => part
    if whole < 0 or part < 0:
        return []
    if s[k] == "/":
        if part == 0:
            return []
        return make(sign * whole, part)
    # a decimal point: 0.25 is 25 / 100
    1 => scale
    for c in rest:
        scale * 10 => scale
    return make(sign * (whole * scale + part), scale)

def less(x, y):
    return x[0] * y[1] < y[0] * x[1]

def decimal(x, places):
    # x to the given number of decimal places, halves rounded away from zero,
    # with "about " in front when the value does not end there exactly.
    "" => sign
    abs(x[0]) => n
    if x[0] < 0:
        "-" => sign
    1 => scale
    for k in [1:places]:
        scale * 10 => scale
    quotient(2 * n * scale + x[1], 2 * x[1]) => t
    "" => about
    if (n * scale) % x[1] != 0:
        "about " => about
    str(quotient(t, scale)) => whole
    str(t % scale) => part
    while len(part) < places:
        "0" + part => part
    # drop trailing zeros of an exact value
    if about == "":
        while len(part) > 0 and part[len(part) - 1] == "0":
            part[0:len(part) - 1] => part
    if t == 0:
        "" => sign
    if part == "":
        return about + sign + whole
    return about + sign + whole + "." + part

def text(x):
    # "3", "-3", "3/4", "-3/4".
    if x[1] == 1:
        return str(x[0])
    return str(x[0]) + "/" + str(x[1])
```

Python projection of frac.eml:

```python
def quotient(a, b):
    q = 0
    while a >= b:
        m = b
        k = 1
        while m + m <= a:
            m = m + m
            k = k + k
        a = a - m
        q = q + k
    return q

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def make(n, d):
    if d < 0:
        n = 0 - n
        d = 0 - d
    a = abs(n)
    g = gcd(a, d)
    if n < 0:
        return [0 - quotient(a, g), quotient(d, g)]
    return [quotient(a, g), quotient(d, g)]

def plus(x, y):
    return make(x[0] * y[1] + y[0] * x[1], x[1] * y[1])

def minus(x, y):
    return make(x[0] * y[1] - y[0] * x[1], x[1] * y[1])

def times(x, y):
    return make(x[0] * y[0], x[1] * y[1])

def over(x, y):
    return make(x[0] * y[1], x[1] * y[0])

def is_zero(x):
    return x[0] == 0

def digits_value(s):
    if s == "" or len(s) > 9:
        return -1
    n = 0
    for c in s:
        if not c in "0123456789":
            return -1
        n = n * 10 + int(c)
    return n

def parse(s):
    sign = 1
    if len(s) > 0 and s[0] == "-":
        sign = -1
        s = s[1:len(s)]
    k = 0
    while k < len(s) and s[k] != "/" and s[k] != ".":
        k = k + 1
    if k == len(s):
        n = digits_value(s)
        if n < 0:
            return []
        return make(sign * n, 1)
    whole = digits_value(s[0:k])
    rest = s[k + 1:len(s)]
    part = digits_value(rest)
    if whole < 0 or part < 0:
        return []
    if s[k] == "/":
        if part == 0:
            return []
        return make(sign * whole, part)
    scale = 1
    for c in rest:
        scale = scale * 10
    return make(sign * (whole * scale + part), scale)

def less(x, y):
    return x[0] * y[1] < y[0] * x[1]

def decimal(x, places):
    sign = ""
    n = abs(x[0])
    if x[0] < 0:
        sign = "-"
    scale = 1
    for k in range(1, places+1):
        scale = scale * 10
    t = quotient(2 * n * scale + x[1], 2 * x[1])
    about = ""
    if n * scale % x[1] != 0:
        about = "about "
    whole = str(quotient(t, scale))
    part = str(t % scale)
    while len(part) < places:
        part = "0" + part
    if about == "":
        while len(part) > 0 and part[len(part) - 1] == "0":
            part = part[0:len(part) - 1]
    if t == 0:
        sign = ""
    if part == "":
        return about + sign + whole
    return about + sign + whole + "." + part

def text(x):
    if x[1] == 1:
        return str(x[0])
    return str(x[0]) + "/" + str(x[1])
```

## README

# P062 - Expression calculator

Type an expression the usual way, with + - * /, ^ for whole powers,
brackets and minus signs, like (1 + 2) * -3 / 4. The calculator turns it
into postfix order with Dijkstra's shunting-yard algorithm, works the
postfix out on a stack, and can show both step by step. Every value is an
exact fraction. Postfix can also be typed in directly.

- `main.eml` - the menu, reading expressions and postfix, the step tables
  and the answer
- `expr.eml` - tokens, the shunting yard, and the stack that works postfix
  out
- `frac.eml` - exact fractions, from P007 by way of P038, P044, P056 and
  P060

How each part works:

- Tokens: numbers (whole or decimal), the operators, and brackets. A minus
  sign at the start, after an operator or after "(" is a sign, shown as
  neg; anywhere else it subtracts.
- Shunting yard. A number goes straight to the output. An operator first
  moves to the output every operator waiting on the stack that binds
  tighter, or as tight when it groups to the left, and then waits itself.
  "(" waits, and ")" moves operators out until its "(".
- Precedence, from loosest: + and -, then * and /, then the sign, then ^.
  So -2^2 is -(2^2) = -4, and (-2)^2 is 4. ^ groups to the right, so
  2 ^ 3 ^ 2 is 2^9 = 512; the rest group to the left, so 8 - 3 - 2 is 3.
- Stack. As in the corpus case `rpn-evaluator`, a number is pushed, and an
  operator pops what it needs - two numbers, or one for the sign - and
  pushes its result. One number left at the end is the answer.
- The answer is a fraction in lowest terms, with its decimal. A decimal
  that does not end is rounded to six places and marked with ~.
- A power must be a whole number no larger than 20. Dividing by zero and
  zero to a negative power are refused with the reason.

What is checked: menu choices 1 to 4; expressions of up to 80 characters
with numbers, + - * / ^, brackets and spaces; brackets that match;
operators with numbers to work on; postfix tokens separated by spaces.
An empty answer cancels.

Sessions: `sessions/basic.in` gives:
- (1 + 2) * -3 / 4 step by step, = -9/4 = -2.25;
- 2 ^ 3 ^ 2 step by step, grouping to the right, = 512;
- 1/3 + 1/6 = 1/2, -2^2 + (-2)^2 = 0, 10 / 4 - 0.5 = 2, and 1/3, which is
  ~0.333333;
- the postfix 3 4 + 2 *, = 14.

`sessions/bad-input.in` gives:
- menu choices 0 and x, and an empty expression;
- unbalanced brackets both ways, a $, the number 1.2.3, "2 +" and "2 3";
- division by zero, 2 ^ 0.5, 2 ^ 21 and 0 ^ -1;
- an empty pair of brackets, and 81 characters;
- the postfix "3 +", "1 x" and an empty one.

Built on the verified corpus case `rpn-evaluator` (postfix worked out by
pushing numbers and popping two for each operator).