# CMPSC 122 Homework 4

\$30.00

## Description

This assignment will focus on the implementation of a simple binary tree, which will associate variable names with their values. It also involves minor changes to pre-existing functionaltiy to make use of the tree.

Problem Description
The project so far supports calculations on numeric values, but most computational statements (and even most calculators) are not limited to numeric literal values. They usually also include variables.
So this assignment will add the ability to assign to variables, and then to later use their values in further computations. This will require a data structure that will associate variables with values, and to do that efficiently, will use a binary search tree.

Parsing and Interpretation
There will be one additional operator for this homework — the sasignment operator (‘=’). We will support the C++ meaning of this operator, that not only assigns to a variable, but ‘computes’ the assigned value. The assignment operator has the lowest precedence (be aware of what that means for the order of calling functions when parsing.
Here are a few examples:

x = 1 + (y = 4) # assign 4 to y and 5 to x
x = y = z = 4 # assign 4 to z, then y, then x
x = y = z + 4 # add 4 to z, then assign sum to y and x
x = 1 + y = 4 # invalid input: cannot assign 4 to (1+y)
Special Note:
It may be tempting to make the function for assignment operator to be just like the ones for sum and product. That would not be correct, because it would do the operations from left to right. HOWEVER: it can be fixed just by changing the name of one function call within the new while loop. Furthermore, if you do so correctly, the while loop would only repeat 0 or 1 times, so the word ‘while’ could optionally be replaced with a different word.
The postfix forms for the legal expression would be similar to the other operators:

x 1 y 4 = + = # assign 4 to y, add 1 to it, then assign 5 to x
x y z 4 = = = # assign 4 to z, then y, then x
x y z 4 + = = # add 4 to z, then assign sum to y and x
A binary search tree will be used when evaluating the postfix expression. If a variable is the left operand of an assignment, the variable will receive the value. If a variable appears at any other time, its value is retrieved for a computation.
That means that the postfix evaluation function’s stack of ‘values’ will now have a mixture of values and variable names, and will need to be able to know the difference and use the information appropriately.

HINT: The instructor discovered that if value = ‘0.3’, value.isdigit() is False. It is safer to check value[0].isdigit(). That will let you more reliably identify whether the stack element is a variable or a number.

Defining a Binary Tree
There is no need for any self-balancing features in this assignment — just the a simple binary tree supporting the ability to store new variables, to associate values with those variables, and to retrieve the value of a variable.
For consistency, call your file vartree.py
Required Features in Implementation
Nested Node class definition for binary tree node
with __slots__ to save list memory
and __init__ a constructor
__init__() a constructor for an empty tree
_search(here, var) recursively search tree rooted ‘here’ for variable ‘var’