dsap.trees.expression_tree.ExpressionTree

class documentation

class ExpressionTree(LinkedBinaryTree):

View In Hierarchy

An arithmetic expression tree.

Method __init__ Create an expression tree.
Method __str__ Return string representation of the expression.
Method evaluate Return the numeric result of the expression.
Method _evaluate_recur Return the numeric result of subtree rooted at p.
Method _parenthesize_recur Append piecewise representation of p's subtree to resulting list.

Inherited from LinkedBinaryTree:

Class Position An abstraction representing the location of a single element.
Method __len__ Return the total number of elements in the tree.
Method left Return the Position of p's left child (or None if no left child).
Method num_children Return the number of children of Position p.
Method parent Return the Position of p's parent (or None if p is root).
Method right Return the Position of p's right child (or None if no right child).
Method root Return the root Position of the tree (or None if tree is empty).
Class _Node Lightweight, nonpublic class for storing a node.
Method _add_left Create a new left child for Position p, storing element e.
Method _add_right Create a new right child for Position p, storing element e.
Method _add_root Place element e at the root of an empty tree and return new Position.
Method _attach Attach trees t1 and t2, respectively, as the left and right subtrees of the external Position p.
Method _delete Delete the node at Position p, and replace it with its child, if any.
Method _make_position Return Position instance for given node (or None if no node).
Method _replace Replace the element at position p with e, and return old element.
Method _validate Return associated node, if position is valid.
Instance Variable _root Undocumented
Instance Variable _size Undocumented

Inherited from BinaryTree (via LinkedBinaryTree):

Method children Generate an iteration of Positions representing p's children.
Method inorder Generate an inorder iteration of positions in the tree.
Method positions Generate an iteration of the tree's positions.
Method sibling Return a Position representing p's sibling (or None if no sibling).
Method _subtree_inorder Generate an inorder iteration of positions in subtree rooted at p.

Inherited from Tree (via LinkedBinaryTree, BinaryTree):

Method __iter__ Generate an iteration of the tree's elements.
Method breadthfirst Generate a breadth-first iteration of the positions of the tree.
Method depth Return the number of levels separating Position p from the root.
Method height Return the height of the subtree rooted at Position p.
Method is_empty Return True if the tree is empty.
Method is_leaf Return True if Position p does not have any children.
Method is_root Return True if Position p represents the root of the tree.
Method postorder Generate a postorder iteration of positions in the tree.
Method preorder Generate a preorder iteration of positions in the tree.
Method _height_bad Return the height of the tree.
Method _height_good Return the height of the subtree rooted at Position p.
Method _subtree_postorder Generate a postorder iteration of positions in subtree rooted at p.
Method _subtree_preorder Generate a preorder iteration of positions in subtree rooted at p.
def __init__(self, token, left=None, right=None):
overrides dsap.trees.linked_binary_tree.LinkedBinaryTree.__init__

Create an expression tree.

In a single parameter form, token should be a leaf value (e.g., '42'), and the expression tree will have that value at an isolated node.

In a three-parameter version, token should be an operator, and left and right should be existing ExpressionTree instances that become the operands for the binary operator.

def __str__(self):

Return string representation of the expression.

def evaluate(self):

Return the numeric result of the expression.

def _evaluate_recur(self, p):

Return the numeric result of subtree rooted at p.

def _parenthesize_recur(self, p, result):

Append piecewise representation of p's subtree to resulting list.