notebook.community



In [36]:

    
class BinaryTree:
    def __init__(self, val):
        self.value=val
        self.right=None
        self.left=None
        
    def get_value(self):
        return self.value
    
    def set_value(self,val):
        self.value=val
        
    def get_right(self):
        return self.right
    
    def get_left(self):
        return self.left
    
    def insert_left(self,v):
        t=BinaryTree(v)
        if self.left:
            t.left=self.left
        self.left=t
        return t
        
    def insert_right(self,v):
        t=BinaryTree(v)
        if self.right:
            t.right=self.right
        self.right=t
        return t

# ----------------------------------------


def build_tree():
    a=BinaryTree('*')
    b=a.insert_left('b')
    b.insert_right('d')

    b.insert_left('x')

    c=a.insert_right('c')
    c.insert_left('e')    
    c.insert_right('f')
    return a

t= build_tree()

import textwrap

def to_str(t,indent):
    if not t: return 'null'
    s= ("""
    {{   
        value: {:}, 
        left:  {:}, 
        right: {:}
    }}""".format(
        t.get_value(),
        to_str(t.get_left(),indent+4), 
        to_str(t.get_right(),indent+4)
    ))
    
    return textwrap.indent(s,' '* indent)
# print(to_str(t,0))




from collections import OrderedDict
import json

def build_dict(t):
    
    if not t: return
    o=OrderedDict()

#     o=dict()

    o['v']=t.get_value()
    
    left=t.get_left()
    if left:
        o['left']=build_dict(left)
    
    right=t.get_right()
    if right:
        o['right']=build_dict(right)
    
    return o
d=build_dict(t)
json.dumps(d)









    Out[36]:





'{"v": "*", "left": {"v": "b", "left": {"v": "x"}, "right": {"v": "d"}}, "right": {"v": "c", "left": {"v": "e"}, "right": {"v": "f"}}}'



In [37]:

    
# VISUALIZATION ----------------------

import networkx as nx
from networkx.drawing.nx_agraph import write_dot, graphviz_layout
import matplotlib.pyplot as plt

def uid_gen():
    n=0
    while True:
        n+=1
        yield n
uid=uid_gen()

def draw_graph(G):
    plt.rcParams["figure.figsize"] = [10.,5.]
    pos =graphviz_layout(G, prog='dot')
    
    node_labels=nx.get_node_attributes(G,'name')

    
    nx.draw(G,pos, with_labels=True,labels=node_labels, width=2, node_size=1000, node_color="orange",alpha=1.0)
    lbls = nx.get_edge_attributes(G,'label')
    nx.draw_networkx_edge_labels(G, pos, edge_labels = lbls)
#     nx.draw_networkx_nodes(G,pos,node_size=2000, nodelist=['x'])
#     nx.draw_networkx_edges(G, pos, alpha=0.9, width=6, edge_color="orange", edgelist=[(1, 'Petya')])
#     plt.figure(1)
    
    plt.show()



import uuid
# import random



def build_graph(g,parent_g_node,t, edge_label=None):
#     global count
    if not t: return
    
    node= next(uid)  #str(uuid.uuid4())  #random.random()    
    g.add_node(node, name=t.get_value())
    if parent_g_node:
        g.add_edge(parent_g_node,node, label=edge_label)


    left=t.get_left()
    right=t.get_right()

    if left:
        build_graph(g,node, left, 'L')
    
    if right:
        build_graph(g,node, right, 'R')
        
    return node




def show_bin_tree(t):
    G=nx.DiGraph()
    root=build_graph(G,None,t )
    draw_graph(G)


show_bin_tree(t)



In [26]:

    
for n in G.nodes.items():
     print(n)
G.edges()
root









    



(1, {'name': '*'})
(2, {'name': 'b'})
(3, {'name': 'x'})
(4, {'name': 'd'})
(5, {'name': 'c'})
(6, {'name': 'e'})
(7, {'name': 'f'})






    Out[26]:





1

Export JSON to use with D3



In [124]:

    
from networkx.readwrite import json_graph
import json
# json.dumps(json_graph.tree_data(G,root='*',  attrs={'children': 'children', 'id': 'name'}))
json.dumps(json_graph.tree_data(G,root=root,  attrs={'children': 'children', 'id': 'id'}))









    Out[124]:





'{"name": "*", "id": 1, "children": [{"name": "b", "id": 2, "children": [{"name": "x", "id": 3}, {"name": "d", "id": 4}]}, {"name": "c", "id": 5, "children": [{"name": "e", "id": 6}, {"name": "f", "id": 7}]}]}'

Using the information from above we can define four rules as follows:

If the current token is a '(', add a new node as the left child of the current node, and descend to the left child.
If the current token is in the list ['+','-','/','*'], set the root value of the current node to the operator represented by the current token. Add a new node as the right child of the current node and descend to the right child.
If the current token is a number, set the root value of the current node to the number and return to the parent.
If the current token is a ')', go to the parent of the current node.



In [27]:

    
class BinaryTree:
    def __init__(self, val):
        self.value = val
        self.right = None
        self.left = None

    def get_value(self):
        return self.value

    def set_value(self, val):
        self.value = val

    def get_right(self):
        return self.right

    def get_left(self):
        return self.left

    def insert_left(self, v):
        t = BinaryTree(v)
        if self.left:
            t.left = self.left
        self.left = t
        return t

    def insert_right(self, v):
        t = BinaryTree(v)
        if self.right:
            t.right = self.right
        self.right = t
        return t


# from pythonds.basic.stack import Stack
# from pythonds.trees.binaryTree import BinaryTree

def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = []  # Stack()
    eTree = BinaryTree('')
    pStack.append(eTree)  # push(eTree)
    currentTree = eTree

    for i in fplist:
        if i == '(':
            currentTree.insert_left('')  # insertLeft('')
            pStack.append(currentTree)  # push(currentTree)
            currentTree = currentTree.get_left()  # getLeftChild()

        elif i in ['+', '-', '*', '/']:
            currentTree.set_value(i)  # setRootVal(i)
            currentTree.insert_right('')  # insertRight('')
            pStack.append(currentTree)  # push(currentTree)
            currentTree = currentTree.get_right()  # getRightChild()

        elif i == ')':
            currentTree = pStack.pop()

        elif i not in ['+', '-', '*', '/', ')']:
            try:
                currentTree.set_value(int(i))  # setRootVal(int(i))
                parent = pStack.pop()
                currentTree = parent

            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(i))

    return eTree


pt = buildParseTree("( ( 10 + 5 ) * ( 6 - 7 ) ")
G=nx.DiGraph()
root=build_graph(G,None,pt )

draw_graph(G)



In [7]:

    
def getId=

class No:
    def __init__(self, v):
        self.data=v
        self.left=None
        self.right=None
        
no=No(5)



In [38]:

    
import matplotlib.rcsetup as rcsetup
print(rcsetup.all_backends)









    



['GTK', 'GTKAgg', 'GTKCairo', 'MacOSX', 'Qt4Agg', 'Qt5Agg', 'TkAgg', 'WX', 'WXAgg', 'GTK3Cairo', 'GTK3Agg', 'WebAgg', 'nbAgg', 'agg', 'cairo', 'gdk', 'pdf', 'pgf', 'ps', 'svg', 'template']