30 - Case Study 9 - Maths Tester

By the end of this chapter, the reader will be able to:

• take some pills for their headache.

In this chapter we're going to make use of our Mad Recursion Skillz to write an application suitable for testing basic mathematics. The application will generate a series of random sums of the form:

1 + 2 * 3 + ( 4 / 5 ) + 6

And then prompt the user for an answer. The application will then compare the user's answer against the correct answer and tally up the user's score.

Although this seems like a fairly simple application, internally it is somewhat more complex than it first appears since we need to implement a recursive algorithm for computing the answers to the randomly generated questions - after all, we can hardly mark someone as correct if we don't know what the correct answer is ourselves! We also need to ensure that questions are properly formed according to the rules of mathematics and that we don't end up with questions that contain unmatched brackets.

So, on with the show!

We're going to make use of a simple interface that consists of a display for the user's score, a label that displays the current question, and a JTextField where they can enter the answer. We also need a button for the user to submit their answer to the application.

As usual, our first step is to develop the interface. This gives us a clear idea of the inputs and outputs of the application, which can help develop the underlying logic:

Fig 30.1: Application Storyboard

As with most of the applications we are developing, the interface is fairly simple. We're concerned mainly with what is happening underneath - the actual code that underpins what is going on. So the code for our interface is as follows:

import javax.swing.*; import java.awt.*; import java.awt.event.*; public class MathsTester extends JFrame implements ActionListener { JTextField answer; JButton submit; JPanel userOptions; JLabel question; JLabel score; ... public MathsTester() { answer = new JTextField (10); submit = new JButton ("Submit answer"); submit.addActionListener (this); userOptions = new JPanel(); userOptions.setLayout (new GridLayout (1, 2)); userOptions.add (answer); userOptions.add (submit); score = new JLabel ("Your Score:"); question = new JLabel (""); add (userOptions, BorderLayout.SOUTH); add (score, BorderLayout.NORTH); add (question, BorderLayout.CENTER); } public void actionPerformed (ActionEvent e) { } }

As usual, the actionPerformed method is going to drive most of our application's functionality, but first we need a couple of other classes. One will generate questions, the other will parse questions to return the answer and compare that value against what the user entered. Before we can implement the answer part, we need the actual questions, so we'll start with that.

Before we begin generating questions, we need to put some limits on what we're going to generate, and what symbols we are going to use to indicate operator is to be applied. We'll use the standard set of programming operators, plus the symbol ^ to represent a power.

We don't want to generate questions such as 16543 ^ 12211 - that involves working with ludicrously large numbers that most calculators won't even be able to deal with. Instead, we're going to set up some variables that indicate the range of the numbers we generate.

• Numbers can range between 1 and 5
• Powers can range from 1 to 3
• Questions will have at most 6 terms.

We're going to return the question as a String, so we need to create an empty string as our first task. We'll call it question. We will worry about implementing brackets when we've got the bulk of the method fleshed out.

We start off by creating a random number within the specified constraints, and then add that to our question string:

public String generateQuestion() { int maxNumber = 20; int maxPower = 4; int maxTerms = 6; int operator = 0; char op = null; String question = ""; int number = (int) (Math.random() * maxNumber) + 1question = question + number; return question; }

Then we need to pick a random operator to apply:

operator = (int) (Math.random() * 5); switch (operator) { case 0: op = '^'; break; case 1: op = '/'; break; case 2: op = '*'; break; case 3: op = '+'; break; case 4: op = '-'; break; }

And the add that to our question:

question = question + " " + op;

This gives us our starting base in the form of a question that looks like this:

2 + 3 - 19 + 

Now, we need to keep adding numbers and operators onto the end with a for loop. We will need to add numbers and operators alternately, so will use the % operator on the counter to work out which we should be adding. In fact, since we'll be generating numbers and operators quite a lot, let's move the code into two separate methods rather than duplicate the functionality:

public int getRandomNumber() { int maxNumber = 4; int number = (int) (Math.random() * maxNumber); return number + 1; } public char getRandomOperator() { int operator = (int) (Math.random() * 5); char op = 0; switch (operator) { case 0: op = '^'; break; case 1: op = '/'; break; case 2: op = '*'; break; case 3: op = '+'; break; case 4: op = '-'; break; } return op; }

Taking into account these changes, our generateQuestion method now looks like this:

public String generateQuestion() { int maxTerms = 5; String question = ""; char op; int number = getRandomNumber(); question = question + number; op = getRandomOperator(); question = question + " " + op; for (int i = 0; i < maxTerms; i++) { if (i % 2 == 0) { question = question + " " +getRandomNumber(); } else { question = question + " " +getRandomOperator(); } } return question; }

This serves as the basic framework for what we're trying to accomplish with this class.

We also need to add another method that gives us a random power:

public int getRandomPower() { int maxNumber = 2; int number = (int) (Math.random() * maxNumber); number = number + 1; return number; }

And then we need to keep track of what the last operator we generated was so that we can ensure we don't force people to compute ridiculously large numbers:

for (int i = 0; i < maxTerms; i++) { if (i % 2 == 0) { if (op == '^') { question = question + " " + getRandomPower(); } else { question = question + " " + getRandomNumber(); } } else { op = getRandomOperator(); +BOLDquestion = question + " " + op; } }

Now our questions will be generated at the call of a method.

However, we've missed out a fairly large chunk of functionality - generating brackets. This is somewhat more complicated.

The first thing we need is a way of determining when to create an open bracket - we'll base this on a simple percentage, creating them 25% of the time. We'll write a method that returns a boolean value indicating when we should create a new bracket:

public boolean openBracket() { int number = (int) (Math.random() * 100); return number < 12.0; }

We also need to keep count of how many open brackets we have - obviously we'll never create a close bracket if there are no open brackets - that would just be silly. We're only ever going to put open brackets around numbers, never around operators... effectively a formula surrounded by brackets is standing in place of any given discreet number.

We put the code for generating an open bracket into the part of the for loop responsible for generating numbers:

int openBrackets = 0; boolean addedBracket; ... if (openBracket() == true) { question = question + " " + " ("; openBrackets += 1; addedBracket = true; }

Then we need to create a corresponding closing bracket - we'll do this only if there is an open bracket and if the addedBracket variable is set to false - in this way, we ensure that we won't put brackets around single terms only:

if (openBrackets > 0 && addedBracket == false) { question = question + ") "; openBrackets -= 1; }

We also need to put a check at the end of the loop, making sure that any remaining open brackets are closed off (this can occur with terms that occur at the end of a question):

for (int i = 0; i < openBrackets; i++) { question = question + ") "; }

Putting this all together, we get the following method:

public String generateQuestion() { int maxTerms = 5; String question = ""; char op; char newOp; int openBrackets = 0; int number = getRandomNumber(); boolean addedBracket; question = question + number; op = getRandomOperator(); question = question + " " + op; for (int i = 0; i < maxTerms; i++) { addedBracket = false; if (i % 2 == 0) { if (openBracket() == true) { question = question + " " + " ("; openBrackets += 1; addedBracket = true; } if (op == '^') { question = question + " " + getRandomPower(); } else { question = question + " " +getRandomNumber(); } if (openBrackets > 0 && addedBracket == false) { question = question + ") "; openBrackets -= 1; } } else { Op = getRandomOperator(); question = question + " " + op; } } } for (int i = 0; i < openBrackets; i++) { question = question + ") "; } return question; }

And there we have it, a powerhouse of a method that generates random questions for our math tester. Awesome.

Now comes the difficult bit - writing some code that can be used to actually compute the answers to our questions. This involves some recursion because of the way our questions involve brackets. In this example we are only looking at pairs of brackets rather than brackets within brackets - the framework we set up for this will be good for either, but actually generating questions of that form is left as an exercise for the reader.

We're going to use another class to perform this task - we'll call it RecursiveParser since that sounds nice and impressive.

We should think a bit about how we're going to calculate these answers - we'll be getting a question as a string and we need to ensure operator precedence is enforced, including the parsing of brackets. The first question we must address when developing any program is how we are going to represent the data - we'll use an ArrayList of terms, so that the formula "2 * 3 * 4" becomes represented by an ArrayList of the form:

Fig 30.2: Calculating The Answer 1

Or the formula 2 + (3 - 5 ) * 2:

Fig 30.3: Calculating The Answer 2

We're also going to hold an array of operators, stored in the order of their precedence:

Fig 30.4: Calculating The Answer 3

Then we step over each element of our operators array within a for loop. Within that loop, we will be stepping over every element of our ArrayList. We check each element in turn, looking for one that matches the current operator we're looking for - when we find a match, we call it a pivot point since it will be surrounded by two terms. So, for the multiply operator on the following ArrayList:

Fig 30.5: Calculating The Answer 4

The pivot point is element 1:

Fig 30.6: Calculating The Answer 5

We then perform the appropriate calculation and collapse these three terms down into a single value which occupies the place the calculation previously did in the ArrayList:

Fig 30.7: Calculating The Answer 6

We continue doing this until we end up collapsing everything into a single value in the ArrayList:

Fig 30.8: Collapsing to a Single Value 1

Becomes:

Fig 30.9: Collapsing to a Single Value 2

So when we are left with a single term, we have the answer to the whole question.

If we encounter an open bracket, we'll pass everything between the brackets to our calculation function (recursively) so that it collapses it all down into a single value and returns that as an answer. We do this before we ever start iterating over our operators:

Fig 30.10: Collapsing to a Single Value 3

We look through this ArrayList for an opening bracket, which we find at position 2. We then find the bracket that closes that opening bracket (which is found at position 6), and then pass everything between these indexes as a new ArrayList for calculation:

Fig 30.11: Collapsing to a Single Value 4

Fig 30.12: Collapsing to a Single Value 5

Fig 30.13: Collapsing to a Single Value 6

And then we replace that whole chunk of the ArrayList, brackets and all, with the answer to the bracketed question:

Fig 30.14: Collapsing to a Single Value 7

This would work equally for brackets which contained brackets, since the first thing the calculate method does is look for an open bracket and pass everything between the open bracket and its closing bracket as a parameter to a recursive call to itself:

Fig 30.15: Process of Recursion

The idea is very simple in theory, and recursion allows us to implement it equally simply in code. However, as with the example of permutations of words, it is a piece of code that benefits from multiple readings before it makes complete sense.

First, we need a few utility methods. We need one that will take our String and turn it into an ArrayList suitable for parsing. We'll call this method makeList:

public ArrayList<String> makeList (String temp) { StringTokenizer myToken = new StringTokenizer (temp, " "); ArrayList tmp<String> = new ArrayList<String>(); while (myToken.hasMoreTokens()) { tmp.add (myToken.nextToken()); } return tmp; }

We need a method to get the elements of an ArrayList that lie between two brackets. We'll call this method split:

public ArrayList split (int start, int end, ArrayListformula) { ArrayList<String> newList = new ArrayList<String>(); String temp; for (int i = start; i < end; i++) { newList.add (formula.get (i)); } return newList; }

We need a method that finds the closing bracket for a corresponding open brace:

public int findClosingBracket (ArrayList<String> formula, int start) { int end = 0; String temp; for (int i = formula.size() - 1; i > start; i--) { temp = formula.get (i); if (temp.charAt (0) == ') ') { end = i; } } if (end == 0) { end = formula.size(); } return end; }

And finally, a method that takes two terms and performs the appropriate calculation on them:

public double calculate (String tmp1, String tmp2, char op) { double num1, num2; double answer = 0.0; num1 = Double.parseDouble (tmp1); num2 = Double.parseDouble (tmp2); switch (op) { case '^': answer = Math.pow (num1, num2); break; case '/': answer = num1 / num2; break; case '*': answer = num1 * num2; break; case '+': answer = num1 + num2; break; case '-': answer = num1 - num2; break; } return answer; }

The code for each of these methods is individually quite simple. That's because we have yet to look at the tricky bit that does the actual recursion. We'll call this method calculateAnswer. First of all, the bit that deals with the brackets:

public double calculateAnswer (ArrayList formula) { char[] operators = { '^', '/', '*', '+', '-' }; String tmp1, tmp2; String pivot = ""; double answer; ArrayList<String> newList = new ArrayList<String>(); int end = 0; String temp; for (int j = 0; j < formula.size(); j++) { pivot = (String) formula.get (j); if (pivot.charAt (0) == ' (') { end = findClosingBracket (formula, j); answer = calculateAnswer (split (j+1, end, formula)); newList.add ("" + answer); j = end; } else if (pivot.charAt (0) != ') ') { newList.add (pivot); } }

And then the bit that deals with the operator precedence:

while (formula.size() > 1) { for (int i = 0; i < operators.length; i++) { newList = new ArrayList(); for (int j = 0; j < formula.size(); j++) { pivot = (String) formula.get (j); if (pivot.length() == 1 &&pivot.charAt (0) == operators[i]) { tmp1 = (String) formula.get (newList.size() - 1); tmp2 = (String) formula.get (j+1); answer = calculate (tmp1, tmp2, operators[i]); newList.remove (newList.size() - 1); newList.add ("" + answer); j = j + 1; } else { newList.add (pivot); } } formula = newList; } } if (formula.size() > 0) { return Double.parseDouble ((String) formula.get (0)); } else { return 0.0; } }

There's a lot of code there, so we'll go through it bit by bit:

for (int j = 0; j < formula.size(); j++) { pivot = formula.get (j); if (pivot.charAt (0) == ' (') { end = findClosingBracket (formula, j); answer = calculateAnswer (split (j+1, end, formula)); newList.add ("" + answer); j = end; } else if (pivot.charAt (0) != ') ') { newList.add (pivot); } }

This piece of code is responsible for dealing with brackets. It steps over every element of the ArrayList passed into the method, looking for open brackets:

Fig 30.16: Dealing with Brackets 1

It goes every element, setting the variable pivot to the current element. If the pivot character is an open bracket:

Fig 30.17: Dealing with Brackets 2

It then looks for the closing bracket for that open bracket, and then sets the variable end to the location of that bracket:

Fig 30.18: Dealing with Brackets 3

These two values are then used as the parameters for the split method, which takes the whole formula and returns only the bits between the start and end parameters:

Fig 30.19: Dealing with Brackets 4

This is then used as the basis of a new call to calculateAnswer. Whatever the method returns is then added to an ArrayList, and the for loop continues from the point at which we found the closing bracket:

Fig 30.20: Dealing with Brackets 5

If the pivot character isn't an open bracket and isn't a closing bracket, the code adds it to another ArrayList it maintains (this is called newList). So for the first two elements, we have a newList variable that contains their values:

Fig 30.21: Dealing with Brackets 6

Then, when it hits the open bracket, it passes the contents of the brackets to another invocation of the calculateAnswer method, which returns an answer that gets added to the newList variable:

Fig 30.22: Dealing with Brackets 7

And then the method continues stepping over our formula variable from the next index after the end bracket, which gives us the following contents for newList at the end of the loop:

Fig 30.23: Dealing with Brackets 8

The effect is that we end up computing out all the brackets, leaving us with a single level question to deal with. The next piece of code calculates the answer to this:

while (formula.size() > 1) { for (int i = 0; i < operators.length; i++) { newList = new ArrayList<String>(); for (int j = 0; j < formula.size(); j++) { pivot = formula.get (j); if (pivot.length() == 1 &&pivot.charAt (0) == operators[i]) { tmp1 = (String) formula.get (newList.size() - 1); tmp2 = (String) formula.get (j+1); answer = calculate (tmp1, tmp2, operators[i]); newList.remove (newList.size() - 1); newList.add ("" + answer); j = j + 1; continue; } else { newList.add (pivot); } } formula = newList; }

We step over every element of our operators array within a for loop:

Fig 30.24: Operators

And within this loop, we step over every element in our formula ArrayList looking for elements that match the current operator and are only one character long (so we don't match negative numbers). So for the first loop, we go over every element looking for one that matches ^:

Fig 30.25: The Parsed Calculation

If the element doesn't match, it is added to a newly cleared newList variable... so if nothing matches for a particular operator, newList contains the current state of the formula ArrayList.

At the end of the loop, the formula ArrayList is set to whatever we ended up within newList... so for this particular operator in this particular question, it gets assigned to the contents of newList, which are exactly the same as the original formula. It is only when we get to iteration 3 of the outer loop (the - operator) that we start doing anything interesting.

When an element matches the current operator, we set the tmp1 variable to the last element in newList, and tmp2 to the element that lies directly after the operator.

Fig 30.26: Formula to newList

The operator itself is the pivot point. We pass both the terms and the operator into our calculate method, which returns the answer. We then remove the last element we added to newList and replace it with our answer. So for step one over the formula, newList contains one element:

Fig 30.27: Calculating an Answer

Then at step two, it matches an operator. It removes the last element that was added, and replaces it with the answer to the calculation:

Fig 30.28: Replacing the Element

And we then continues the loop over formula at the point after the second term:

Fig 30.29: Continuing the Loop

The point after the second term is also a matched operator, so it sets tmp1 to be the last element in newList (which is 5), and tmp2 becomes the element after the operator (which is also 5). We then perform the calculation and replace the contents of our newList element with the answer:

Fig 30.30: The Answer

It continues this in a while loop that is based on the number of elements in the formula being greater than 1. As soon as there is only element left, the loop terminates and the method returns a double representing what the value of the calculation was.

Tricky? Just a bit!

Now we need to put the code into our application. When we setup the interface, we're going to set the contents of our question label to be a question generated from our generator. When the user presses a button, it is going to pass the text from the label to our recursive parser and compare the answer from that to the answer the user typed:

public class MathsTester extends JFrame implements ActionListener { int userScore; QuestionGenerator generator; ... public MathsTester() { ... score = new JLabel ("Your Score:"); userScore = 0; ... question = new JLabel (generator.generateQuestion()); ... } public void actionPerformed (ActionEvent e) { String input = answer.getText(); RecursiveParser newParser = new RecursiveParser(); double answer; double user; answer = newParser.getAnswer (question.getText()); try { user = Double.parseDouble (input); } catch (NumberFormatException ex) { JOptionPane.showMessageDialog (null, "Please enter a number."); return; } if (user == answer) { userScore += 1; score.setText ("Your score: " + userScore); JOptionPane.showMessageDialog (null, "Correct!"); } else { JOptionPane.showMessageDialog (null, "Incorrect! The answer was " + answer); } question.setText (generator.generateQuestion()); } }

There's a problem with our application in that the numbers it produces are completely random (within limits), and so the answers to the questions are often very precise. It would be much better for us if we could limit the answers to a certain number of significant decimal places.

In the java.text package is a class called DecimalFormat that allows us to do just that. We create a DecimalFormat object, passing in a string that represents the format we wish to use:

DecimalFormat df = new DecimalFormat ("0.00");

And then pass in the value we wish to truncate as a parameter to the format method of this object:

String str = df.format (myNumber);

And then finally:

double num = Double.parseDouble (str);

Now the answers will only ever be to two significant decimal places. Neato!

Although from the introduction it seemed like a fairly simple application, the complexity of bracket and operator precedence means that it is surprisingly complex to develop this particular program. If we didn't have recursion as a tool available to us, it would be even more difficult - straightforward iteration doesn't lend us the same power when dealing with these kind of problems.

At this point, we've mastered all of the programming tools we have available to us as intermediate Java programmers. There are obviously more, and of greater power and complexity than what we've covered - but as far as this book goes, there are no more coding tools to learn - our toolkit is full of all the goodness we can possibly squeeze into it.

In the next few chapters, we'll be looking at some of the context of Java - why certain tools are better than others for some kinds of problems, and how we can bring together everything we've learned to create a 'finished' application. But you deserve a great big pat on the back for the hard work you've done up until now. Well done!

Further Reading

The following table details further reading on the topic in this chapter, and also any external resources that you may find useful.