Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Simplification by jcg
#sipmlify
# expression is seen as a train to shunt
"""
Djikstra shunting algorithm
(queue)
/-number--- \
(stack ) / \ digit string
res -----------------------var------------------car
\ /
\ / operator : +, -, *, ~ (unary -)
\ /
|
|
|op (stack)
polynom = dict monome {2 : 3, 1 : 5, 0 : 2 } = 3*x^2 + 5*x + 2
monome = key value exponent
degree coeff
"""
#utilitaries
# queues
def enqueue(c: "car", q: "queue"): # put a car in a queue
q.append(c)
def dequeue(q: "queue")-> "car": # extract a car from queue
return q.pop(0)
def is_empty_queue(q: "queue") -> bool:# is the queue empty ?
return q == []
#stack
def push(c: "obj", s: "stack"): # push on stack
s.append(c)
def pop(s: "stack") -> "obj": # pop stack
return s.pop()
def top(s: "stack") -> "obj": # top of stack
return s[-1]
def is_empty_stack(s: "stack") -> bool:# is the stack empty ?
return s == []
def compute_number(q: "queue") ->int : # extract number from queue and empties queue
n = 0
while not is_empty_queue(q) :
c = dequeue(q)
n *= 10
n += ord(c) - ord('0')
return n
def is_begin_parenth_expr(c: "car") -> bool: # char is begin of grouping
return c == '('
def is_end_parenth_expr(c: "car") -> bool: # char is end of grouping
return c == ')'
def is_var(x: "token"): # x is var
return x == "x"
def is_number(x : "token") : # x is a number
return type(x)==type(1)
# str conversions
def exponent_to_multstr(n : int) -> str : # 3 -> "x*x*x"
return '*'.join('x' for x in range(n))
def exponent_to_powstr(n : int) -> str : # 3 -> "x**3"
return 'x'+('' if n==1 else '**'+str(n))
def monome_to_str(coeff : int, exp : int) -> str : # 3,5 -> "3*x**5"
if coeff == 0 or exp == 0:
return str(coeff)
if abs(coeff) == 1 :
if coeff < 0 :
prefix = '-'
else :
prefix = ''
else :
prefix = str(coeff) + ('*' if exp > 0 else '')
return prefix + exponent_to_powstr(exp)
def polynome_to_str(p : "polynome")->str : # {1:3, 0 :2, 2:-1} -> "-x**2+3*x+2"
p = [(p[i],i) for i in sorted(p)]
if p==[] :
return '0'
p.sort(key = lambda x : x[1], reverse = True)
s = monome_to_str(*p[0])
for m in p[1:] :
if m[0]>0 :
s+='+'
elif m[0]==0 :
continue
s+=monome_to_str(*m)
return s
def polynomstack_to_str(stack) : # displays stack of operands waiting for evaluate
return ", ".join(map(polynome_to_str, stack))
def priority(c : "operator") -> int : # priority of operators
if c in '+-' :
return 1
elif c in '*/' :
return 2
elif c in '~' : # unary minus
return 3
else :
return 0
def evaluate(op : "operator", A : "polynome" , B : "polynome") -> "polynome" : #eval operation on A and B, remove 0 coeffs
if op == '+' :
res = add(A, B)
elif op == '-' :
res = diff(A, B)
elif op=='*' :
res = mult(A, B)
else :
return None
# remove all null coeff
for i, k in list(res.items()):
if k == 0:
del res[i]
return res
def minus(A: "polynome") -> "polynome" : # opposite of A
res = {}
for k in A:
res[k] = -A[k]
return res
def add( A : "polynome" , B : "polynome") -> "polynome": #A+B
res = {}
for i in A:
res[i] = A[i]
for i in B:
res[i] = res.get(i,0) + B[i]
return res
def diff( A : "polynome" , B : "polynome") -> "polynome": #A-B
res = add(A, minus(B))
return res
def mult( A : "polynome" , B : "polynome") -> "polynome" : # A*B
res = {}
for i in A:
for j in B:
res[i+j] = res.get(i+j, 0) + A[i] * B[j]
return res
def add_result(token : "token", stack : "stack") : # push token on stack of results
if is_number(token):
push({0: token}, stack)
elif is_var(token):
push({1: 1}, stack)
else : # operator : eval and push result
if token == '~' :
push(minus(pop(stack)),stack)
else:
B = pop(stack)
A = pop(stack)
C = evaluate(token, A, B)
push(C, stack)
def simplify(expr, debug=None) :
WAITING, NUMBER, VAR, EXPR = 0,1,2,3 #states
operator_stack = [] # stack of ooperators
expression_stack = [] # stack of expressions
number_queue = [] # queue for building number
state = WAITING # current state,
prec = None # precedent state
def process(c : "char"): #update the stacks, queue, etc.
nonlocal state, prec # current state, precedent state
if state == WAITING:
if c.isdigit(): #we begin to build a a number
enqueue(c, number_queue)
state = NUMBER
else:
if c == ' ':
pass
elif is_var(c):
add_result(c, expression_stack)
prec = EXPR
elif is_begin_parenth_expr(c):
push(c, operator_stack)
prec = WAITING
elif is_end_parenth_expr(c):
while not is_begin_parenth_expr(top(operator_stack)):
op = pop(operator_stack)
add_result(op, expression_stack)
pop(operator_stack)
prec = EXPR
else : #operator
if c == '-' and prec == WAITING :
push('~', operator_stack)
prec = WAITING
else:
while not is_empty_stack(operator_stack) and priority(top(operator_stack))>=priority(c) :
op = pop(operator_stack)
add_result(op, expression_stack)
push(c, operator_stack)
prec = WAITING
elif state == NUMBER :
if c.isdigit():
enqueue(c, number_queue)
# return
else :
x = compute_number(number_queue)
add_result(x, expression_stack)
prec = EXPR
state = WAITING
process(c)
if debug: s = ''
for c in expr.join('()') : # put brackets around expr
process(c)
if debug :
s += c
print("Expression ",expr)
print("expression_stack : <", polynomstack_to_str(expression_stack),">")
print("number_queue : <",number_queue,">")
print("operator_stack : <",', '.join(operator_stack[1:]),">")
print("deja_vu :",repr(s))
input()
#traite(')')
return polynomstack_to_str(expression_stack)
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert simplify("(x-1)*(x+1)") == "x**2-1", "First and simple"
assert simplify("(x+1)*(x+1)") == "x**2+2*x+1", "Almost the same"
assert simplify("(x+3)*x*2-x*x") == "x**2+6*x", "Different operations"
assert simplify("x+x*x+x*x*x") == "x**3+x**2+x", "Don't forget about order"
assert simplify("(2*x+3)*2-x+x*x*x*x") == "x**4+3*x+6", "All together"
assert simplify("x*x-(x-1)*(x+1)-1") == "0", "Zero"
assert simplify("5-5-x") == "-x", "Negative C1"
assert simplify("x*x*x-x*x*x-1") == "-1", "Negative C0"
Oct. 3, 2014
Comments:
