Description

This assignment involves manipulating binary trees which represent arithmetic expressions. The binary trees are implemented by the LinkedBinaryTree class provided by the textbook, which we have put in a textbook package in the source code. We have made one small modification to the code, to remove the implementations of some standard tree traversals. If you choose to use tree traversals as part of your solution, you will need to implement them yourself in Assignment.java instead.The only file which you should edit is Assignment.java

  • Each of these methods is described by a more detailed comment in the code, and has some examples of input/output later in this document. You can (and should) add private static helper methods as needed.
  • Note that all the methods in this class should be static methods (meaning that you do not need to instantiate the class to use them.) For all the methods exceptisArithmeticExpression, an IllegalArgumentException should be thrown if an invalid argument is used (i.e. if the tree is null or not an arithmetic expression, or if we try to set a value to null.)
  • The first two methods, prefix2tree and equals have been implemented for you:
  • prefix2tree takes an arithmetic expression in prefix notation (also known as Polish notation) and builds a linked binary tree, using the textbook’s implementation LinkedBinaryTree, which is included in the code base in the package textbook. This should be very helpful for your testing, as it makes it very easy to build valid trees, as well as giving you an example of using one of the most useful LinkedBinaryTree methods, attach.
  • equalstake two trees and decides if they are the same (i.e. they have the same structure and every node has the same value.) You may find this useful during testing.
  • In a separate text file, for each public method, you should describe the algorithm you intend to use for this, and state the big-Oh worst-case runtime, in terms of the length of the arithmetic expression, the height of the tree, or other important aspects of the input data. You should also give a short justification of this cost, for example, by indicating how much of the tree is examined, and how much work is done on each node.
  • Description and justification of the tests you have written

We strongly encourage you to implement most of the methods recursively

Notation

Values and variables

Any strings which are integers are values. Anything that is not an integer or an operator (see below) is to be considered a variable (although in the automarking we will only use single letters for variable labels, i.e. “x”, “c”, etc.)

Operators

Our operators are all binary operators (they take exactly two operands.) We will support +, − and ∗ only (i.e. you do not need to implement division). Operands are always either numbers, or are variables. Any string which is not an integer or decimal number is to be considered a variable.

Infix notation (parenthesised) Infix is the notation you are probably most familiar with. Infix notation puts binary operators (such as +, − and ∗) in between their operands, and uses parenthesis to show the order in which the operators should be applied. For this assignment we will strictly include the parenthesis even when we would normally omit them (for example, it’s obvious that 1 ∗ 3 + 4 − 2 = 5, but your tree2infix method should write this as ((1 ∗ 3) + (4 − 2))).

Prefix notation (without parenthesis)

Prefix notation is where the arithmetic operators are written before their operands. For example adding one and two in prefix notation is + 1 2. Because we know in advance how many operands each operator uses, we will never use parenthesis to show precedence (note: we are only using - as a binary operator. If we want to take the negative of a variable x, we’d have to write − 0 x to subtract it from zero.

Examples

Substitute

There are two versions of this method. One takes a single variable label and value, the other takes a map of labels to values.