Description
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 infixtotree.py:
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 infixtotree.py 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 exprtree.py)
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 exprtree.py 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) )
Output:
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.
exprtree.py
Defines the expression tree, as illustrate in the previous section.
infixtotree.py
given an iterator to an infix expression, produces an expression tree
newsplit.py
divides into tokens, generating an iterator, with added support for new operators
vartree.py
Implements a binary tree for variables (no new code required)
evalpostfix.py
evaluates a postfix expression, given an iterator, with added support for variables
linkedlist.py
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.