Parse Tree Python

Parse Tree Python

Implementasi tree yang lengkap secara struktur dapat digunakan untuk menyelesaikan malasah ril, di antaranya adalah parse tree (pohon uraian).

Langkah pertama dalam pembangunan suatu parse tree Adalah memecah string ekspresi ke dalam daftar tokens. Ada 4 jenis token berbeda yang perlu diperhatikan: kurung left, kurung kanan, operator dan operan. Kita tahun bahwa kapanpun kita membaca kurung kiri kita

memulai suatu ekspresi baru, dan karena itu kita membuat suatu tree baru untuk menyesuaikan ekspresi tersebut. Sebaliknya, kapanpun kita membaca suatu kurung kanan, kita telah menyelesaikan suatu ekspresi. Kita juda mengetahui bahwa operan akan menjadi node daun (leave) dan anak-anak (children) dari operator-operatornya. Terakhir, kita mengetahui bahwa setiap operator akan mempunyai anak kiri dan kanan.

Berdasarkan informasi di atas kita dapat mendefinisikan 4 rule berikut:
1. Jika current token adalah '(', tambahkan node baru sebagai anak kiri (left child) dari current node, dan turunkan ke anak kiri tersebut.
2. Jika current token adalah operator dalam list ['+','-','/','*'], set nilai root dari current node ke operator yang direpresentasikan oleh current token. Tambahkan node baru sebagai anak nakan dari current node dan turunkan ke anak kanan tersebut.
3. Jika current token adalah suatu bilangan, set nilai root dari current node ke bilangan tersebut dan kembali ke induknya.
4. Jika current token adalah ')', pindahkan ke induk dari current node.

Sekarang mari kita manfaatkan 4 aturan di atas untuk menguji ekspresi matematika (3 + (4 * 5)). Ekspresi ini akan diurai ke dalam daftar token ['(', '3', '+', '(', '4', '*', '5' ,')',')']. Awalnya dimulai dengan suatu parse tree yang mengandung node root kosong.


Source Code :

from __future__ import print_function

class Stack:

    def __init__(self):

        self.items = []

    def isEmpty(self):

        return self.items==[]

    def push(self,items):

        self.items.append(items)

    def pop(self):

        return self.items.pop()

    def peek(self):

        return self.items[len(self.items)-1]

    def size(self):

        return len(self.items)

    

class Binarytree:

    def __init__(self,root):

        self.key = root

        self.leftChild = None

        self.rightChild = None

    def insertLeft(self,newNode):

        if self.leftChild == None :

            self.leftChild = Binarytree(newNode)

        else :

            t = Binarytree(newNode)

            t.leftChild = self.leftChild

            self.leftChild = t

    def insertRight(self,newNode):

        if self.rightChild == None :

            self.rightChild = Binarytree(newNode)

        else :

            t = Binarytree(newNode)

            t.rightChild = self.rightChild

            self.rightChild = t

    def getrightChild(self):

        return self.rightChild

    def getleftChild(self):

        return self.leftChild

    def getrootVal(self):

        return self.key

    def setrootVal(self,obj):

        self.key = obj

    def size(left):

        count = 0

        selfleft = self

        selfright = self

        while selfleft.getleftChild() != None or selfright.getrightChild() != None :

            count += 1

            if selfleft.getleftChild() != None:

                selfleft = selfleft.getleftChild()

            else :

                selfright = selfright.getrightChild()

        return count

    

def buildParseTree(fpexp):

    fplist = fpexp.split()

    pStack = Stack()

    eTree = Binarytree("")

    pStack.push(eTree)

    currentTree = eTree

    for i in fplist:

        if i == "(":

            currentTree.insertLeft("")

            pStack.push(currentTree)

            currentTree = currentTree.getleftChild()

        elif i not in ["+","-","*","/",")"]:

            currentTree.setrootVal(int(i))

            parent = pStack.pop()

            currentTree = parent

        elif i in ["+","-","*","/"]:

            currentTree.setrootVal(i)

            currentTree.insertRight("")

            pStack.push(currentTree)

            currentTree = currentTree.getrightChild()

        elif i == ")":

            currentTree = pStack.pop()

        else:

            return ("Error")

    return eTree

def Inorder(tree):

    if tree != None:

        Inorder(tree.getleftChild())

        print(tree.getrootVal(),end=" ")

        Inorder(tree.getrightChild())

def Preorder(tree):

    if tree != None:

        print(tree.getrootVal(),end=" ")

        Preorder(tree.getleftChild())

        Preorder(tree.getrightChild())

def Postorder(tree):

    if tree != None :

        Postorder(tree.getleftChild())

        Postorder(tree.getrightChild())

        print(tree.getrootVal(),end=" ")

pt = buildParseTree( "( ( 3 + ( 4 * 5 ) ) )" )

Inorder(pt)

print ()

Preorder(pt)

print ()

Postorder(pt)