How to fix 'NoneType' has no attribute 'key', when trying to compare a key value to a string

Question

I am writing a program where the user inputs a postfix expression and it outputs the answer. Current I am stuck when Using my 'evaluate' function within my for loop.

Inside my For loop Main.py:

else:

    # Debug Code
    print('{}: Else'.format(i))
    print('{}: Length'.format(len(stack)))

    Node.right = stack.pop()
    Node.left = stack.pop()
    Node = TreeNode(str(i))
    stack.push(str(i))

    # Debug Code
    print('{}: Right Key'.format(Node.right))
    print('{}: Left Key'.format(Node.left))
    print('{}: Node Key'.format(Node.key))
    print('{}: Node Key Type'.format(type(Node.key)))

    Node = evaluate(Node)
    stack.push(int(Node))

I am getting the error below:

Traceback (most recent call last):
  File "c:\Users\dpr48\main.py", line 49, in <module>
    Node = evaluate(Node)
  File "c:\Users\dpr48\main.py", line 10, in evaluate
return evaluate(node.left) + evaluate(node.right)
  File "c:\Users\dpr48\main.py", line 9, in evaluate
    if node.key == '+':
AttributeError: 'NoneType' object has no attribute 'key'

So my question is why is it not using the 'TreeNode' class to get the key value? As well as the line of code that should define the 'Node.left' as the 'stack.pop()' value and 'Node.right' as the 'stack.pop()' value ends up not changing either of them and leaves them as None, as found in the 'Debug Code' that I have implemented to see what the program is doing interenally.

Provided each class used below:

Main.py

from Stack import Stack
from TreeNode import TreeNode

def evaluate(node):
    if node.key == '+':
        return evaluate(node.left) + evaluate(node.right)
    elif node.key == '-':
         return evaluate(node.left) - evaluate(node.right)
    elif node.key == '*':
         return evaluate(node.left) * evaluate(node.right)
    elif node.key == '/':
         return evaluate(node.left) / evaluate(node.right)
    else:
        return node.key

stack = Stack()
exp = "23+"
list = [*exp]

for i in list:
    if i.isdigit() is True:

        # Debug Code
        print('{}: True'.format(i))

        Node = TreeNode(int(i))
        stack.push(int(i))

    else:

        # Debug Code
        print('{}: Else'.format(i))
        print('{}: Length'.format(len(stack)))

        Node.right = stack.pop()
        Node.left = stack.pop()
        Node = TreeNode(str(i))
        stack.push(str(i))

        # Debug Code
        print('{}: Right Key'.format(Node.right))
        print('{}: Left Key'.format(Node.left))
        print('{}: Node Key'.format(Node.key))
        print('{}: Node Key Type'.format(type(Node.key)))

        Node = evaluate(Node)
        stack.push(int(Node))

print(evaluate(stack.node))

Stack.py

from Node import Node
from LinkedList import LinkedList

class Stack:
    def __init__(self):
        self.list = LinkedList()
    
    def push(self, new_item):
        # Create a new node to hold the item
        new_node = Node(new_item)
    
        # Insert the node as the list head (top of stack)
        self.list.prepend(new_node)

    def pop(self):
        # Copy data from list's head node (stack's top node)
        popped_item = self.list.head.data
    
        # Remove list head
        self.list.remove_after(None)
    
        # Return the popped item
        return popped_item

    def __len__(self):
        node = self.list.head # Start at head of stack to count until stack returns Null
        count = 0 
        while node != None:
            node = node.next
            count+=1

        return count # Returning length of stack

LinkedList.py

class LinkedList:
def __init__(self):
    self.head = None
    self.tail = None

def append(self, new_node):
    if self.head == None:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        self.tail = new_node

def prepend(self, new_node):
    if self.head == None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head = new_node

def insert_after(self, current_node, new_node):
    if self.head == None:
        self.head = new_node
        self.tail = new_node
    elif current_node is self.tail:
        self.tail.next = new_node
        self.tail = new_node
    else:
        new_node.next = current_node.next
        current_node.next = new_node

def remove_after(self, current_node):
    # Special case, remove head
    if (current_node == None) and (self.head != None):
        succeeding_node = self.head.next
        self.head = succeeding_node  
        if succeeding_node == None: # Remove last item
            self.tail = None
    elif current_node.next != None:
        succeeding_node = current_node.next.next
        current_node.next = succeeding_node
        if succeeding_node == None: # Remove tail
            self.tail = current_node

Node.py

class Node:
def __init__(self, initial_data):
    self.data = initial_data
    self.next = None

TreeNode.py

class TreeNode:
# Constructor assigns the given key, with left and right
# children assigned with None.
def __init__(self, key):
    self.key = key 
    self.left = None
    self.right = None
 

Answer 1

There are several issues:

• Node is the name of a class, yet you use the same name for a TreeNode instance, shadowing the class name. This is not the main problem, but certainly not advised. Related: Don't use PascalCase for instances, but camelCase. So node, not Node.

• You assign to Node.right when you have not yet defined Node yet, which happens later with Node = TreeNode(str(i)). You should first assign to Node (well, better node) and only then assign to its attributes.

• With Node.right = stack.pop() you clearly expect the stack to contain TreeNode instances, but with stack.push(str(i)) you push strings. That will lead to the problems you describe. The stack should not be populated with strings, but with TreeNode objects.

• At the end of the else block you call evaluate, and then push that result value to the stack. This is wrong and should be removed. The evaluation should only happen when you have completed the tree, and it should not involve the stack. The stack has a role in building the tree, not in evaluating it.

• The final print line makes an access to stack.node, but stack has no node attribute. You'll want to pop the top item from the stack, which (if the input syntax was correct) should only have 1 node left on it, representing the root of the tree.

• Not a problem, but i is guaranteed to be a string (with length 1), so there is no need to call str on it.

Here is the corrected code:

for i in list:
    if i.isdigit() is True:
        node = TreeNode(int(i))  # lowercase name
        stack.push(node)  # don't push string, but object
    else:
        node = TreeNode(i)  # First create the node
        node.right = stack.pop()  # Then assign to its attributes
        node.left = stack.pop()
        stack.push(node)  # don't push string
        # Don't evaluate here, nor push anything else to the stack


print(evaluate(stack.pop()))