CMPSC 122 Homework 5


Category: You will Instantly receive a download link for .zip solution file upon Payment


5/5 - (2 votes)

This assignment will implement an expression tree, suitable for C++ arithmetic expressions. It will also make use of polymorphism to enable additional operations, such as the conditional operator.

Problem Description
Many compiler optimizations for expressions are very much simplified if the internal representation is something other than a sequence of tokens (either in infix or postfix form). A very useful representation is the expression tree, which can represent any form of expression.
Here is a short list of the sorts of expressions that will be supported by this phase of the assignment:

numbers (3, 5, 12)
variables (x, n, abc)
binary operations (+, *, <) conditional expression: test ? true case : false case This last example will likely be unfamiliar to most students. It consists of three sub-expressions. The 'test' is first evaluated and found to be either true or false. If true, the 'true case' is evaluated; otherwise, the 'false case' is evaluated. Here is a very simple application: y = x > 0 ? x : 0-x
If x is greater than 0, then the conditional expression returns the value of x; otherwise it subtracts x from 0. The result in either case is assigned to y. This effectively is an absolute value operation as a single assignment statement.
Parsing and Interpretation
There will be two sorts of changes to be made to the part of the program that parses the infix expression.
I. Support for new operators
There is the conditional expression above, using the ‘?’ and ‘:’ symbols; and there are also the relational operators (>, <, >=, <=, ==, !=) Here is a summary of the precedence of all operators for this project, with the lowest precedence at the top) Category operators Associativity Assignment = Right to Left Conditional ? : Right to Left Relational > < >= <= == != Left to right Additive + - Left to right Multiplicative * / % Left to right Some C++ references actually give equal precedence to the Assignment and Conditional operators, but coding might still be easier if they are separate. Technically, == != have lower precedence than the other relational operators, but for simplicity it is acceptable to treat them equally for this course. NOTE: new_split_iter will need to be aware that some operators now have two characters. Fortunately, in all such cases, the second character is '=' II: Building and Returning an Expression Tree What your parsing functions return is changing again (for the last time). In Homework 1 and 2, they returned a computed result as a value. In Homework 3 and 4, they constructed a postfix expression, returned through an iterator generator Now, they will construct and return an expression tree. The function that recognizes variable names and numeric values will return leaves of this tree. The other functions will receive sub-trees from the functions they call, and build larger trees from those components. Parsing the expression tree will appear in from peekable import Peekable, peek from newsplit import new_split_iter from exprtree import Value,Var,Oper,Cond def tree_assign( iter ): .... where each of these functions will return some kind of ExprTree node (among the four options imported here). For example, tree_assign would be constructing an "Oper" object if it finds an '=' operator. The bottom of the instructor's looks like this at the moment: def to_expr_tree( expr ): return tree_assign(Peekable((new_split_iter(expr)))) if __name__ == "__main__": print (to_expr_tree("A = 5")) print (to_expr_tree("A = 2 + 3 * B - xyz")) print (to_expr_tree("x < 0 ? 0 - x : x")) Defining an Expression Tree The required operations for this tree will be these: The ability to construct the tree (using __init__) The ability to traverse the tree (using __iter__) This is to produce a fully-parenthesized infix expression The ability to produce a postfix iterator for eval_postfix The ability to evaluate the tree directly The details for these operations depend on what an individual tree node looks like, and this is best accomplished by using polymorphism, or derived classes. Here is a bit of sample code from the instructor's solution at this time: (in from abc import ABCMeta,abstractmethod from vartree import VarTree class ExprTree(metaclass=ABCMeta): """Abstract class for expression""" def __str__(self): return ' '.join( str(x) for x in iter(self) ) # All of the derived class mus implement these functions @abstractmethod def __iter__(self): """an inorder iterator for this tree node, for display""" pass @abstractmethod def postfix(self): """a post-order iterator to create a postfix expression""" pass @abstractmethod def evaluate(self, variables): """evaluate using the existing variables""" pass class Var(ExprTree): """A variable leaf""" def __init__(self, n): self._name = n def __iter__(self): yield self._name def postfix(self): yield self._name def evaluate(self, variables): return variables.lookup(self._name) The only really interesting thing about this Var class is that evaluating it means consulting a collection of variables from the previous assignment. The functionality is much more interesting for the binary operations and the conditional expression. Perhaps a quote of the testing code from would be more informative: if __name__ == '__main__': V = VarTree() VA = Var("A") Sum = Oper(Value(2),'+',Value(3)) A = Oper(VA,'=',Sum) print( "Infix iteration: ", list(A) ) print( "String version ", A ) print( "Postfix iteration: ", list(A.postfix() )) print( "Execution: ", A.evaluate(V) ) print( "Afterwards, A = ", VA.evaluate(V) ) # If A == 5, return A+2 else return 3 CondTest = Cond(Oper(VA,'==',Value(5)),Oper(VA,'+',Value(2)),Value(3)) print( CondTest,'-->‘,CondTest.evaluate(V) )

Infix iteration: [‘(‘, ‘A’, ‘=’, ‘(‘, 2, ‘+’, 3, ‘)’, ‘)’]
String version ( A = ( 2 + 3 ) )
Postfix iteration: [‘A’, 2, 3, ‘+’, ‘=’]
Execution: 5
Afterwards, A = 5
( ( A == 5 ) ? ( A + 2 ) : 3 ) –> 7

Assignment Specifications
Here is a list of files relevant to this phase of the project. One is completely new; one is a new revision of a previous file; one has a minor feature change, and the other three are unchanged but included for completeness.
Defines the expression tree, as illustrate in the previous section.
given an iterator to an infix expression, produces an expression tree
divides into tokens, generating an iterator, with added support for new operators
Implements a binary tree for variables (no new code required)
evaluates a postfix expression, given an iterator, with added support for variables
used as a stack for postfix evaluation
You are also encouraged to insert your own unit testing into each file, but that will not be itself graded.

Testing and Evaluation
Here are a few lines of code from the instructor’s solution and test at this time of writing:

(in the test program)
from infixtotree import to_expr_tree
from evalpostfix import eval_postfix
from vartree import VarTree

def test(expr):
tree = to_expr_tree(expr)
print (expr, ‘:’, tree.evaluate(V))
if ‘?’ not in expr:
print(“from postfix:”, eval_postfix(tree.postfix())

V = VarTree()
test(“a = 2 + 3*4”)
test(“b = a > 0 ? a+1 : a-1”)

(NOTE: eval_postfix doesn’t use this same VarTree V)
Since eval_postfix is from a previous assignment, it does not need to support the conditional operator. It is here just to test your tree traversal.
Extra Credit Option
Support the logical operators and and or, represented using those words (NOT the symbols && and ||).

Precedence order: ‘=’ < 'or' < 'and' < '==' The words are chosen so that Python's eval function can still be used to evaluate them. Include suitable unit tests for this feature.