Reverse Polish notation is easy with test-driven development
In writing any computer program, except perhaps the very simplest, you are guaranteed to make mistakes. Test-driven development, in which tests are written before the actual program, turns the mistakes you’re sure to make into an advantage that makes programming very easy.
With the right tests, a particular programming task could become so easy that the program practically writes itself.
This is not one of those “you too can learn to code” articles, though you can find plenty of those here on Medium. I assume you already know Java or C# or something like that, and some kind of unit testing.
I don’t assume you already know what reverse Polish notation is, so I’ll give a quick explanation of it, even though I doubt you have never ever heard of it before if you’re serious about “coding.”
In any case, reverse Polish notation here is just one example out of many I could have picked to illustrate how test-driven development simplifies almost any programming task (though there are exceptions that prove the rule).
Background: the need for reverse Polish notation
Our normal notation for arithmetic expressions, which we take for granted, is sometimes called “infix notation.” For example, 8 × 21 + 1. Easy, no problem.
An expression like 7 − 1.4142 × 7 + 1.4142 is also easy, and a computer will give you an answer right away. But ambiguity creeps in… did I mean (7 − 1.4142) × (7 + 1.4142) instead? That’s a more interesting number, it’s almost exactly 47.
Here’s a more practical example: your car has 100,000 miles on it. Call that startMileage. Go on a trip from Detroit to Chicago. Your car now has 100,282 miles on it, call that endMileage.
Do you have a variable gallonsUsed with the appropriate information in it? Now compute your car’s miles per gallon (MPG) with this formula:
mpg = endMileage - startMileage / gallonsUsed;Oops, something went wrong there. It’s fixed easily enough by adding parentheses.
This example comes from the book Practical Debugging in C++ by Ann R. Ford and Toby J. Teory, but it’s of course also applicable in Java, C, C#, JavaScript, etc., without any change, and many others with only minor syntactical changes.
Nowadays we take the parentheses keys for granted. Even basic scientific calculators, like the ones you can get at CVS for less than $20, have parentheses keys.
Those calculators can keep track of a lot more than the much bigger and bulkier but less powerful calculators that were available in the first half of the 20th Century.
Implementing parentheses keys for those old calculators would have been difficult, but people still needed to do calculations with formulas involving parentheses. If only there was a way to get rid of parentheses…
The Polish mathematician Jan Łukasiewicz came up with a solution: put the operators before the operands. So instead of 8 × 21 + 1, we have + 1 × 21 8. Big deal.
And instead of (7 − 1.4142) × (7 + 1.4142), we have × + 1.4142 7 − 1.4142 7. No need for parentheses here, though we do need to make sure the spaces are clearly visible. Nevertheless, here we start to see some benefit to Łukasiewicz’s idea.
Any Polish speakers reading this please correct me if I’m wrong: Łukasiewicz’s name is pronounced something like “loo-kah-see-eh-vish” or “woo-kah-see-eh-vish.” To sidestep this problem of pronunciation, we can just call Łukasiewicz’s notation “Polish notation.”
Implementing Polish notation on the less agile calculators of yesteryear still presented difficulties. Charles Hamblin came up with the idea of taking Polish notation and just reversing it. Thus reverse Polish notation was born.
To use our previous examples once again, 8 × 21 + 1 becomes 8 21 × 1 + and (7 − 1.4142) × (7 + 1.4142) becomes 7 1.4142 − 7 1.4142 + ×.
The greatest advantage of reverse Polish notation is that it can be implemented with a simple stack.
If the calculator gets a number, it pushes it onto the stack. If it gets an operator, it pops two numbers off the stack, performs the indicated arithmetic operation, and pushes the result onto the stack.
And you probably don’t need too deep a stack for most practical calculations, though it does take some getting used to for the human operator.
With the invention of computer programming languages like Pascal and C that understood and expected infix notation, there was still a use for reverse Polish notation: as a programming exercise.
I think it was in the classic Problem Solving and Structured Programming in Pascal by Elliott B. Koffman that I first read about reverse Polish notation. That was many years ago.
Much more recently, Samah Majadla, who is teaching the second Integrate Detroit cohort, assigned reverse Polish notation as the first of four optional programming exercises for the second cohort.
Samah’s modern twist on this old chestnut is that the students are expected and required to use the test-driven development principles she’s teaching them to complete the exercise.
As a graduate of the first cohort, I’m not expected to do any of those exercises, but I figure the practice wouldn’t hurt. I am free to do them as I please, but I will try to adhere to the principles of test-driven development as much as I can.
Writing the tests for a reverse Polish calculator in Java
The reverse Polish notation exercise never seemed all that difficult to me, though it did seem potentially like one of the more time-consuming exercises. With test-driven development, however, it turned out to be much quicker and easier than I expected.
This implementation can easily have a graphical user interface (GUI), but for the purpose here let’s just focus on the engine that receives an arithmetic expression in reverse Polish notation as a String and gives the result as a double.
Also it might be nice if the implementation can keep a “ticker tape” of past calculations, at least within the current session.
Samah did not mention this in her description of the exercise, but to streamline testing, this new requirement suggests that calculate(expression) should not be a static function like she specified.
We should write the tests before the actual implementation, but I really do like to write the stubs first, even if our class is implicitly a direct descendant of Object that does not implement any interfaces.
Here’s what I got so far, minus the boilerplate automatically generated by NetBeans:
public class ReversePolishCalculator { public String history() {
return "This feature has not been implemented yet.";
} public double calculate(String expression) {
return 0.0;
}}
That should be good enough for some failing first tests. And also for NetBeans to auto-generate a template for ReversePolishCalculatorTest with the appropriate JUnit, TestNG or Selenium imports taken care of for us (I’ll stick with JUnit 4.12 for the time being).
I set TEST_DELTA to 0.00001; it could be smaller but here I’m not the least bit interested in testing the machine precision of the Java Virtual Machine. In any case, the test expressions should be such that incorrect results differ from correct results by noticeably greater margins.
In setUp() (annotated Before), revPolCalc, a private instance, is initialized so that testHistory() can reasonably expect the ticker tape to be blank at the beginning of the test.
@Test
public void testHistory() {
System.out.println("history");
String expResult = "";
String result = revPolCalc.history();
assertEquals(expResult, result);
String expression = "1 1 +";
revPolCalc.calculate(expression);
expResult = expression + "\n= 2\n";
result = revPolCalc.history();
assertEquals(expResult, result);
expression = "1 2 3 * - 4 /";
revPolCalc.calculate(expression);
expResult = expResult + "\n" + expression + "\n= -1.25\n";
result = revPolCalc.history();
assertEquals(expResult, result);
}I did think of breaking this test up into smaller tests, but here I’m also interested in seeing that past expressions and their results are saved to the ticker tape, at least until the next time JUnit runs setUp().
By contrast, I wouldn’t lose anything by breaking up my first draft of testCalculate() into two separate tests:
@Test
public void testCalculate() {
System.out.println("calculate");
String expression = "1 1 +";
double expResult = 2.0;
double result = revPolCalc.calculate(expression);
assertEquals(expResult, result, TEST_DELTA);
expression = "1 3 /";
expResult = 0.33333;
result = revPolCalc.calculate(expression);
assertEquals(expResult, result, TEST_DELTA);
}I should also have a test for the example expression Samah gave in the exercise description, 3 2 + 8 4 × −, that is, 3 + 2 − 8 × 4 (in which, with normal parsing, the multiplication of 8 by 4 would happen before the addition and subtraction).
@Test
public void testCalculateOnGivenExpression() {
String expression = "3 2 + 8 4 * -";
System.out.println("calculate \"" + expression + "\"");
double expResult = -27.0;
double result = revPolCalc.calculate(expression);
assertEquals(expResult, result, TEST_DELTA);
}How should we handle division by zero? I think there should be some kind of exception. For that, we could just take the previous test and make a few little changes, like adding the expected exception annotation.
However, I wrote a more verbose test with a try-catch-fail that reports the value of result if no exception is thrown. This will later have the pleasant surprise of reminding me of a special “number” I had forgotten about.
If we do make a GUI for this, can we rely on the object passing expressions to only use the appropriate digits and operator symbols? Maybe, maybe not.
I think it makes sense for something like calculate("These are not numbers at all!") to trigger a NumberFormatException, though the superclass IllegalArgumentException might also be appropriate.
And while an end user might appreciate being able to pass into the program something like “one one plus” and get a result, he or she will not care whether under the hood that’s taken care of by ReversePolishCalculator or some other class in the package or project.
In any case, by the single responsibility principle, recognizing words as numbers should probably not be in the ReversePolishCalculator class, and maybe it shouldn’t even be in the same package.
However, I’d like this implementation to understand the proper minus sign, the multiplication cross and the division obelus as proper operators, even though this might be considered syntactic sugar.
Here’s the test for the division obelus:
/**
* Test of calculate method, of class ReversePolishCalculator.
* The obelus ("÷", Unicode 0x00F7) should work the same
* as the forward slash ("/", ASCII 0x2F).
*/
@Test
public void testCalculateWithObelus() {
String expression = "1 7 \u00F7";
String exprWSlash = expression.replace("\u00F7", "/");
System.out.println("calculate \"" + expression + "\" should work the same as " + exprWSlash);
double expResult = 0.142857;
double result = revPolCalc.calculate(expression);
assertEquals(expResult, result, TEST_DELTA);
double resultWSlash = revPolCalc.calculate(exprWSlash);
assertEquals(result, resultWSlash, TEST_DELTA);
}Note that this makes sure that both 1 7 ÷ and 1 7 / give results reasonably close to 0.142857 (remember that TEST_DELTA gives us some leeway; we don’t want a test to fail just because the conversion of a truncated non-terminating binary does not quite become the truncated non-terminating decimal we expected).
The tests for the proper minus sign and the multiplication cross are very similar, so I won’t quote them here.
And what about expressions with too many numbers or too many operators? Like 1 7 ÷ 2 5 8 943 56 or × + 1 + + + +? Maybe they should cause an exception, though I’m not sure what would be appropriate.
But I think these tests are sufficient for us to make some serious progress on a workable implementation of ReversePolishCalculator.
Since we have technically correct stubs, we can run the tests and see them all fail. Most should fail because they’re expecting numbers other than 0.
The ticker tape test will fail because right now history() gives a message saying the feature is not implemented rather than any kind of actual calculation history.
Maybe I’ve written too many tests at once. Maybe I should have just written one and gotten it to pass before moving on to the next one.
On the other hand, these tests are so closely related that doing them one by one might mean some tests pass on the first run. You have to see a test fail the first time. That gives you greater confidence in passing tests. At least it does to me.
Starting to write the implementation of a reverse Polish calculator in Java
The first order of business is to get the tests that directly depend on calculate() to pass. With those taken care of, the ticker tape test will almost take care of itself.
In the instructions for the exercise, Samah suggests using the String.split() function to split up expression into more manageable chunks. According to the documentation, split() is an instance function that takes a “regex” as an argument.
As in “regular expressions.” I admit I’m not very strong on those, I need to read Jonny Fox’s tutorial. For now, though, I just need to make sure that I can split by spaces without the unexpected surprises I’ve had trying to use regular expressions in Microsoft Word and OpenOffice Writer.
The Scala REPL is just the thing for the task. But if you have a Java REPL in your Java installation it might make more sense to use that. Either one should operate on top of the Java Virtual Machine (for the specifics of using the Scala REPL, see my article from July).
scala> var expression = "Hello world! This is a String."
expression: String = Hello world! This is a String.scala> expression.split(" ")
res0: Array[String] = Array(Hello, world!, This, is, a, String.)scala> expression = "3 2 + 8 4 * -"
expression: String = 3 2 + 8 4 * -scala> expression.split(" ")
res1: Array[String] = Array(3, 2, +, 8, 4, *, -)
Okay, now we can get down to the business of actually writing calculate(). Like I said earlier, this is not going to be static because that would complicate the ticker tape feature.
public double calculate(String expression) {
Stack<String> stack = new Stack();
String[] elems = expression.split(" ");
double operand1, operand2;
for (String elem : elems) {
stack.push(elem);
}
// Now we parse, right?
return 0.0; // Keeping this line for now
}Hmm… I seem to have misunderstood something. So I go back to Samah’s instructions for the exercise, specifically the part where she works out the 3 2 + 8 4 × − example.
First 3 is pushed onto the stack, and then 2. But the addition operator is not pushed onto the stack, rather it causes two numbers to be popped off the stack, operated on, and then that result is pushed onto the stack.
So no operators go on the stack, only numbers, which by the exercise instructions are to be of type double. I’d be annoyed with myself right now if I had punched a card with the line Stack<String>.
As it happens, Stack<E> can hold objects but not primitives. But that’s a tiny problem easily solved by the judicious use of primitive wrappers and auto-boxing.
Moving on, we’re going to need a few local variables to assist us in parsing the reverse Polish expression.
public double calculate(String expression) {
Stack<Double> stack = new Stack();
String[] elems = expression.split(" ");
boolean numParseFlag;
char currChar;
double operand1, operand2, parsedNum;
double currVal = 0.0;
for (String elem : elems) {
numParseFlag = true;
if (elem.length() == 1) {
numParseFlag = false;
currChar = elem.charAt(0);
switch (currChar) {
case '+':
operand1 = stack.pop();
operand2 = stack.pop();
currVal = operand1 + operand2;
stack.push(currVal);
break;
case '-':
operand1 = stack.pop();
operand2 = stack.pop();
currVal = operand1 - operand2;
stack.push(currVal);
break;
case '*':
operand1 = stack.pop();
operand2 = stack.pop();
currVal = operand1 * operand2;
stack.push(currVal);
break;
case '/':
operand1 = stack.pop();
operand2 = stack.pop();
currVal = operand1 / operand2;
stack.push(currVal);
break;
default:
numParseFlag = true;
}
}
if (numParseFlag) {
try {
parsedNum = Double.parseDouble(elem);
stack.push(parsedNum);
} catch (NumberFormatException nfe) {
throw nfe;
}
}
}
return currVal;
}We’re not doing anything meaningful with nfe here, so we might as well remove the catch and let the client program worry about it.
The client program for now is going to be our test class as used by the JUnit test runner. Hopefully all the tests will pass, except of course for the ticker tape test.
Testcase: testCalculateWithObelus(basicexercises.ReversePolishCalculatorTest): Caused an ERROR
For input string: "÷"
java.lang.NumberFormatException: For input string: "÷"
...Testcase: testCalculate(basicexercises.ReversePolishCalculatorTest): FAILED
expected:<0.33333> but was:<3.0>
...Testcase: testCalculateWithMinusSign(basicexercises.ReversePolishCalculatorTest): Caused an ERROR
For input string: "?"
java.lang.NumberFormatException: For input string: "?"
...Testcase: testCalculateOnGivenExpression(basicexercises.ReversePolishCalculatorTest): FAILED
expected:<-27.0> but was:<27.0>
...Testcase: testHistory(basicexercises.ReversePolishCalculatorTest): FAILED
expected:<[]> but was:<[This feature has not been implemented yet.]>
...Testcase: testDivisionByZeroCausesException(basicexercises.ReversePolishCalculatorTest): FAILED
Calculating "0 0 /" should have triggered an exception, not given result NaN.
...Testcase: testCalculateWithMultCross(basicexercises.ReversePolishCalculatorTest): Caused an ERROR
For input string: "×"
java.lang.NumberFormatException: For input string: "×"
...
Only the test with calculate("one one plus") passed, because it is set up to expect a NumberFormatException or an IllegalArgumentException.
The tests with the proper minus sign, the multiplication cross and the division obelus failed because they were expecting results, not exceptions.
But the most important thing right now is that the tests with only ASCII operator symbols also failed.
And that’s because I got dyslexic with operand1 and operand2. Either operand2 should be popped off the stack first, or the computation of currVal should use operand2 first.
For addition and multiplication it doesn’t matter, they’re, as the mathematicians say, commutative. The fix for subtraction and division is easy:
case '-':
operand2 = stack.pop();
operand1 = stack.pop();
currVal = operand1 - operand2;
stack.push(currVal);
break;
...omitting case '*', no change...
case '/':
operand2 = stack.pop();
operand1 = stack.pop();
currVal = operand1 / operand2;
stack.push(currVal);
break;I suppose there’s no need to switch them around for addition and multiplication, but the question might come up at code review. Might as well change those now.
This brings up our test pass rate from 12.5% to 37.5%. If the “fancy” operator symbols are not required, we could just discard the corresponding tests. But the fix is so easy, we might as well just do it:
case '-':
case '\u2212':
operand2 = stack.pop();
operand1 = stack.pop();
currVal = operand1 - operand2;
stack.push(currVal);
break;
case '*':
case '\u00D7':
operand2 = stack.pop();
operand1 = stack.pop();
currVal = operand1 * operand2;
stack.push(currVal);
break;
case '/':
case '\u00F7':
operand2 = stack.pop();
operand1 = stack.pop();
currVal = operand1 / operand2;
stack.push(currVal);
break;Now we’re up to 75% of the tests passing. At this point we could either deal with the ticker tape test or the division by zero test. I choose to deal with the ticker tape test first.
Add the private field calcHistory, initializing it with an empty String.
public double calculate(String expression) {
calcHistory = calcHistory + expression + "\n";
Stack<Double> stack = new Stack();
String[] elems = expression.split(" ");
...omitting several lines quoted above...
parsedNum = Double.parseDouble(elem);
stack.push(parsedNum);
}
}
calcHistory = calcHistory + "= " + currVal;
if (calcHistory.endsWith(".0")) {
calcHistory = calcHistory.substring(0,
calcHistory.length() - 2);
}
calcHistory = calcHistory + "\n";
return currVal;
}
}Also remember to change history() to a simple getter of calcHistory.
Alright, 87.5% pass rate. Now this just leaves us the division by zero test. I thought dividing a double by 0.0 would cause an ArithmeticException, but that’s not what happened here.
The test runner reports that
Calculating "0 0 /" should have triggered an exception, not given result NaN.I had completely forgotten about NaN (“not a number”). Let’s go back to the Scala REPL, which has access to the same primitive data types as Java does.
scala> var numberA = Math.sqrt(2)
numberA: Double = 1.4142135623730951scala> val zero = 0.0
zero: Double = 0.0scala> numberA / zero
res2: Double = Infinityscala> numberA = numberA * -1
numberA: Double = -1.4142135623730951scala> numberA / zero
res3: Double = -Infinity
Hmm… I think there’s a function Double.isNaN()…
scala> numberA.isNaN
res4: Boolean = falseJust as I expected, just as it should be. But:
scala> res2.isNaN
res5: Boolean = falsescala> res3.isNaN
res6: Boolean = false
Okay, I don’t know what I should do about this. I could force calculate() to throw an exception upon encountering any of these “non-numbers,” or I could rewrite the test to accept NaN or infinity as a valid result.
However, by the requirements Samah set out, I think maybe the exercise is complete. The basic core functionality is pretty much all there.
The next steps
I feel like we have arrived at a natural stopping point here, and much quicker than I thought it would take. Though I can’t know for sure how long this exercise would have taken me without test-driven development.
I do know how long it took me with: I wrote the stubs and the tests one night about a couple of weeks ago. It took me a couple of hours, though with my attention divided among too many different things.
Then I forgot about it for a few days, until one insomniac night, in about a half hour, I got the program to pretty much the point you see here, though with an ugly kludge for history().
The next steps should be just as easy, provided they’re well defined, and have appropriate tests. Like, for example, what should calculate() do when given an expression with too many numbers or too many operators?
In a code review, we should examine the question of whether it is appropriate for calculate() to return currVal without checking that it matches the number at the top of the stack, which should be the only number on the stack.
That suggests one or two tests to write. I wonder if it would just give a result with too many numbers on the stack? I wonder if too many operators in the expression would cause an IndexOutOfBoundsException? No need to wonder, we can write tests and see what happens.
Samah points out that it is redundant to have these two lines
operand2 = stack.pop();
operand1 = stack.pop();for each operator (regardless of whether or not we also switched them for addition and multiplication). There is surely a more efficient way to go about this.
This is something for code review, unless it gets taken care of during the refactoring part of the test-driven development cycle before then.
Having the tests simplifies the code review. We can try something, and then we can run the tests to make sure that in trying to eliminate this redundancy, or whatever other inefficiency, we haven’t broken something else.
If we do make a GUI, how do we properly encapsulate the stack that the calculator uses internally, but expose the top numbers on the stack to the GUI to display to the user?
I still don’t think test-driven development makes much sense for GUIs, I think that’s expecting of it what we should expect from integration testing and quality assurance.
But for everything else in the program, test-driven development is the way to go.