### What is Test Driven Development?

Driving development with automated tests is called Test Driven Development.

1. Red—write a little test that doesn’t work, perhaps doesn’t even compile at first
2. Green—make the test work quickly, committing whatever sins necessary in the process
3. Re-factor—eliminate all the duplication created in just getting the test to work

### Test Driven Development Sample Problem

#### Infix->Postfix conversion

In the current post, I demonstrate one of the TDD problems ‘Infix->Postfix conversion’.
Given an expression in infix form like
3 * (2 + 5)
Transform it to its postfix equivalent
3 2 5 + *
A more complex infix expression would be
((((1*(2+3))-3)+4)*5).
Its postfix equivalent would be 1 2 3 + * 3 – 4 + 5 *

### Approach

To know more about infix to postfix conversion algorithm read here: http://scriptasylum.com/tutorials/infix_postfix/algorithms/postfix-evaluation/index.htm

Algorithm in short is:

1. Fetch a character
2. If numeric, add it to result
3. If operator, check if it has higher precedence (By default * and / has higher precedence over + and -. We can override the precedence using
4. brackets)
5. If yes, pop the stack and add the popped one to result
6. Back to step 1.

Test case: The infix expression can’t be null or empty string

```
public void testValidateInfixExpression() {
try {
new PostfixExp(null);
fail("Infix expression can't be null");
} catch (Exception e) {
}
try {
new PostfixExp("");
fail("Infix expression can't be empty");
} catch (Exception e) {
}
try {
new PostfixExp(" ");
fail("Infix expression can't be blank");
} catch (Exception e) {
}
}
```

PostfixExp class doesn’t exist so it has to be created as well as the constructor. Implement the constructor to pass the test.

```    public PostfixExp(String inInfixExpression) {
if (inInfixExpression == null) {
throw new IllegalArgumentException("inInfixExpression cannot be null or empty");
}
if (inInfixExpression.trim().equals("")) {
throw new IllegalArgumentException("inInfixExpression cannot be empty");
}
}
```

Test case: The first char in infix expression can’t be an operator. Add a test case to the above unit test.

```
try {
new PostfixExp("+");
fail("The first char cannot be an operator");
} catch (Exception e) {
}
```

Implement the code so that the above test passes.

```        char[] chars = inInfixExpression.toCharArray();
if (isOperator(chars[0])) {
throw new IllegalArgumentException("First char cannot be operator");
}
```

Method isOperator doesn’t exist. We now realize that we missed a test case here so we take a step back and come with a new test case.

Test case: We support multiplication, division, add and substract so the operator char has to be one of these: * / + –

```    public void testIsOperator() {
assertTrue(PostfixExp.isOperator('+'));
assertTrue(PostfixExp.isOperator('-'));
assertTrue(PostfixExp.isOperator('*'));
assertTrue(PostfixExp.isOperator('/'));
}
```

We now implement isOperator() method.

```    public static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
```

Once this is implemented, we should run the previous unit test which will assert that the first char is not an operator.

```    public PostfixExp(String inInfixExpression) {
if (inInfixExpression == null) {
throw new IllegalArgumentException("inInfixExpression cannot be null or empty");
}
if (inInfixExpression.trim().equals("")) {
throw new IllegalArgumentException("inInfixExpression cannot be empty");
}
char[] chars = inInfixExpression.toCharArray();
if (isOperator(chars[0])) {
throw new IllegalArgumentException("First char cannot be operator");
}
}
```

Test case: Parse number from the infix expression: If infix has “234+”, we should be able to parse the string to return 234 as number.

```    public void testParseNumber() {
assertEquals(new Integer(234), PostfixExp.parseNumber("234+"));
}
```

Test case: We want to call parseNumber when we encounter the first digit character so we make sure that the string passed to parseNumber() starts with a digit character.

```    public void testParseNumber() {
try {
PostfixExp.parseNumber("+234");
fail("First char should be a digit");
} catch (RuntimeException e) {
}
assertEquals(new Integer(234), PostfixExp.parseNumber("234+"));
}
```

Test case: Since parseNumber is a public method, we will want to make sure that the string parameter is not empty.

```    public void testParseNumber() {
try {
PostfixExp.parseNumber("");
fail("The string passed can't be empty");
} catch (RuntimeException e) {
}
try {
PostfixExp.parseNumber("+234");
fail("First char should be a digit");
} catch (RuntimeException e) {
}
assertEquals(new Integer(234), PostfixExp.parseNumber("234+"));
}
```

We implement parseNumer:

```    public static Integer parseNumber(@NotNull String inNumberString) {
char[] numChars = inNumberString.toCharArray();
if (numChars.length == 0) {
throw new IllegalArgumentException("inChars is empty");
}
int i = 0;
char num = numChars[i];
if (!Character.isDigit(num)) {
throw new RuntimeException("Not an integer " + num);
}
StringBuilder sb = new StringBuilder();
sb.append(num);
while (Character.isDigit(numChars[i])) {
sb.append(numChars[i++]);
}
return Integer.valueOf(sb.toString());
}
```

Suppose the number to be parsed is a single digit, for example ’2+3′ which returns us 2, we may not need to a StringBuilder. It can simply return after parsing the first char.

```     assertEquals(new Integer(2), PostfixExp.parseNumber("2"));
assertEquals(new Integer(2), PostfixExp.parseNumber("2+3"));
```

We re-factor parseNumber.

```    public static Integer parseNumber(@NotNull String inNumberString) {
..
if (numChars.length == 1 || isOperator(numChars[i])) {
return Integer.valueOf(String.valueOf(num));
}
..
}
```

Test case: Given two operators we should be able to know whether the second one has higher precedence.

```    public void testHighPrecedence() {
assertFalse(PostfixExp.hasHighPrecedence('+', '*'));
assertFalse(PostfixExp.hasHighPrecedence('-', '*'));
assertFalse(PostfixExp.hasHighPrecedence('+', '/'));
assertFalse(PostfixExp.hasHighPrecedence('-', '/'));
assertTrue(PostfixExp.hasHighPrecedence('*', '+'));
assertTrue(PostfixExp.hasHighPrecedence('/', '-'));
assertTrue(PostfixExp.hasHighPrecedence('*', '+'));
assertTrue(PostfixExp.hasHighPrecedence('/', '-'));
}
```

We implement hasHighPrecedence.

```    public static boolean hasHighPrecedence(char c1, char c2) {
if (c1 == '+' || c1 == '-') {
return !(c2 == '*' || c2 == '/');
}
return c1 == '*' || c1 == '/';
}
```

Test case: We should make sure that c1 and c2 are valid operators.

```        try {
PostfixExp.hasHighPrecedence('#', '+');
fail("Not a valid operator");
} catch (Exception e) {
}
try {
PostfixExp.hasHighPrecedence('+', '#');
fail("Not a valid operator");
} catch (Exception e) {
}
```

Implement the check in hasHighPrecedence.

```    public static boolean hasHighPrecedence(char c1, char c2) {
if (!isOperator(c1)) {
throw new RuntimeException(c1 + " is not a valid operator");
}
if (!isOperator(c2)) {
throw new RuntimeException(c2 + " is not a valid operator");
}
...
```

Test case: Now we are ready to solve the simplest infix expression=”3″.

```    public void testPostfixExpression() {
PostfixExp p = new PostfixExp("3");
List l = p.getPostfixElements();
assertNotNull(l);
assertEquals(1, l.size());
assertEquals(3, l.get(0));
}
```

Implementation:

```
public PostfixExp(String inInfixExpression) {
...
if (chars.length == 1) {
return;
}
}
public List getPostfixElements() {
return result;
}
```

Test case: Infix expression=”+”, should fail as it is not a digit.

```    public void testPostfixExpression() {
PostfixExp p = new PostfixExp("3");
...
try {
new PostfixExp("+");
fail("Invalid infix expression");
} catch (Exception e) {
}
}
```

The test passes as we already have a validation in place that first char must be a digit.

Test case: Infix expression=”(3)”, should pass as a digit is within the brackets.

```assertEquals("[3]", new PostfixExp("(3)").toString());
```

Implementation:

```    public PostfixExp(String inInfixExpression) {
...
for (int i = 0; i < chars.length; i++) {
if (chars[i]== '(') {
} else if (chars[i]== ')') {
} else if (Character.isDigit(chars[i])) {
Integer num = parseNumber(inInfixExpression.substring(i));
}
}
}
```

Test case: Infix Expression has an opening bracket but is not closed so parsing should fail as it is not a valid expression.

```        try {
new PostfixExp("(3");
fail("Invalid infix expression. Bracket has not been closed.");
} catch (Exception e) {
}
```

Implementation: We introduce bracket level to keep track of brackets. As we open a bracket, we increase the counter and decrease it when we close it.

```    public PostfixExp(String inInfixExpression) {
...
int bracketLevel = 0;
for (int i = 0; i < chars.length; i++) {
if (chars[i]== '(') {
bracketLevel++;
} else if (chars[i]== ')') {
bracketLevel--;
} else if (Character.isDigit(chars[i])) {
Integer num = parseNumber(inInfixExpression.substring(i));
}
if (bracketLevel > 0) {
throw new RuntimeException("Invalid infix expression! A bracket has not been closed");
}
}
...
```

Test case: Infix Expression has a closed bracket but no corresponding open bracket so parsing should fail as it is not a valid expression.

```        try {
new PostfixExp("3)");
fail("Invalid infix expression. There is no opening bracket.");
} catch (Exception e) {
}
```

Implementation:

```        ...
if (bracketLevel < 0) {
throw new RuntimeException("Invalid infix expression! Tried to close a bracket which has no opening bracket");
}
}
```

Test case: Now we introduce operator. Infix Expression=”3+”. When we encounter an operator, we push it on to a stack.

```assertEquals("[3, +]", new PostfixExp("3+").toString());
```

Implementation:

```    public PostfixExp(String inInfixExpression) {
...
for (int i = 0; i < chars.length; i++) {
if (chars[i]== '(') {
...
} else if (isOperator(chars[i])) {
operators.push(chars[i]);
}
}
...
while (!operators.isEmpty()) {
}
```

Test case: Infix expression can’t have a character other than [0-9 ( ) + – * /]

```        ...
try {
new PostfixExp("3#");
fail("Invalid infix expression. # is not a valid operator");
} catch (Exception e) {
}
```

Implementation:

```       ...
for (int i = 0; i < chars.length; i++) {
if (chars[i]== '(') {
bracketLevel++;
} else if (chars[i]== ')') {
bracketLevel--;
} else if (Character.isDigit(chars[i])) {
Integer num = parseNumber(inInfixExpression.substring(i));
} else if (isOperator(chars[i])) {
operators.push(chars[i]);
} else {
throw new RuntimeException("Invalid character " + chars[i]);
}
}
...
```

Test case: We now try several simple infix expressions, all of them passes.

```        assertEquals("[3, 2, +]", new PostfixExp("3+2").toString());
assertEquals("[3, 2, +]", new PostfixExp("(3+2)").toString());
assertEquals("[3, 2, +]", new PostfixExp("(3+(2))").toString());
assertEquals("[3, 2, 3, *, +]", new PostfixExp("3+2*3").toString());
assertEquals("[3, 2, 3, 4, *, +, +]", new PostfixExp("3+2+3*4").toString());
```

Test case: In absence of brackets, we should make sure ‘*’ and ‘/’ has higher precedence over ‘+’ and ‘-’ which means “3+2+3*4″ is equal to “3+2+(3*4)”

```        assertEquals("[3, 2, *, 3, +, 4, +]", new PostfixExp("3*2+3+4").toString());
```

The test fails as we have not implemented precedence logic. Before we push a new operator, we check whether the stack operator has higher precedence compared to it. If it has we pop the stack operator and add it to result.

```        for (int i = 0; i < chars.length; i++) {
...
} else if (isOperator(chars[i])) {
if (hasHighPrecedence(operators.peek(), chars[i])) {
}
operators.push(chars[i]);
}
...
}
```

We run the test again and it fails with empty stack exception:

```java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at tdd.PostfixExp.(PostfixExp.java:38)
at tdd.PostfixTests.testPostfixExpression(PostfixTests.java:140)
```

This is right as the stack may not have any operator when we call peek. We need to make sure the stack is not empty before we try peek.

```                ...
if (!operators.isEmpty() && hasHighPrecedence(operators.peek(), chars[i])) {
}
operators.push(chars[i]);
...
```

With this change, the test passes.

Just to make sure the default precedence works, we try a little more complicated expression.

```      assertEquals("[3, 2, 3, *, 4, 5, *, +, +]", new PostfixExp("3+2*3+4*5").toString());
```

The test passes.

Test case: Brackets should let override the precedence. The ‘+’ operation is on the left side of higher precedence operator ‘*’. The infix expression “3+2*3″ converts into postfix expression “3 2 3 * +” as ‘*’ has higher precedence over ‘+’. We can use brackets around to override precedence, “(3+2)*3″, should convert to postfix expression as “3 2 + 3 *”

```        assertEquals("[3, 2, +, 3, *]", new PostfixExp("(3+2)*3").toString());
```

The test fails. If we encounter a closing bracket, we pop the stack and add it to the result.

```      for (int i = 0; i < chars.length; i++) {
if (chars[i]== '(') {
bracketLevel++;
} else if (chars[i]== ')') {
if (!operators.isEmpty()) {
}
bracketLevel--;
}
...
}
```

Test case: We should let brackets override the default precedence. The ‘+’ operation is on the right side of higher precedence operator ‘*’.

```    assertEquals("[3, 2, 3, +, *]", new PostfixExp("3*(2+3)").toString());
```

Test fails as ‘*’ has higher precedence.

```junit.framework.ComparisonFailure:
Expected :[3, 2, 3, +, *]
Actual   :[3, 2, *, 3, +]
at tdd.PostfixTests.testPostfixExpression(PostfixTests.java:157)
```

We fix this by making sure that we check the precedence only when the bracketLevel is 0.

```            ...
else if (isOperator(chars[i])) {
if (!operators.isEmpty() && bracketLevel == 0 && hasHighPrecedence(operators.peek(), chars[i])) {
}
operators.push(chars[i]);
...
```

Test case: The test passes and now we can try some more complicated infix expressions.

```        assertEquals("[3, 2, *, 3, 5, 2, +, *, +]", new PostfixExp("3*2+3*(5+2)").toString());
assertEquals("[3, 2, *, 3, 5, 2, 3, *, +, *, +]", new PostfixExp("3*2+3*(5+2*3)").toString());
assertEquals("[3, 2, +, 5, *]", new PostfixExp("((3+2)*5)").toString());
assertEquals("[3, 1, -, 2, /, 3, *, 5, +]", new PostfixExp("((3-1)/2)*3+5").toString());
assertEquals("[3, 1, -, 2, /, 3, 5, +, *]", new PostfixExp("((3-1)/2)*(3+5)").toString());
assertEquals("[1, 2, 3, +, *, 3, -, 4, +, 5, *]", new PostfixExp("((((1*(2+3))-3)+4)*5)").toString());
```

The test case passes so we leave the implementation here.

### Unit tests

```import junit.framework.TestCase;

import java.util.List;

/**
* 10 2 8 * + 3 -
* 3 2 5 + *
*/
public class PostfixTests extends TestCase {

public void testHighPrecedence() {
assertFalse(PostfixExp.hasHighPrecedence('+', '*'));
assertFalse(PostfixExp.hasHighPrecedence('-', '*'));
assertFalse(PostfixExp.hasHighPrecedence('+', '/'));
assertFalse(PostfixExp.hasHighPrecedence('-', '/'));
assertTrue(PostfixExp.hasHighPrecedence('*', '+'));
assertTrue(PostfixExp.hasHighPrecedence('/', '-'));
assertTrue(PostfixExp.hasHighPrecedence('*', '+'));
assertTrue(PostfixExp.hasHighPrecedence('/', '-'));
try {
PostfixExp.hasHighPrecedence('#', '+');
fail("Not a valid operator");
} catch (Exception e) {
}
try {
PostfixExp.hasHighPrecedence('+', '#');
fail("Not a valid operator");
} catch (Exception e) {
}
}

public void testParseNumber() {
try {
PostfixExp.parseNumber("");
fail("The string passed can't be empty");
} catch (RuntimeException e) {
}
try {
PostfixExp.parseNumber("+234");
fail("First char should be a digit");
} catch (RuntimeException e) {
}
assertEquals(new Integer(2), PostfixExp.parseNumber("2+3"));
assertEquals(new Integer(234), PostfixExp.parseNumber("234+"));
}

public void testIsOperator() {
assertTrue(PostfixExp.isOperator('+'));
assertTrue(PostfixExp.isOperator('-'));
assertTrue(PostfixExp.isOperator('*'));
assertTrue(PostfixExp.isOperator('/'));
}

public void testValidateInfixExpression() {
try {
new PostfixExp(null);
fail("Infix expression can't be null");
} catch (Exception e) {
}
try {
new PostfixExp("");
fail("Infix expression can't be empty");
} catch (Exception e) {
}
try {
new PostfixExp(" ");
fail("Infix expression can't be blank");
} catch (Exception e) {
}
try {
new PostfixExp("+");
fail("The first char cannot be an operator");
} catch (Exception e) {
}
try {
new PostfixExp("23+\$");
fail("Invalid Infix expression");
} catch (Exception e) {
}
PostfixExp p = new PostfixExp("3+2");
List l = p.getPostfixElements();
assertNotNull(l);
assertEquals(3, l.size());
assertEquals(3, l.get(0));
assertEquals(2, l.get(1));
assertEquals('+', l.get(2));

p = new PostfixExp("(3+2)");
l = p.getPostfixElements();
assertNotNull(l);
assertEquals(3, l.size());
assertEquals(3, l.get(0));
assertEquals(2, l.get(1));
assertEquals('+', l.get(2));
assertEquals("[3, 2, +]", p.toString());

assertEquals("[3, 2, 5, *, +]", new PostfixExp("3+2*5").toString());
assertEquals("[3, 2, +, 5, *]", new PostfixExp("(3+2)*5").toString());
assertEquals("[3, 2, +, 5, *]", new PostfixExp("((3+2)*5)").toString());
assertEquals("[3, 1, -, 2, /, 3, *, 5, +]", new PostfixExp("((3-1)/2)*3+5").toString());
assertEquals("[3, 1, -, 2, /, 3, 5, +, *]", new PostfixExp("((3-1)/2)*(3+5)").toString());
assertEquals("[1, 2, 3, +, *, 3, -, 4, +, 5, *]", new PostfixExp("((((1*(2+3))-3)+4)*5)").toString());
}

public void testPostfixExpression() {
PostfixExp p = new PostfixExp("3");
List l = p.getPostfixElements();
assertNotNull(l);
assertEquals(1, l.size());
assertEquals(3, l.get(0));
assertEquals("[3]", p.toString());
try {
new PostfixExp("+");
fail("Invalid infix expression");
} catch (Exception e) {
}

try {
new PostfixExp("(");
fail("Invalid infix expression");
} catch (Exception e) {
}

assertEquals("[3]", new PostfixExp("(3)").toString());

try {
new PostfixExp("(3");
fail("Invalid infix expression. Bracket has not been closed.");
} catch (Exception e) {
}

try {
new PostfixExp("3)");
fail("Invalid infix expression. There is no opening bracket.");
} catch (Exception e) {
}

assertEquals("[3, +]", new PostfixExp("3+").toString());

try {
new PostfixExp("3#");
fail("Invalid infix expression. # is not a valid operator");
} catch (Exception e) {
}

assertEquals("[3, 2, +]", new PostfixExp("3+2").toString());
assertEquals("[3, 2, +]", new PostfixExp("(3+2)").toString());
assertEquals("[3, 2, +]", new PostfixExp("(3+(2))").toString());
assertEquals("[3, 2, 3, *, +]", new PostfixExp("3+2*3").toString());
assertEquals("[3, 2, +, 3, 4, *, +]", new PostfixExp("3+2+3*4").toString());
assertEquals("[3, 2, *, 3, +, 4, +]", new PostfixExp("3*2+3+4").toString());
assertEquals("[3, 2, 3, *, 4, 5, *, +, +]", new PostfixExp("3+2*3+4*5").toString());

assertEquals("[3, 2, +, 3, *]", new PostfixExp("(3+2)*3").toString());
assertEquals("[3, 2, 3, +, *]", new PostfixExp("3*(2+3)").toString());

assertEquals("[3, 2, *, 3, 5, 2, +, *, +]", new PostfixExp("3*2+3*(5+2)").toString());
assertEquals("[3, 2, *, 3, 5, 2, 3, *, +, *, +]", new PostfixExp("3*2+3*(5+2*3)").toString());
assertEquals("[3, 2, +, 5, *]", new PostfixExp("((3+2)*5)").toString());
assertEquals("[3, 1, -, 2, /, 3, *, 5, +]", new PostfixExp("((3-1)/2)*3+5").toString());
assertEquals("[3, 1, -, 2, /, 3, 5, +, *]", new PostfixExp("((3-1)/2)*(3+5)").toString());
assertEquals("[1, 2, 3, +, *, 3, -, 4, +, 5, *]", new PostfixExp("((((1*(2+3))-3)+4)*5)").toString());

}
}
```

### Source Code

```import com.sun.istack.internal.NotNull;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostfixExp {

public PostfixExp(String inInfixExpression) {
if (inInfixExpression == null) {
throw new IllegalArgumentException("inInfixExpression cannot be null or empty");
}
if (inInfixExpression.trim().equals("")) {
throw new IllegalArgumentException("inInfixExpression cannot be empty");
}
char[] chars = inInfixExpression.toCharArray();
if (isOperator(chars[0])) {
throw new IllegalArgumentException("First char cannot be operator");
}
if (chars.length == 1) {
return;
}
Stack operators = new Stack();
int bracketLevel = 0;
//3+2*3+4*5
for (int i = 0; i < chars.length; i++) {
if (chars[i]== '(') {
bracketLevel++;
} else if (chars[i]== ')') {
if (!operators.isEmpty()) {
}
bracketLevel--;
} else if (Character.isDigit(chars[i])) {
Integer num = parseNumber(inInfixExpression.substring(i));
} else if (isOperator(chars[i])) {
if (!operators.isEmpty() && bracketLevel == 0 && hasHighPrecedence(operators.peek(), chars[i])) {
}
operators.push(chars[i]);
} else {
throw new RuntimeException("Invalid character " + chars[i]);
}
}
if (bracketLevel > 0) {
throw new RuntimeException("Invalid infix expression! A bracket has not been closed");
}
if (bracketLevel < 0) {
throw new RuntimeException("Invalid infix expression! Tried to close a bracket which has no opening bracket");
}
while (!operators.isEmpty()) {
}
}

public static boolean hasHighPrecedence(char c1, char c2) {
if (!isOperator(c1)) {
throw new RuntimeException(c1 + " is not a valid operator");
}
if (!isOperator(c2)) {
throw new RuntimeException(c2 + " is not a valid operator");
}
if (c1 == '+' || c1 == '-') {
return !(c2 == '*' || c2 == '/');
}
return c1 == '*' || c1 == '/';
}

public static Integer parseNumber(@NotNull String inNumberString) {
return parseNumber(inNumberString.toCharArray());
}

private static Integer parseNumber(@NotNull char[] inNumChars) {
if (inNumChars.length == 0) {
throw new IllegalArgumentException("inChars is empty");
}
int i = 0;
char num = inNumChars[i];
if (!Character.isDigit(num)) {
throw new RuntimeException("Not an integer " + num);
}
if (inNumChars.length == 1 || isOperator(inNumChars[i])) {
return Integer.valueOf(String.valueOf(num));
}
StringBuilder sb = new StringBuilder();
sb.append(num);
i++;
while (Character.isDigit(inNumChars[i])) {
sb.append(inNumChars[i++]);
}
return Integer.valueOf(sb.toString());
}

public static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}

public List getPostfixElements() {
return result;
}

public String toString() {
return result.toString();
}

private List result = new ArrayList();
();
}
```
Share.