pythonlinked-liststacknodespostfix-notation

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


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
 

Solution

  • There are several issues:

    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()))