CPSC 331: HW3

HW3

This assignment will be marked out of 30 points. You also have an opportunity to earn 5 bonus

points. This is an individual assignment. Please review the rules on academic misconduct on the

course D2L page.

This assignment consists of two parts. The first part consists of problems that will give you

more practice working with binary trees. The second part consists of a coding exercise that explores

the use of trees in parsing and evaluating arithmetic expressions.

Part I

1. (5 points)

Prove the following:

• A binary tree with n nodes has n + 1 null links.

• In a non-empty binary tree, the number of full nodes plus one is equal to the number of

leaves. (A full node is a node that has two children.)

2. (5 points)

Design a linear time algorithm to test whether a binary tree is a binary search tree. Provide

pseudocode for your algorithm and justify that your algorithm is linear in the number of

nodes.

3. (5 points)

Analyze the worst case and best case running times of inserting n elements into an initially

empty binary search tree. For each case, provide details of your analysis starting from counting

relevant operations to an accurate asymptotic characterization.

Part II

Write a parser that parses an arithmetic expression given in infix notation into a binary expression tree. Your parser should support infix expressions consisting of binary operators {‘+’, ‘-’,

‘*’, ‘/’ }, numbers (in integer format), as well as parentheses (which may be nested). Once

an expression has been parsed into an expression tree, your program will additionally be able to

perform preorder and postorder traversals on the tree, and evaluate the expression.

You can perform the parsing either using a stack (worth 15 points) or via recursive descent

(worth 15 points + 5 bonus) using an expression grammar for infix expressions. Both strategies

will be discussed in class and tutorials.

Stack-based Parsing (15 points)

Please review Section 4.2.2 in Weiss which presents a stack-based algorithm for parsing parenthesesfree expressions given in postfix notation. Note that you will first need to apply Dijkstra’s shunting

yard algorithm to convert the given infix expression to postfix.

• You may use the Stack class from the Java Collections Framework.

• Implementation of Dijkstra’s shunting yard algorithm and the subsequent stack-based parsing

algorithm must be your own. You are also required to use the provided ExpressionTree and

ExpressionTreeNode classes (see below).

• Your implementation should check for errors and throw an exception if there are any syntax

problems in the input expression.

1

CPSC 331: Spring 2018 HW3

Recursive Descent (15 + 5 points)

An expression grammar for infix expressions is given below.

E –> T { ( “+” | “-” ) T }

T –> F { ( “*” | “/” ) F }

F –> num | “(” E “)”

This grammar generates expressions consisting of the binary operators +, -, * and / as well as

parenthetical expressions.

Notation: In the above grammar, braces {} are used to indicate productions that may repeat 0 or

more times, | separate alternatives, while parentheses () are used for grouping. The only terminal

symbol is a num. For this assignment, you can assume that num ∈ Z.

Note that * and / have higher precedence compared to + and -. Operators with the same

precedence are associated left-to-right (left-associativity), e.g. the expression “2 – 3 + 4” yields

the following tree.

+

– 4

2 3

Before proceeding with your implementation, please make sure you understand the rules of the

grammar and know how to apply them for parsing via recursive descent.

Implementation

Write a Java class called ExpressionTree that parses expressions either using a stack or by

recursive descent. In either case, your class should have the following public methods.

public class ExpressionTree {

private ExpTreeNode root = null ;

// Builds empty tree

public ExpressionTree () {

}

// Parse an expression from a string

public void parse ( String line ) throws ParseException {

}

// Evaluate an expression

public int evaluate () {

return 0;

}

// Return a postfix version of the expression

public String postfix () {

return “”;

}

2

CPSC 331: Spring 2018 HW3

// Return a prefix version of the expression

public String prefix () {

return “”;

}

}

A skeleton of this class as well as the class ExpTreeNode are available on D2L.

Additional Requirements

Include as many private methods as necessary to parse a given expression. You can assume that

properly formatted input expressions will have tokens separated by whitespace. However, you

should check for expressions that have syntax issues. If an input expression contains a syntax error,

the parse method should throw a ParseException. In the thrown exception, include a description

of the nature of the error as well as the location of the error in the input string.

When converting expressions to prefix or postfix, please separate tokens using whitespace. Prefix

and postfix expressions should be parentheses free.

Documentation and Testing

For all private methods that you add, please provide Javadoc comments to explain what the methods

are doing.

Write a program to test your parser. Test with both small size expressions as well as expressions with mixed operators, nested parentheses etc. A test program that is compatible with your

implementation will be made available closer to the due date.

Submission

Part I

Please prepare a PDF file called part1.pdf (scanned or typeset) that is packaged with the rest

of the files for Part II. If you are scanning your solution, please submit the scanned pages as a single

PDF file.

Part II

Please package your Java class files in a compressed archive called hw3.zip. Please remove any

driver programs (main methods) that you used to test your implementations. Please make sure

that your name appears at the beginning of each file. If you need to cite any other sources that you

used, please include them either at the beginning of the file ExpressionTree.java or in a separate

file called README.

Please do not place the files in different folders. Your archive should only contain the following

Java files: ExpTreeNode.java, ExpressionTree.java. In addition, your archive should also contain

the file please part1.pdf and optionally a README file if applicable.

3