# CPSC 331 HW3 solution

\$24.99

Original Work
Category:

## Description

5/5 - (1 vote)

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 ﬁrst 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 inﬁx notation into a binary expression tree. Your parser should support inﬁx 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 inﬁx 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 postﬁx notation. Note that you will ﬁrst need to apply Dijkstra’s shunting yard algorithm to convert the given inﬁx expression to postﬁx. • 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 inﬁx 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
32 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 “”; }
}