An arithmetic expression can be represented as a binary tree where every leaf contains a

number and every internal node an arithmetic operator. We call these trees syntax trees.

Here we consider arithmetic expressions comprised of positive integers and the operators

$+\text{'}($addition$)$ and $-*($subtraction$).$

For example, the arithmetic expression $(10+(40-30))+20)$ is represented as the following

syntax tree of height $3.$

Note that parentheses are not necessary when arithmetic expressions are in syntax tree

form.

Addition is symmetric and associative $$thatis$,$a$+$b$=$b$+$a$,$and $($a$+$b$)+$c$=$a$+($b$+$c$).$

$($Subtraction is neither symmetric nor associative.$)$ Therefore, the above arithmetic

expression is equivalent to the expression $(\{40-30)+(10+20))$ which is represented as the

following syntax tree of height $2.$

We want to take advantage of symmetry and associativity of addition to transform syntax

trees to equivalent ones of minimum height. This transformation should not evaluate the

expressions and therefore the output trees should have the same number of internal nodes

$($operators$)$ and leaves $($numbers$)$ as the input trees.

XSCH$3150$

$($a$)$ Describe a set of tree transformations that, when applied to a syntax tree, reduce its

height. This set should be complete: we can apply them repeatedly to a syntax tree to

derive an equivalent tree of minimum height. Explain the transformations and why they are

complete.

$(15$ marks$)$

b$\}$ Implement the following method in Java that inputs a syntax tree and outputs an

equivalent one with minimum height. The method should run in time O$($N$),$ where N is the

number of nodes in the input syntax tree.

$(18$ marks$)$

AExpr compact $($AExpr inTree$)$

BExpr is the class shown below. The static factory methods makePlusNode,

makeMinusNode, and makeNumberNode create new tree nodes.

class AExpr $\{$

private int height;

private boolean isOperator; $//$true: internal node;

false: leaf

$//$ when internal node

private char operator; $//$ can be $\text{'}+\text{'}$ or $\text{'}$~$\text{'}$

private AZxpr leftOperand;

private AExpr rightOperand;

$//$ when leaf

int numbex;

private AExpr$($boolean isOp, char op$,$ AExpr left, AExpr

right,

int num, int h$)\{$

isOperator $=$ isOp; operator $=$ op; leftOperand $=$ left;

rightOperand $=$ right; number $=$ num; height $=$ hi

$\}$

$//$ factory methods to create Syntax Tree nodes

static AExpr makePlusNode $($AExpr left, AExpr right$)($

return new AExpr$($true$,\text{'}+\text{'},$ left, right, O$,$

$1+$ Math.max $($left$.$getHeight$(),$ right.getHeight$()))$;

$\}$

static AExpr makeMinusNode $($AExpr left, AExpr right$)\{$

return new AExpr$($true$,\text{'}$~$\text{'},$ left, right, O$,$

$1+$ Math.max$($left$.$getHeight$(),$ right.getHeight$()))$;

$\}$

static AExpr makeNumberNode $($int num$)\{$

XSCH$3$

return new AExpr$($false$,\text{'}+\text{'},$ null, null, num, $0)$;

$1$

$//$interface with node

boolean isOperatox$()\{$ return isOperator; $\}$

boolean isPlus$()\{$ return isOperator && $($operator $==\text{'}+\text{'})$; $\}$

boolean isMinus$()($ return isOperator && $($operator $==\text{'}=\text{'})$; $\}$

boolean isNumber$()\{$ return :isOperator; $\}$

RExpr getLeft$()($ return leftoperand; $)$

AExpr getRight$()\{$ return rightOperand; $\}$

int getNumber$()\{$ return number; $\}$

int getHeight$\{)\{$ return height; $\}$

void setLeft $($AExpr left$)\{$ leftOperand $=$ left; $\}$

void setRight $($AExpr right$)($ rightOperand $=$ right; $\}$

void setNumber$($int num$)\{$ number $=$ num; $\}$

void setHeight $($int h$)\{$ height $=$ h; $\}$

$\}$