In [1]:
import string
import operator
from pythonds9.basic.stack import Stack
from pythonds9.tree.binary_tree import BinaryTree
from pythonds9.tree.utils import viz_tree
from rcviz import CallGraph, viz
In [2]:
def build_parse_tree(fpexp):
    fplist = fpexp.split()
    p_stack = Stack()
    e_tree = BinaryTree('')
    
    p_stack.push(e_tree)
    current_tree = e_tree
    
    for i in fplist:
        if i == "(":
            # create our left child, and descend to it
            current_tree.insert_left('')
            p_stack.push(current_tree)
            current_tree = current_tree.get_left_child()
        elif i.isdigit():
            current_tree.set_root_val(int(i))
            parent = p_stack.pop()
            current_tree = parent
        elif i in ["+", "-", "/", "*"]:
            current_tree.set_root_val(i)
            current_tree.insert_right('')
            p_stack.push(current_tree)
            current_tree = current_tree.get_right_child()
        elif i == ")":
            current_tree = p_stack.pop()
        else:
            raise ValueError("invalid expression given!")
            
    return e_tree
In [3]:
cg = CallGraph()
@viz(cg)
def evaluate(parse_tree):
    opers = {
        "+": operator.add,
        "-": operater.sub,
        "*": operator.mul,
        "/": operator.truediv
    }
    
    left_c = parse_tree.get_left_child()
    right_c = parse_tree.get_right_child()
    
    if left_c and right_c:
        # recursion on expression
        fn = opers[parse_tree.get_root_val()]
        return fn(evaluate(left_c), evaluate(right_c))
    else:
        # base case
        return parse_tree.get_root_val()
In [4]:
def evaluate_post(tree):
    opers = {
        "+": operator.add,
        "-": operater.sub,
        "*": operator.mul,
        "/": operator.truediv
    }
    
    res1 = None
    res2 = None
    
    if tree:
        res1 = evaluate_post(tree.get_left_child())
        res2 = evaluate_post(tree.get_right_child())
        if res1 and res2:
            fn = opers[tree.get_root_val()]
            return fn(res1, res2)
        else:
            return tree.get_root_val()
In [5]:
def preorder(tree):
    if tree:
        print(tree.get_root_val(), end=" ")
        preorder(tree.get_left_child())
        preorder(tree.get_right_child())
In [6]:
def postorder(tree):
    if tree:
        postorder(tree.get_left_child())
        postorder(tree.get_right_child())
        print(tree.get_root_val(), end=" ")
In [7]:
def inorder(tree):
    if tree:
        inorder(tree.get_left_child())
        print(tree.get_root_val(), end=" ")
        inorder(tree.get_right_child())
In [20]:
def printexp(tree):
    s_val = ""
    if tree:
        s_val = "(" + printexp(tree.get_left_child())
        s_val += str(tree.get_root_val())
        s_val += printexp(tree.get_right_child()) + ")"
        
    return s_val

Testing our Expression Functions

In [8]:
pt = build_parse_tree("( ( 10 + 5 ) * 3 )")
In [9]:
viz_tree(pt)
Out[9]:
node0 * node1 + node0:f0->node1:f1 node4 3 node0:f2->node4:f1 node2 10 node1:f0->node2:f1 node3 5 node1:f2->node3:f1
In [10]:
inorder(pt)
10 + 5 * 3 
In [11]:
preorder(pt)
* + 10 5 3 
In [12]:
postorder(pt)
10 5 + 3 * 
In [21]:
printexp(pt)
Out[21]:
'(((10)+(5))*(3))'

Updating BinaryTree class to include traversal methods

In [13]:
class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.left_child = None
        self.right_child = None
        
    def insert_left(self, key):
        if self.left_child is None:
            self.left_child = BinaryTree(key)
        else:  # if there IS a left child
            t = BinaryTree(key)
            t.left_child = self.left_child
            self.left_child = t
            
    def insert_right(self, key):
        if self.right_child is None:
            self.right_child = BinaryTree(key)
        else:  # if there IS a right child
            t = BinaryTree(key)
            t.right_child = self.right_child
            self.right_child = t
            
    def get_right_child(self):
        return self.right_child
    
    def get_left_child(self):
        return self.left_child
    
    def get_root_val(self):
        return self.key
    
    def set_root_val(self, new_key):
        self.key = new_key
    
    def preorder(self):
        print(self.key)
        
        if self.left_child:
            self.left_child.preorder()
        
        if self.right_child:
            self.right_child.preorder()

    def inorder(self):
        if self.left_child:
            self.left_child.inorder()
            
        print(self.key)

        if self.right_child:
            self.right_child.inorder()
 
    def postorder(self):
        if self.left_child:
            self.left_child.postorder()

        if self.right_child:
            self.right_child.postorder()

        print(self.key)
    
    def __repr__(self):
        return f"BinaryTree({self.key!r})"

After updating it in pythonds9, test again

In [14]:
pt
Out[14]:
BinaryTree('*')
In [15]:
pt.preorder()
* + 10 5 3 
In [16]:
pt.inorder()
10 + 5 * 3 
In [17]:
pt.postorder()
10 5 + 3 *