|
1
|
|
|
import functools |
|
2
|
|
|
import operator |
|
3
|
|
|
import re |
|
4
|
|
|
|
|
5
|
|
|
|
|
6
|
|
|
class Polynomial: |
|
7
|
|
|
def __init__(self, val): |
|
8
|
|
|
if isinstance(val, list): |
|
9
|
|
|
self.plist = val |
|
10
|
|
|
|
|
11
|
|
|
def __add__(self, other): |
|
12
|
|
|
if len(self.plist) > len(other.plist): |
|
13
|
|
|
new = [i for i in self.plist] |
|
14
|
|
|
for i in range(len(other.plist)): |
|
15
|
|
|
new[i] += other.plist[i] |
|
16
|
|
|
else: |
|
17
|
|
|
new = [i for i in other.plist] |
|
18
|
|
|
for i in range(len(self.plist)): |
|
19
|
|
|
new[i] += self.plist[i] |
|
20
|
|
|
return Polynomial(new) |
|
21
|
|
|
|
|
22
|
|
|
def __radd__(self, other): |
|
23
|
|
|
return self.__add__(other) |
|
24
|
|
|
|
|
25
|
|
|
def __sub__(self, other): |
|
26
|
|
|
return self.__add__(other.__neg__()) |
|
27
|
|
|
|
|
28
|
|
|
def __rsub__(self, other): |
|
29
|
|
|
return -Polynomial.__sub__(other) |
|
30
|
|
|
|
|
31
|
|
|
def __mul__(self, other): |
|
32
|
|
|
result = [] |
|
33
|
|
|
for i in range(len(other.plist)): |
|
34
|
|
|
result.append( |
|
35
|
|
|
Polynomial([0] * i + [j * other.plist[i] for j in self.plist]) |
|
36
|
|
|
) |
|
37
|
|
|
return functools.reduce(operator.add, result) |
|
38
|
|
|
|
|
39
|
|
|
def __rmul__(self, other): |
|
40
|
|
|
return self.__mul__(other) |
|
41
|
|
|
|
|
42
|
|
|
def __neg__(self): |
|
43
|
|
|
return Polynomial([-1]) * self |
|
44
|
|
|
|
|
45
|
|
|
def __repr__(self): |
|
46
|
|
|
result = [] |
|
47
|
|
|
for i in range(len(self.plist)): |
|
48
|
|
|
if i == 0: |
|
49
|
|
|
result.insert(0, str(self.plist[i])) |
|
50
|
|
|
else: |
|
51
|
|
|
if self.plist[i] == 0: |
|
52
|
|
|
continue |
|
53
|
|
|
else: |
|
54
|
|
|
if self.plist[i] == 1: |
|
55
|
|
|
base_str = 'x' |
|
56
|
|
|
else: |
|
57
|
|
|
base_str = str(self.plist[i]) + '*x' |
|
58
|
|
|
if i == 1: |
|
59
|
|
|
result.insert(0, base_str) |
|
60
|
|
|
else: |
|
61
|
|
|
result.insert(0, base_str + '**' + str(i)) |
|
62
|
|
|
for i in range(1, len(result)): |
|
63
|
|
|
if result[i][0] != '-': |
|
64
|
|
|
result[i] = '+' + result[i] |
|
65
|
|
|
for i in range(len(result)): |
|
66
|
|
|
if result[i][0] == '-': |
|
67
|
|
|
if result[i][1] == '1' and '*' in result[i] and result[i][2] == '*': |
|
68
|
|
|
result[i] = result[i][0] + result[i][3:] |
|
69
|
|
|
|
|
70
|
|
|
if result[-1] == '+0' and len(result) > 1: |
|
71
|
|
|
result.pop() |
|
72
|
|
|
return ''.join(result) |
|
73
|
|
|
|
|
74
|
|
|
|
|
75
|
|
|
def tokenise(expr): |
|
76
|
|
|
symbols = list(expr) |
|
77
|
|
|
# merge numbers |
|
78
|
|
|
changed = True |
|
79
|
|
|
while changed: |
|
80
|
|
|
changed = False |
|
81
|
|
|
for i in range(len(symbols) - 1): |
|
82
|
|
|
try: |
|
83
|
|
|
int(symbols[i]) |
|
84
|
|
|
int(symbols[i + 1]) |
|
85
|
|
|
symbols = symbols[:i] + [symbols[i] + symbols[i + 1]] + symbols[i + 2 :] |
|
86
|
|
|
changed = True |
|
87
|
|
|
break |
|
88
|
|
|
except ValueError: |
|
89
|
|
|
pass |
|
90
|
|
|
|
|
91
|
|
|
# convert numbers and x |
|
92
|
|
|
for i in range(len(symbols)): |
|
93
|
|
|
try: |
|
94
|
|
|
int(symbols[i]) |
|
95
|
|
|
symbols[i] = Polynomial([int(symbols[i])]) |
|
96
|
|
|
except ValueError: |
|
97
|
|
|
if symbols[i] == 'x': |
|
98
|
|
|
symbols[i] = Polynomial([0, 1]) |
|
99
|
|
|
return symbols |
|
100
|
|
|
|
|
101
|
|
|
|
|
102
|
|
|
def calc(tokens): |
|
103
|
|
|
while len(tokens) > 1: |
|
104
|
|
|
if ')' in tokens: |
|
105
|
|
|
right_bracket = tokens.index(')') |
|
106
|
|
|
sub_tokens = tokens[:right_bracket] |
|
107
|
|
|
sub_tokens.reverse() |
|
108
|
|
|
left_bracket = len(sub_tokens) - sub_tokens.index('(') - 1 |
|
109
|
|
|
tokens = ( |
|
110
|
|
|
tokens[:left_bracket] |
|
111
|
|
|
+ calc(tokens[left_bracket + 1 : right_bracket]) |
|
112
|
|
|
+ tokens[right_bracket + 1 :] |
|
113
|
|
|
) |
|
114
|
|
|
elif '*' in tokens: |
|
115
|
|
|
index = tokens.index('*') |
|
116
|
|
|
tokens = ( |
|
117
|
|
|
tokens[: index - 1] |
|
118
|
|
|
+ [tokens[index - 1] * tokens[index + 1]] |
|
119
|
|
|
+ tokens[index + 2 :] |
|
120
|
|
|
) |
|
121
|
|
|
elif '-' in tokens: |
|
122
|
|
|
index = tokens.index('-') |
|
123
|
|
|
tokens = ( |
|
124
|
|
|
tokens[: index - 1] |
|
125
|
|
|
+ [tokens[index - 1] - tokens[index + 1]] |
|
126
|
|
|
+ tokens[index + 2 :] |
|
127
|
|
|
) |
|
128
|
|
|
else: |
|
129
|
|
|
index = tokens.index('+') |
|
130
|
|
|
tokens = ( |
|
131
|
|
|
tokens[: index - 1] |
|
132
|
|
|
+ [tokens[index - 1] + tokens[index + 1]] |
|
133
|
|
|
+ tokens[index + 2 :] |
|
134
|
|
|
) |
|
135
|
|
|
return tokens |
|
136
|
|
|
|
|
137
|
|
|
|
|
138
|
|
|
def simplify(expr): |
|
139
|
|
|
tokens = tokenise(expr) |
|
140
|
|
|
result = calc(tokens)[0] |
|
141
|
|
|
return str(result) |
|
142
|
|
|
|
|
143
|
|
|
|
|
144
|
|
|
if __name__ == "__main__": # pragma: no cover |
|
145
|
|
|
# These "asserts" using only for self-checking and not necessary for |
|
146
|
|
|
# auto-testing |
|
147
|
|
|
assert simplify("(x-1)*(x+1)") == "x**2-1", "First and simple" |
|
148
|
|
|
assert simplify("(x+1)*(x+1)") == "x**2+2*x+1", "Almost the same" |
|
149
|
|
|
assert simplify("(x+3)*x*2-x*x") == "x**2+6*x", "Different operations" |
|
150
|
|
|
assert simplify("x+x*x+x*x*x") == "x**3+x**2+x", "Don't forget about order" |
|
151
|
|
|
assert simplify("(2*x+3)*2-x+x*x*x*x") == "x**4+3*x+6", "All together" |
|
152
|
|
|
assert simplify("x*x-(x-1)*(x+1)-1") == "0", "Zero" |
|
153
|
|
|
assert simplify("5-5-x") == "-x", "Negative C1" |
|
154
|
|
|
assert simplify("x*x*x-x*x*x-1") == "-1", "Negative C0" |
|
155
|
|
|
|
KenMercusLai /
checkio
