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.
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)
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.isdigit(). That will let you more reliably identify whether the stack element is a variable or a number.
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
|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’
returning correct Node, or None if not found
|_insert(here, var, value)||return a search tree with variable inserted or updated
this should be a recursive implementation for immutable behavior
|assign(var, value)||public method to assign to a variable|
|lookup(var)||public method retrieve value of variableif the variable does not yet exist, assign it zero|
|Good functions for Completeness / Practice|
|is_empty()||Identify whether tree is empty|
|__len__()||returns number of elements in list|
|__iter__()||inorder iterator generator(with yield statements)|
|__str__()||represents entire tree as a string
For full credit, this must be no worse than log-linear time and not quadratic
One new file and three modified files are to appear in the solution to this assignment:
You are also encouraged to insert your own unit testing into each file, but that will not be itself graded.
Here are a few lines of code from the instructor’s solution and test at this time of writing:
(in the test program) from infixtoiter import to_postfix from evalpostfix import eval_postfix def test(expr): print (expr, ':', eval_postfix( to_postfix( expr )) ) test("b=6") # b=6 : 6 test("b * 9") # b * 9 : 54
You may assume that all expressions are legal C expressions with binary operators, but you may NOT assume that:
Support those optional class features listed above, along with suitable unit tests.
Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.
You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.Read more
Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.Read more
Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.Read more
Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.Read more
By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.Read more