1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
|
from fractions import Fraction
from sys import argv
# Parser (Rekursiver Abstieg)
# ===========================
class SyntaxError(ValueError):
pass
def scan(s):
a = []; i = 0; n = len(s)
while i < n:
if s[i] in "+-*/^()=x":
if s[i] == "x" and len(a) != 0 and isinstance(a[-1], int):
a.append("*")
a.append(s[i])
i += 1
elif s[i].isdigit():
j = i
while i<n and s[i].isdigit(): i += 1
a.append(int(s[j:i]))
elif s[i].isspace():
i += 1
else:
raise SyntaxError(
"unerwartetes Zeichen: '{}'".format(s[i]))
a.append(None)
return a
def expect_token(a, i):
if a[i] is None:
raise SyntaxError("unerwartetes Ende der Eingabe")
else:
return a[i]
def atom(a, i):
t = expect_token(a, i)
if isinstance(t, int) or t == "x":
return i + 1, a[i]
elif t == "(":
i,x = expression(a, i + 1)
if expect_token(a, i) != ")":
raise SyntaxError(
"')' wurde erwartet, es kam aber '{}'".format(a[i]))
return i + 1, x
else:
raise SyntaxError(
"unerwartetes Symbol: '{}'".format(t))
def power(a, i):
i, x = atom(a, i)
if a[i] == "^":
i, y = negation(a, i + 1)
return i, ["^", x, y]
else:
return i, x
def negation(a, i):
if a[i] == "-":
i, x = power(a, i + 1)
return i, ["~", x]
else:
return power(a, i)
def multiplication(a, i):
i, x = negation(a, i)
op = a[i]
while op == "*" or op == "/":
i, y = negation(a, i + 1)
x = [op, x, y]
op = a[i]
return i, x
def addition(a, i):
i, x = multiplication(a, i)
op = a[i]
while op == "+" or op == "-":
i, y = multiplication(a, i + 1)
x = [op, x, y]
op = a[i]
return i, x
def comparison(a, i):
(i, x) = addition(a, i)
if a[i] == "=":
(i, y) = addition(a, i + 1)
x = ["=", x, y]
return i, x
def expression(a, i):
return comparison(a, i)
def ast(a):
i, t = expression(a, 0)
if a[i] is None:
return t
else:
raise SyntaxError(
"Ende der Eingabe wurde erwartet, es kam aber: '{}'"
.format(a[i]))
# Auswertung eines abstrakten Syntaxbaums
# =======================================
dispatch = {
"+": lambda x, y: x + y,
"-": lambda x, y: x - y,
"*": lambda x, y: x*y,
"/": lambda x, y: x/y,
"^": lambda x, y: x**y,
"~": lambda x: -x,
"=": lambda x, y: x == y
}
def evaluator(x):
def evaluate(t):
if isinstance(t, int):
return Fraction(t, 1)
elif t == "x":
return x
else:
return dispatch[t[0]](*map(evaluate, t[1:]))
return evaluate
def cond(value):
return value if isinstance(value, bool) else value == 0
# Folge der rationalen Zahlen (Calkin-Wilf-Folge)
# ===============================================
def rat_seq(n):
bits = "{:b}".format(n)
q = (0, 1)
for bit in bits:
if bit == "0":
q = (q[0], q[0] + q[1])
else:
q = (q[0] + q[1], q[1])
return Fraction(q[0], q[1])
# Hauptprogramm
# =============
def find_solutions(t, n):
for k in range(0, n):
try:
q = rat_seq(k)
evaluate = evaluator(q)
if cond(evaluate(t)): print(q)
if q == 0: continue
evaluate = evaluator(-q)
if cond(evaluate(t)): print(-q)
except ZeroDivisionError:
continue
def main():
n = int(argv[1]) if len(argv) == 2 else 10000
while True:
try:
s = input("> ")
if s == "": continue
find_solutions(ast(scan(s)), n)
except SyntaxError as e:
print("Syntaxfehler: " + str(e))
except (KeyboardInterrupt, EOFError):
print()
break
main() |
