# base tree code from http://knuth.luther.edu/~leekent/CS2Plus/chap6/chap6.html # changed this code to allow for variable functions, and change infix expressions to postfix # added variable node class to consider when both nodes have variables in them import queue class EquationTree: def __init__(self): self.root = EqualsNode() self.root.left = None self.root.right = None def updateNode(self, parent, left, newNode): if left: parent.left = newNode else: parent.right = newNode self.printTree() def get_expression(self): self.output = "" self.inorder(self.root) print("output is: ", self.output) return self.output def inorder(self, node): if node: self.inorder(node.left) self.output += str(node.value) self.inorder(node.right) def evaluate(self, parent, left): # can simplify this to call helper function if left: if parent.left.canEval(): print("parent.left.left is ", parent.left.left.value) print("parent.left.right is ", parent.left.right) if isinstance(parent.left.left, NumNode): print("num node") print("evaluating", parent.left.eval()) newNode = NumNode(parent.left.eval()) else: print("variable node") print("evaluating", parent.left.eval()) newNode = VariableNode(str(parent.left.eval()) + "x") parent.left = newNode elif parent.left.left != None and parent.left.left.canEval(): self.evaluate(parent.left, True) elif parent.left.right != None and parent.left.right.canEval(): self.evaluate(parent.left, False) else: if parent.right.canEval(): if isinstance(parent.right.left, NumNode): print("evaluating", parent.right.eval()) newNode = NumNode(parent.right.eval()) else: print("evaluating", parent.right.eval()) newNode = VariableNode(str(parent.right.eval()) + "x") parent.right = newNode elif parent.right.left != None and parent.right.left.canEval(): self.evaluate(parent.right, True) elif parent.right.right != None and parent.right.right.canEval(): self.evaluate(parent.right, False) def printTree(self): q = queue.Queue() q.enqueue(self.root) while not q.isEmpty(): currentNode = q.front() if currentNode.left != None: b = Branch() q.enqueue(b) q.enqueue(currentNode.left) if currentNode.right != None: q.enqueue(currentNode.right) print(q.dequeue().value, end =' ') class Branch: def __init__(self): self.value = "\n" self.left = None self.right = None class EqualsNode: def __init__(self): self.value = "=" class TimesNode: def __init__(self, left, right): self.left = left self.right = right self.value = "*" def eval(self): '''if check_if_variables(str(self.left.eval()), str(self.right.eval())) == "both_vars": v1 = str(self.left.eval()).split("x")[0] v2 = str(self.right.eval()).split("x")[0] evalStr = v1 + "*" + v2 return eval(evalStr) else: return self.left.eval() * self.right.eval()''' #if isinstance(self.left, VariableNode) and isinstance(self.right,VariableNode): # return self.left.eval()*self.right.eval() #elif isinstance(self.left,VariableNode) or isinstance(self.right,VariableNode): # print("can't combine variables of differing types") #need some sort of combined node here i think #else: return self.left.eval() * self.right.eval() def inorder(self): return "(" + self.left.inorder() + " * " + self.right.inorder() + ")" class PlusNode: def __init__(self, left, right): self.left = left self.right = right self.value = "+" def canEval(self): if isinstance(self.left, VariableNode) and isinstance(self.right,VariableNode): return True elif isinstance(self.left, NumNode) and isinstance(self.right, NumNode): return True else: return False def getInverse(self): return MinusNode(None,None) def eval(self): #print("left value ", self.left) #print(isinstance(self.left, NumNode)) #print("right value ", self.right.value()) return self.left.eval() + self.right.eval() def inorder(self): return "(" + self.left.inorder() + " + " + self.right.inorder() + ")" class MinusNode: def __init__(self,left, right): self.left = left self.right = right self.value = "-" def canEval(self): if isinstance(self.left, VariableNode) and isinstance(self.right,VariableNode): return True elif isinstance(self.left, NumNode) and isinstance(self.right, NumNode): return True else: return False def getInverse(self): return PlusNode(None, None) def eval(self): return self.left.eval() - self.right.eval() def inorder(self): return "(" + self.left.inorder() + "-" + self.right.inorder() + ")" class NumNode: def __init__(self, num): self.value = num self.left = None self.right = None def eval(self): return self.value def canEval(self): return False # not an operator def inorder(self): return str(self.value) class VariableNode: def __init__(self, value): self.value = value self.left = None self.right = None def eval(self): # get value before x return int(self.value.split("x")[0]) def canEval(self): return False #not an operator def inorder(self): return str(self.eval()) def check_if_variables(x, y): if 'x' in x and 'x' in y: return "both_vars" elif 'x' in x or 'x' in y: return "one_var" else: return "both_const" def E(q): if q.isEmpty(): raise ValueError("Invalid Prefix Expression") token = q.dequeue() if token == "+": return PlusNode(E(q),E(q)) if token == "*": return TimesNode(E(q),E(q)) if token == "-": return MinusNode(E(q), E(q)) #try: if "x" in token: output = VariableNode(token) # make a different class for variable node else: output = NumNode(int(token)) #except: # print("Not a valid operation, need variables of like terms") # output = NumNode(float(0)) return output OPERATORS = set(['+', '-', '*', '/', '(', ')']) PRIORITY = {'+':1, '-':1, '*':2, '/':2} def infix_to_prefix(formula): # this method was taken from open source https://github.com/lilianweng/LeetcodePython/blob/master/expression.py op_stack = [] exp_stack = [] for ch in formula.split(): if not ch in OPERATORS: exp_stack.append(ch) elif ch == '(': op_stack.append(ch) elif ch == ')': while op_stack[-1] != '(': op = op_stack.pop() a = exp_stack.pop() b = exp_stack.pop() exp_stack.append( op+b+a ) op_stack.pop() # pop '(' else: while op_stack and op_stack[-1] != '(' and PRIORITY[ch] <= PRIORITY[op_stack[-1]]: op = op_stack.pop() a = exp_stack.pop() b = exp_stack.pop() exp_stack.append( op+" "+b+" "+a ) op_stack.append(ch) # leftover while op_stack: op = op_stack.pop() a = exp_stack.pop() b = exp_stack.pop() exp_stack.append( op+" "+b+" "+a ) print(exp_stack[-1]) return exp_stack[-1] def add_to_tree(q, root, left): if not q.isEmpty(): token = q.dequeue() operator = False if token == "+": newNode = PlusNode(None, None) operator = True elif token == "*": newNode = TimesNode(None, None) operator = True elif token == "-": newNode = MinusNode(None, None) operator = True elif "x" in token: newNode = VariableNode(token) else: newNode = NumNode(int(token)) if left: root.left = newNode else: root.right = newNode if operator: add_to_tree(q, newNode, True) add_to_tree(q, newNode, False) return newNode def generate_tree(equation): t = EquationTree() expressions = equation.split("=") x1 = infix_to_prefix(expressions[0]) x2 = infix_to_prefix(expressions[1]) lst1 = x1.split() q1 = queue.Queue() lst2 = x2.split() q2 = queue.Queue() for token in lst1: q1.enqueue(token) add_to_tree(q1, t.root, True) # add expression tree to left side of equation tree for token in lst2: q2.enqueue(token) add_to_tree(q2, t.root, False) # add expression tree to right side of equation tree t.printTree() return t def eval_tree(expression): '''x = NumNode(5) y = NumNode(4) p = PlusNode(x,y) t = TimesNode(p, NumNode(6)) root = PlusNode(t, NumNode(3)) print(root.eval()) print(root.inorder())''' #x = input("Please enter a prefix expression: ") x = infix_to_prefix(expression) lst = x.split() q = queue.Queue() for token in lst: q.enqueue(token) root = E(q) result = root.eval() print(root.eval()) print(root.inorder()) return result #print(infix_to_prefix("3 + 4 - 6")) def split_equation(equation): expressions = equation.split("=") return expressions def main(): #exp = split_equation("4x * 3x + 2") #x = eval_tree(exp[0]) '''eqTree = EquationTree() x1 = VariableNode("4x") x2 = NumNode(3) x3 = NumNode(2) x4 = NumNode(7) t = PlusNode(x1,x2) t2 = PlusNode(x3,x4) eqTree.root.left = t eqTree.root.right = t2 eqTree.printTree()''' equationTree = generate_tree("4x + 3 = 2 + 7") print(equationTree.root.left.canEval()) print(equationTree.root.right.canEval()) newNode = NumNode(equationTree.root.right.eval()) equationTree.updateNode(equationTree.root, False, newNode) equationTree.printTree() equationTree.get_expression() ''' print("old node should be 2, is ", oldNum.value) print("moved node should be 7, is ", moveNode.value) print("new op is ", newOp.value) ''' if __name__ == "__main__": main()