Project 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.
3 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 answerexpr.eml- tokens, the shunting yard, and the stack that works postfix outfrac.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (35 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (15 lines)
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
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (expr.py)
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 (frac.py)
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])