Intro

The practice of Test-Driven Development (TDD) can sound like an excercise is self-flagellation. It makes sense considering the mainstream attitude towards writing automated tests as a chore akin to writing documentation, rather than a part of development as integral as the code itself. {1} But if part of the distaste is fear of the unknown, then exposure and practice may be acclimatizing forces. This post will introduce the practice of TDD by implementing a Polish notation parser in JavaScript (ES6). We will implement a simple testing framework, and implement several features using the TDD methodology.

Polish Notation

You may be familiar with Polish notation if you have ever seen lisp-like code. In Polish notation, the operator comes first, followed by the operands.

We want to implement a Polish notation parser. The first step is to come up with some user stories. We’ll implement them one at a time using TDD.

• As a user, I want to enter a number and have it recognized as a number
• As a user, I want to enter an expression in Polish notation to add two numbers and view the sum eg: + 1 2 = 3
• As a user, I want to enter an expression to multiply numbers and view the product eg: * 1 2 = 2
• As a user, I want to be able to both multiply and add groups. eg: (* (+ 1 2) 5)

Setup

Since many of us learned JavaScript by using it in the browser, our testing framework will be browser-based. Although running the tests using NodeJS is simpler from a Continuous Integration (CI) perspective, my hope is using a browser rather than command-line will be a gentler introduction. We start with a simple function called runTest, which will take the name of a test function (in the global scope), and run that function. It’s expected that the test function will return true if the test passes, and something falsy otherwise. If there is an exception, the test will fail. When the test passes, we write to the page the word “passed” in green. When it fails, we write the word “FAILED” in red caps.

function runTest(testName) {
    var passed = false;
    try {
        passed = window[testName]()
    }
    catch(e) {
        console.error(e)
    }
    var result = passed ? '<span style="color: green">passed</span>' : '<b style="color:red">FAILED</b>';
    document.write(testName + ' ' + result + '<br>');
}

Since we will be adding tests incrementally, we will create an array of test names, and execute runTest against each name. Another way to do things would be to get a list of functions in the global scope beginning with a certain prefix like test, and just execute all of them. I want to avoid as much magic as we can in this post, so we will just manually specify them.

var tests = [];
tests.forEach(runTest);

This code is placed inside a script block and saved in a file called expressions.html. We’ll open this page in our browser, and reload it whenever we want to run the tests.

Adding Numbers and Starting with TDD

Let’s start with the first user story:

As a user, I want to enter a number and have it recognized as a number.

In TDD, we write a failing test for this first and add it to the tests array.

function testNum() {
  return evaluateExpression("3") === 3;
}

var tests = [
  'testNum'
];

We will assume that there will be a function called evaluateExpression. When we call it with the string 3, we should get back the number 3. Reloading the browser to run the test, we should see that the test failed. Opening the developer console to view the console logs, we see that the error was:

evaluateExpression is not defined

That makes sense since we didn’t write it yet. Let’s do this now. One of the principles of TDD is to get the test “green” (or passing) as soon as possible. That means we should provide the simplest solution that makes the test pass. Once that is done, we can modify our function to make it better. This is called the “red, green, refactor” cycle. The test starts out “red”. We make it “green” as simply and quickly as possible. Then, we refactor the code to remove duplication, satisfy edge cases, and bring it to the final state, all the while keeping the test green as much as possible.

To do this for the test above, we will just make evaluateExpression return the number 3 directly.

function evaluateExpression() {
  return 3
}

This may seem silly since the implementation will be just a one-liner; but, when starting out, it’s important to get a feel for the process. When we come to a feature that is not so easily implemented, we’ll want to keep in mind that the task is not to complete a fully-formed feature, but to make the test green. Some people including Kent Beck, the creator of TDD, have said that this sort of rigorous cycle helps keep them on task and working towards the goal, rather than getting bogged down by the ambiguity of a feature. We’ll refactor this code to remove duplication by removing the 3 that occurs in both the test and the return of the function.

function evaluateExpression(expr) {
  return parseInt(expr);
}

Great, we have implemented the first user story using TDD. Let’s move on to the next.

refs/tags/story-numbers

Addition

As a user, I want to enter an expression in Polish notation to add two numbers and view the sum eg: + 1 2 = 3

Remember the red, green, refactor cycle. Let’s create the failing test and add it to tests array.

function testAdd() {
  return evaluateExpression("+ 1 2") == 3;
}

var tests = [
  'testNum',
  'testAdd'
];

Let’s implement this in the simplest way possible. We modify the evaluateExpression function to return a hard-coded 3 if the expression starts with a plus-sign.

function evaluateExpression(expr) {
  // if the first character is a plus
  if(expr.charAt(0) === '+') {
    return 3;
  }
  return parseInt(expr);
}

Reloading to check, this makes the tests pass. It’s time to refactor. We will create a function called sum, which we pass operands to. Keeping in mind that we want to keep the test green for as long as possible, we limit the changes we make, and move the hard-coded 3 to the sum function.

    function evaluateExpression(expr) {
        if(expr.charAt(0) === '+') {
            // return the result of summing "parts"
            // whatever that turns out to be
            return sum(parts);
        }
        return parseInt(expr);
    }

    function sum() {
        return 3;
    }

Focusing on the sum function, we want this to just accept an array of numbers, and return the sum. Implementing that looks like:

function sum(operands) {
  return operands.reduce((a, b) => a + b, 0);
}

This is similar to using a loop:

function sum(operands) {
  var value = 0;
  for(var i = 0; i < operands.length; i++) {
    value += operands[i];
  }
  return value;
}

Saving the sum definition makes the test red, but we can make it green again by passing evaluated numbers to the sum function.

function evaluateExpression(expr) {
  if(expr.charAt(0) === '+') {
    // split a string into an array by white-space
    var parts = expr.split(/\s+/);
    // throw away the plus by removing the first-element of the array
    parts.shift(); 
    // and convert each element to a number
    parts = parts.map((i) => parseInt(i));
    return sum(parts);
  }
  return parseInt(expr);
}

There’s a small nitpick here. We call parseInt twice. Can we DRY this up? Although we might not always want to do so, DRY-ing in this case will help us with future user stories. We can improve this by calling evaluateExpression recursively.

function evaluateExpression(expr) {
  if(expr.charAt(0) === '+') {
    var parts = expr.split(/\s+/);
    parts.shift();
    // call evaluateExpression recursively to convert each element to a number
    parts = parts.map(evaluateExpression);
    return sum(parts);
  }
  return parseInt(expr);
}

On the recursive call, the function will NOT detect a plus at the beginning of the string, so will fall through to the last case, calling parseInt.


refs/tags/story-addition

Multiplication

The next user story is similar to the last, so it should be really easy to “make green”, but there will be a big opportunity to refactor.

As a user, I want to enter an expression to multiply numbers and view the product eg: * 1 2 = 2

The test is similar to the last. Make sure to add it to the tests array!

function testMultiply() {
  return evaluateExpression("* 1 2") == 2;
}

Making it green is super simple because we can just copypasta most of what we did before.

function evaluateExpression(expr) {
  if(expr.charAt(0) === '+') {
    var parts = expr.split(/\s+/);
    parts.shift();
    parts = parts.map(evaluateExpression);
    return sum(parts);
  }
  // we just copied this whole part from the branch above 🤮
  else if(expr.charAt(0) === '*') {
    var parts = expr.split(/\s+/);
    parts.shift();
    parts = parts.map(evaluateExpression);
    return product(parts);
  }
  return parseInt(expr);
}
function product(operands) {
  return operands.reduce((a, b) => a * b, 1);
}

This makes the tests pass, but it’s time to refactor. Since we’ve copypasta’d, there should be a lot we can do. We extract the common lines out of the branches, and modify the final return to look at only the first token.

function evaluateExpression(expr) {
  var parts = expr.split(/\s+/);
  var first = parts.shift();
  parts = parts.map(evaluateExpression);
  if(first === '+') {
    return sum(parts);
  }
  else if(first === '*') {
    return product(parts);
  }
  return parseInt(first);
}

refs/tags/story-multiplication

Parenthetical expressions

Finally, we are ready to implement the first complex user story, which is the biggest one yet.

As a user, I want to be able to both multiply and add groups. eg: (* (+ 1 2) 5)

This is a bigger user story because there are some things implied in it that are not explicitly stated (a common problem in software estimation). Although there is only one nested grouped expression shown, it’s implied that there can be any number of nested grouped expressions, and to any level, meaning you could have something like:

(* 2 (+ (* 1 2) (+ 2 2)))

Another thing that has been implied is that whitespace is not required next to parentheses. To keep the implementation simple, we will reject this implication explicitly, and require that there be spaces between all parentheses, operators, and operands. Despite these implications, we will start with a simpler test.

function testAddGroup() {
  return evaluateExpression("( + 1 2 )") === 3;
}

The naive approach to implementing this might have us just strip the parentheses from the expression and use our function as we did before. Since I don’t think this helps us move the needle at all, I’m going to skip a bit ahead. When we see an open-parenthesis, we will assume that we are starting a new expression. The operator should be the next token. We will process tokens until we come to a close-parenthesis. When we come to a close-parenthesis, we will have all the operands evaluated, and we can apply the operator to the operands. We’ll continue processing the list of tokens wherever we left off.

We wind up refactoring what we have to separate tokenization and evaluation. We also combine the operator branches, and use a dictionary to lookup the operator function we want (sum or product). We also change the operand evaluation to use a while loop instead of a map. This will be important later for recursively evaluating all of the operands when we come to nested groups. This relies on tokens being passed by reference to recursive calls.

var ops = {'+': sum, '*': product};

function evaluateExpression(expr) {
  var tokens = expr.split(/\s+/);
  return _evaluateExpression(tokens)[0];
}
function _evaluateExpression(tokens) {
    var first = tokens.shift();
    var op = ops[first];
    if(op) {
      // This doesn't help us right now, but later this
      // control structure will allow us to keep processing
      // operands until we run out of them.  We're relying
      // on the `tokens` field being passed by reference,
      // so that we keep on removing tokens from the
      // original list, until it is empty.
      var operands = [];
      do {
          var result = _evaluateExpression(tokens);
          operands = operands.concat(result);
      } while(tokens.length);
      return [op(operands)];
    } 
    return [parseInt(first)];
}

I should stop a moment and note that these particular steps and formulation are derived after the fact. I’ve already implemented this, and I want to show the cleanest way of arriving at my final solution. When I first implemented this via TDD, I was stuck at this step for awhile, and the testAddGroup test stayed red too long, and the other tests went red for awhile too. I don’t have an easy answer as to what to do if you find yourself in this situation, except that recursive solutions are often like this. Recursion can be like this by definition, because you define some base cases, and then the big recursive step that is sometimes like catching lightning in a bottle.

refs/tags/story-groups

With that, we can finish our implementation by adding branches that deal with the parentheses.

function _evaluateExpression(tokens) {
  // elided
  if(op) {
    // elided
    var result = _evaluateExpression(tokens);
    operands = operands.concat(result);
    // elided
  } 
  else if(first === '(') {
    return _evaluateExpression(tokens);
  }
  else if(first === ')') {
    return [];
  }
  // elided
}

If we encounter an open-parenthesis, we must recurse in order to handle a nested expression. If we encounter a close-parenthesis, we return an empty array. In the current implementation, this will be concatenated to the operands array, and so leave it unchanged. This is a problem that will become visible after we add the next test, but this makes all the current tests pass.

Nested groups

We’ll now test nested groups.

function testMultGroupNested() {
  return evaluateExpression("( + ( * 1 2 ) ( + 2 2 ) )") === 6;
}

This test fails for the reason I hinted at earlier. When we see a close-parenthesis, instead of just adding the empty array to our operands, we must take it as some sign that we need to end our recursion, and allow some parent-level to process the remaining tokens. We’ll modify our code to do this.

function _evaluateExpression(tokens) {
  // elided
  if(op) {
      var operands = [];
      do {
          var result = _evaluateExpression(tokens);
          // we have to stop processing if we see an empty array,
          // allowing the caller to process further tokens.
          if(!result.length) { break; }
          operands = operands.concat(result);
      } while(tokens.length);
      return [op(operands)];
  } 
  // elided
}

This makes our tests pass. If we were implementing this feature for a project, we’d add more test cases with deeper nesting just to make sure it works right.

refs/tags/story-nested-groups

Conclusion

In this post, we implemented a Polish notation parser by using TDD. TDD is a method of testing whereby you write tests first, and follow a red, green, refactor cycle in writing your code. Some say that it improves productivity and results in cleaner code. I think that it’s an important methodology to practice in order to learn how to write testable code, but I don’t write most of my code using TDD. Where I do like to use TDD is where the requirements are very clear, and I have a somewhat clear idea of what the implementation should be. I also avoid using it when implementing primarily UI-level features like animations. Still, it’s important to know how to use TDD to test features like these, and doing so has made me a better programmer.

Notes

{1}

I wrote about this before in [Let’s Test]({{ site.baseurl }}/programming/2019/02/04/tdd.html)

• tdd
• automated-testing
• recursion
• javascript