Создание дерева выражений из заданной нотации - PullRequest
Новая
       23

Создание дерева выражений из заданной нотации

0 голосов
/ 18 апреля 2020

Я пытаюсь создать дерево выражений либо из постфикса, либо из инфикса, а затем могу распечатать дерево выражений в виде постфикса или инфикса в зависимости от того, как оно будет пройдено. Тем не менее, я не уверен насчет логики c, если она верна, более того, я продолжаю получать сообщение об ошибке объект типа «Узел» не имеет атрибута «left» при попытке печати с использованием printinfix

Для постфикса моя логика c выглядит следующим образом: Если (встретившись, мы вставляем текущий узел в стек и go его левому потомку. Если был обнаружен оператор, мы go к родительскому узлу текущего узла и вставьте его, а затем go к его правому дочернему элементу, если встретились), мы go к родительскому узлу. Если обнаружен операнд, мы go установим ему текущее значение и go его родительскому элементу

для инфикса Мой лог c выглядит следующим образом: правило 1: чтение (создайте узел слева и перейдите к нему правило 2: чтение операнда или вставка в текущем узле и переход к родительскому правилу 3: оператор чтения * назначьте значение узлу и current = right или перейти к правому правилу 4: чтение) go to parent

мои логики c для печати в инфиксах - это рекурсивная печать влево, root, а затем вправо

Вот мой код: 

class ParseTree:
    class Node:
        def __init__(self, data, left = None, right = None):
            self.data, self.left, self.right = data, left, right
        def __str__(self):
            return self.data
    def __init__(self, root = None):
        self.root = root
    def __str__(self):
         pass # to be implemented

    def fromPostfix(self, expression=""):
        s=[] #maintain parents
        for c in expression.split():
             if c=='(':
                s.append(self.Node)#first push the current node on the stack
                self.Node.data=c
                self.Node= self.Node.left
             elif c in ["+", "-", "*", "/", "^", "#"]:
                 self.Node=s.pop()
                 s.append(self.Node)  # first push the current node on the stack
                 self.Node=self.Node.right
             elif c == ')':
                 self.Node=s.pop()
             elif c.isnumeric() or c.isalpha() :

                     self.Node.data=int(c)
                     self.Node=s.pop()
             else:

                     raise ValueError("Invalid token! ")


    def fromInfix(self, expression=""):
        """infix:
          rule 1: reading ( create node on the left and move to it
          rule 2: reading operand or A insert at current nod and move to parent
          rule 3: reading operator * assign value to the node and current =right or move to the right
          rule 4: reading ) go to parent
          """
        s=[] #maintain parents
        for c in expression.split():
             if c=='(':
                s.append(self.Node)#first push the current node on the stack
                self.Node= self.Node.left
             elif c in ["+", "-", "*", "/", "^", "#"]:
                 s.append(self.Node)
                 self.Node.data = c
                 self.Node=self.Node.right
             elif c == ')':
                 self.Node.data = c
                 self.Node=s.pop()
             elif c.isnumeric() or c.isalpha() :
                     self.Node.data=c
                     self.Node=s.pop()
             else:

                     raise ValueError("Invalid token! ")

    def printinfix(self):
        if self is None:
            return
        self.infix(self.Node.left)
        print(self.Node.data+" ")
        self.infix(self.Node.right)


t=ParseTree("(a+b)/2")
t.fromPostfix()
t.infix()
...