Java Homework Help

Data Structures and Algorithms 6th Edition

Write a Java project that:

Implements the Linked Binary Tree ADT present in the textbook.

You must include (implement) all of the interfaces and classes for the abstract tree, abstract binary tree, tree, and linked binary tree.

A large part off this assignment will be gathering together the various code fragments and placing them in the right classes.

Be sure to review code fragments 8.1 to 8.28 to make sure that you have included all of the necessary code.

Some of the necessary code may not appear in a formal code fragment but is implied in the text.

Your project may not compile error free until all of the necessary code fragments have be implemented.

Implements the Shunting Yard algorithm to convert an in-fix expression into its corresponding post-fix notation.

Uses the queue and stack approach to evaluate an expression that is in post-fix notation.

Uses the queue and stack approach to build the binary expression tree for an expression that is in post-fix notation.

You must use your implementations of stacks and queues from previous assignments.

Your program must:

Ask the user to enter the absolute path and filename (as a single String) of the file that contains a list of arithmetic expressions. Each expression will be on a single line in the input text file delimited by an end of line character.

Read arithmetic expressions from an input file until the EOF is reached.

See file format and example at end of assignment.

For each expression your program should:

Print out the expression that was read from the file.

Determine if the expression is valid.

Print an invalid expression message for invalid expressions.

For each valid expression

Evaluate the expression and display the results of the evaluation

Print the expression in post-fix notation

Represent the expression as a binary expression tree, binary expression tree does not need to be printed.

Print the expression tree using the pre-order traversal

Print the expression tree using the in-order traversal

Print the expression tree using the post-order traversal

Print the expression using Eulers tour so that it produces a traditional parenthesized expression.

Input file format:

Each token in the input file will be blank separated so the expressions should be easy to parse.

Tokens will be one of the following:

Numeric values (possibly includes negative numbers):

The uniary negative operator will not have a blank space between the operator and its corresponding operand, e.g. -45

The binary subtraction operator will have blank space between the operator and its corresponding operands, e.g. 11 - 5

Operators will be limited to:

Addition +

Subtraction -

Multiplication *

Division /

Parenthesis

In order to make expression more readable parenthesis, curly brackets and square brackets may be used.

For grouping and nesting purposes the symbols must match correctly.

For example:

( 3 - [ { 4 / 3 } + 7 ] - 2 ) is correct grouping

( { [ } ] ) is incorrect nesting

There will be no implied multiplication

The expression 3 * ( 4 - -5 ) is valid

The expression 3 ( 4 - -5 ) is not valid

You do not need to check for invalid tokens.