This section is intended to practice trivial recursions, as a warm-up towards the second section. Since recursions require a unique way of thinking, this should let you slide in smoothly into the right mindset.

·         Write a class called Recursions in Recursions.java. Write your answers to this section in that file as public static methods. Use a main method to test your recursions, but do not submit it.

Recursion 1: reversing a number

Requirements

·         Write a method called reverse which accepts an integer and returns an integer.

·         The method reverses a non-negative number.

·         For example, the result of reversing 915 is 519. Reversing 12,300 results in 321.

Guidance & notes:

·         It can easily be done by converting the number to a string, and then running the string reverse recursion. However, you must not do so, but rather use an arithmetic recursion.

·         You can use a private helper method here (you probably have to), but the algorithm must be based on direct or indirect recursive calls.

·         You should also not declare class variables.

·         You may find out that you need an internal loop to help you with your computations. As long as it’s not the essence of the recursive solution, it’s fine.

Bonus 5 points:

·         If you managed to solve it without any loop at all, yet recursively, you win a 5 point bonus.

Recursion 2: recursive data structure

Requirements

1.       Consider a singly linked list.

2.       You are given a class Element, with a getNext method, and a getData method which returns a String, representing the data.

3.       Write a method find, which accepts a string and a reference to the first element (head) of a linked list (in that order: data then head), and returns a reference to the element that has this data (case sensitive).

4.       If no such element found, or the input was invalid, just return null.

5.       The algorithm must be based on recursive calls.

Guidance & notes

·         In order to test this recursion, you may have to write the Element class just for testing. You should already know by now how to do it by yourself. Please do not submit it.

Remember the calculator we built in exercise 9?

In this exercise we are going to write a parser that accepts an arithmetic expression from the user, then parses it and evaluates it. To keep it easy, our parser will only support binary operators.

The parsing process

The parsing process is based on 2 stages:

1.       Building a binary parse tree (see below).

2.       Converting the binary parse tree to an ExpressionElement structure, the same structure we used in exercise 9 (recall the class diagram).

The expression structure, as a binary tree

An expression structure, represented by an ExpressionElement, can be depicted as a tree.

Consider the following expression:

To evaluate this expression using our calculator in exercise 9, we would write this code:

Literal lm2 = new Literal(-2);

Literal l2 = new Literal(2);

Literal l3 = new Literal(3);

Literal l5 = new Literal(5);

Literal l10 = new Literal(10);

OperatorAdd a2and10 = new OperatorAdd(l2, l10);

OperatorDivide d2and10by3 = new OperatorDivide(a2and10, l3);

OperatorAdd a5andm2 = new OperatorAdd(l5, lm2);

OperatorAdd root = new OperatorAdd(d2and10by3, a5andm2);

System.out.println(root + " = " + root.evaluate());

If we look at an operator as a circle (“node”) with its two operands as lower circles (“child nodes”), we can depict the structure we made out of the expression as in the following diagram:

This diagram is called a “tree”, where each circle is called a “node”, some nodes have “children” (nodes they are pointing at), and those have “parents”.

Moreover:

-          The blue node is called the “root”, because it has no parent.

-          An orange node is called a “leaf”, because it has no children.

-          The green nodes are inner nodes.

-          Since each inner node has exactly 2 child nodes, the tree is called a “binary tree”.

Evaluating the result of an expression tree

So how would you go about evaluating the expression given in this binary tree?

The natural way would be starting at the bottom, going from left to right:

·         2 + 10 = 12, so let’s replace the leftmost + node and its children with a single leaf, the value 12.

·         The division operator now divides 12 by 3. We take the result, and we replace the division node and both its children with a single leaf, the value 4.

·         Next, we go an evaluate the right subtree, where 5+(-2)=3.

·         And last, we calculate 4 + 3.

·         We can say that in general, evaluating an expression tree begins from left to right, from bottom to top, where each operator is replaced by the result of evaluating that operator on both its operand. This goes on until the root node is replaced with a literal value, and that is the expression result.

Try this on paper. This is, in fact, how the code you wrote works. Try and write the code snippet given above, and walk it through using a debugger or debug prints.

Although we first invoke evaluate on the root, the root first invokes the evaluate method on each of its operands, which in turn do the same on their operands. This process continues until it reaches an object of type Literal (a leaf). Leaves return just a number, and the results are returned from bottom to top, from left to right.

The binary parse tree (not to confuse with an expression tree)

When a user enters an expression string, for example “(2+10)/3+5+(-2)”, we have to decide how to parse it. “Parsing” means analyzing a string and making a meaningful structure out of it. To make things simple, we will build a tree that reflects our expression binary tree one to one. In our tree, each node (which is not a leaf) will represent an operator. It will have exactly two children, which represent the operands. Each leaf represents a literal.

The data field in each node in the tree will be a String.

This way, converting from the binary parse tree to an expression tree will be fairly easy.

If you’re lost, here is an example:

Consider the following input string: “(2+10)/3+5+(-2)”. The binary parse tree will look exactly like the expression tree in the diagram above.  Only instead of an ExpressionElement, each node in the parse tree will be of type ParseNode, with these fields: data (String), left (ParseNode) and right (ParseNode). Very much like a binary operator with a string representation, a left operand and a right operand.

1.       This section’s API is given here.

2.       Write a class called InvalidExpressionFormatException in package calc, which extends Exception. Implement a constructor which accepts one string parameter called message, and pass it on to the super constructor. Use this exception according to the guidance in the API.

3.       Write a class called ParseNode in package calc. The class visibility should be package private (i.e., default). The class should have 3 instance variables as described above (data, left and right). Implement the following public methods (as in the API documentation):

a.       A constructor which accepts the string data.

b.      A getter for the data.

c.       Setters and getters for the left and right children.

4.       Write a class called ParseTree in package calc. This is a utility class (no instance variables), which implements 2 public static methods, both are recursive methods (and according to the API):

·         ExpressionElement toExpressionElement(ParseNode root) throws InvalidExpressionFormatException

o   This method receives a reference to the root of a binary parse tree.

o   It then builds an expression structure, as described above and in exercise 9, made of references to ExpressionElements.

o   It returns the root, which is the first operator to evaluate.

o   Implement this method as a recursion.

·         ParseNode buildTree(String expression) throws InvalidExpressionFormatException

o   This method parses the string expression (as received by the user) and builds a binary parse tree out of it.

o   It then returns a reference to the root node, which reflects the first operator to evaluate.

o   Implement this method as a recursion.

o   Note: check the API for what is an acceptable expression format!

·         There is no need to verify the parameters in the exception class and in ParseNode.

·         ParseNode is the simplest class with the simplest implementation. Don’t overthink it.

·         Note that in the provided solution for exercise 9, the string representation of each of the relevant operators is a public constant, so you can use it in your utility class.

·         As you may already have figured, after the user has entered their expression, we build a binary parse tree out of it by invoking buildTree, and pass the returned reference to the method toExpressionElement. The result of the latter can be evaluated just as we did in exercise 9.

·         Download the solution to exercise 9 from here. You will have to use it in exercise 10, but remember not to modify it and not submit any part of it.

Writing and testing toExpressionElement

Decide on a simple yet representing expression, say “(2+10)/3+5+(-2)”.

Begin by writing a main method (not for submission).

In your main method, build a binary parse tree that reflects that expression, manually:

ParseNode pnMinus2 = new ParseNode("-2");

ParseNode pn2 = new ParseNode("2");

ParseNode pn3 = new ParseNode("3");

ParseNode pn5 = new ParseNode("5");

ParseNode pn10 = new ParseNode("10");

ParseNode pnAdd1 = new ParseNode("+");

ParseNode pndivide = new ParseNode("/");

ParseNode pnAdd2 = new ParseNode("+");

ParseNode pnAdd3 = new ParseNode("+");

           

pnAdd1.setLeft(pn2);

pnAdd1.setRight(pn10);

pndivide.setLeft(pnAdd1);

pndivide.setRight(pn3);

pnAdd2.setLeft(pn5);

pnAdd2.setRight(pnMinus2);

pnAdd3.setLeft(pndivide);

pnAdd3.setRight(pnAdd2);

The reference variable pnAdd3 is the tree root, and we can reach the entire tree from there. Later, our buildTree method will build this tree automatically for us.

Call toExpressionElement(pnAdd3) and print the result, like this:

try {

      ExpressionElement result = ParseTree.toExpressionElement(pnAdd3);

      System.out.println(result + " = " + result.evaluate());

} catch (InvalidExpressionFormatException e) {

      System.out.println(e.getMessage());

}

Run it, and your output should look exactly like this:

((2+10)/3)+(5+-2) = 7.0

If it didn’t work well for you, use a debugger to find your bugs.

Writing and testing buildTree

The trick in writing this recursion, is taking advantage of the string format. According to the API, each operand is enclosed in parentheses. That means that an expression can only be one of 2 forms:

-          “literal”, if the expression is made only of a single literal. For example “-2”.

-          (left operand)operator(right operand)”, where each operand can, again, be of any of these 2 forms (this is the recursive part).

-          We will instantiate a node for the operator, and set its left and right children by recursively calling buildTree on each of the operands.

So first, validate the expression just for basic stuff, such as null and zero length.

Then, find out if it’s a single literal (hint: if it can be parsed by the Double.parseDouble method).

If it’s not a single literal, it must be of the second form. Here’s what you can do to parse the second form:

-          Split the string to 3 substrings: the left operand, the operator and the right operand.

-          You can do that by counting parentheses (increase a counter on each opening parenthesis, decrease it on a closing parenthesis). When the counter reached zero, you’re past the left operand.

-          Instantiate a node out of the operator. Now you have to set both its children.

-          You can set the children by recursively calling buildTree on each part of the string; the left and right operands.

Validating expression format

The exception you’ve written needs to be thrown if the provided expression is not well-formatted. A well-formatted expression is in one of the 2 forms:

-          Form 1: literal

-          Form 2: (left operand)operator(right operand)

Where each operand can also be either of the 2 forms. Example of a well formatted expression: (((2)+(10))/(3))+((5)+(-2)).

You don’t have to start by validating the expression. However, while parsing the expression, if you expect something, like parenthesis, and it’s not there, throw the exception.

For example, consider the sample expression given above, if we add an opening parenthesis to the beginning, it will be ill-formatted: ((((2)+(10))/(3))+((5)+(-2))

When you try to get to the operator, a good algorithm would be counting parentheses. Start with the first open parenthesis, and initialize a counter with 1. Iterate through the string, and whenever you encounter a close parenthesis, decrease the counter by one. Whenever you encounter an opening parenthesis, increate the counter by 1. So if you’re running this algorithm on the ill-formatted string above, your loop will reach the end of the string before the counter reached 0. If your loop reached the end of the string, throw the exception.

So the general guideline, is that if your code has more points where it’s expecting something (no opening parenthesis, but the string is not a number, for example), throw the exception there.

1.       Download the file Calculator.java from here. Note that it’s not part of package calc, so you must place it in the folder above the calc folder.

2.       Make sure the file compiles. If it doesn’t compile, check for imports, visibility modifiers and API conformity.

3.       Once it’s compiled, use it to run the calculator application.

4.       Make sure to enter well formatted expression input!

Below is a sample result of running Calculator.

You’re not expected to exactly match between the exception text and the real problem, since this is a very advanced issue, so your text may vary:

Enter an expression to calculate ["bye" to quit]: Hi!

Invalid format exception thrown.

Expected: literal

Enter an expression to calculate ["bye" to quit]: -0.14

-0.14 = -0.14

Enter an expression to calculate ["bye" to quit]: 0.0000

0.0000 = 0.0

Enter an expression to calculate ["bye" to quit]: 15

15 = 15.0

Enter an expression to calculate ["bye" to quit]: (3*4)

Invalid format exception thrown.

Expected: open parenthesis

Enter an expression to calculate ["bye" to quit]: (3)*4

Invalid format exception thrown.

Expected: open parenthesis

Enter an expression to calculate ["bye" to quit]: (3)*(4

Invalid format exception thrown.

Element is empty or null

Enter an expression to calculate ["bye" to quit]: ((3)*(4))

Invalid format exception thrown.

Expected: open parenthesis

Enter an expression to calculate ["bye" to quit]: (3)*(4)

(3)*(4) = 12.0

Enter an expression to calculate ["bye" to quit]: ((3)*(4))/(1.5)

((3)*(4))/(1.5) = 8.0

Enter an expression to calculate ["bye" to quit]: (((3)*(4))/(1.5))-(22)

(((3)*(4))/(1.5))-(22) = -14.0

Enter an expression to calculate ["bye" to quit]: ((((3)*(4))/(1.5))-(22))+(14.5)

((((3)*(4))/(1.5))-(22))+(14.5) = 0.5

Enter an expression to calculate ["bye" to quit]: (((((3)*(4))/(1.5))-(22))+(14.5))-(0.5)

(((((3)*(4))/(1.5))-(22))+(14.5))-(0.5) = 0.0

Enter an expression to calculate ["bye" to quit]: bye

Goodbye!

 

Submit all the files given below, both in hard and soft copies:

·         Ex10.zip (archive file):

o   Recursions.java

o   calc (folder):

§  InvalidExpressionFormatException.java

§  ParseNode.java

§  ParseTree.java

 

Good luck!

 

 

© 2010 Boaz Kantor