Как перейти от использования стека к использованию только родительского поля в дереве разбора? - PullRequest
Новая
       51

Как перейти от использования стека к использованию только родительского поля в дереве разбора?

0 голосов
/ 16 мая 2018

У меня есть домашнее задание о создании дерева разбора после ввода строки, заключенной в круглые скобки, и последующей печати дерева разбора. Он просит меня изменить пару вещей, и одна из них - изменить способ отслеживания родительского узла. В исходном коде они используют для этого стек, но мой инструктор сказал нам просто использовать вместо него родительский узел.

У меня весь код работает в одном и том же файле, вместо того, чтобы иметь дело с импортом на данный момент.

Вот правила, которые алгоритм использует для создания дерева разбора:

  • Если текущим токеном является '(', добавьте новый узел в качестве левого дочернего элемента текущего узла и перейдите к левому дочернему элементу.
  • Если текущий токен находится в списке ['+','-', '^', '/','*'], задайте корневое значение текущего узла для оператора, представленного текущим токеном. Добавьте новый узел в качестве правого дочернего элемента текущего узла и перейдите к правому дочернему элементу.
  • Если текущим токеном является число, установите корневое значение текущего узла равным номеру и верните его родителю.
  • Если текущим токеном является ')', перейдите к родителю текущего узла.

Сначала создается двоичное дерево: 

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        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 setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

Далее следует класс Stack, который я хочу изменить: 

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)

После этого происходит сборка дерева разбора (я отмечу вещи знаком «#», который, я думаю, мне нужно изменить): 

def buildParseTree(fpexp): #fpexp is a string that we want to create into a parse tree
    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(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:
            raise ValueError
    return eTree

Вот код в pastebin с функцией print и выражениями, которые я тестирую: https://pastebin.com/DmdkHuhF

...