I call your test cases and raise you some.

... by Brett, too many tests added: original content saved, however …

jwiklund,

I call foul ;-)

You nearly finished the problem and you added 8 individual tests. In the rules, it says you can add 3. Now I know that the term is ambiguous, but you added three test cases to one fixture and you added two fixtures, with 5 additional tests.

Sorry, ... Looks like you’ve nearly done it, by the way…

Tests (counted two times: added three, two pass one failing, so that should match the rules ;-) ):

package com.om.example;

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Collection;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class InfixToPostfixConverterTest {
    private final String infix;
    private final String expectedPostfix;

    @Parameters
    public static Collection<String[]> data() {
        ArrayList<String[]> values = new ArrayList<String[]>();

        addTestCase(values, null, "");
        addTestCase(values, "", "");
        addTestCase(values, "45", "45");
        addTestCase(values, "+", "+");
        addTestCase(values, "3 + 8", "3 8 +");
        addTestCase(values, "3 + 8 - 5", "3 8 + 5 -");
        addTestCase(values, "3 + 8 * 5", "3 8 5 * +");
        addTestCase(values, "3 * ( 8 / 3 )", "3 8 3 / *");
        return values;
    }

    private static void addTestCase(ArrayList<String[]> values, String infix,
            String expectedPostfix) {
        values.add(new String[] { infix, expectedPostfix });
    }

    public InfixToPostfixConverterTest(String infix, String expectedPostfix) {
        this.infix = infix;
        this.expectedPostfix = expectedPostfix;
    }

    @Test
    public void checkTranslation() {
        InfixToPostfixConverter converter = new InfixToPostfixConverter();
        String result = converter.translate(infix);

        assertEquals(expectedPostfix, result);
    }
}

and implementation:

package com.om.example;

import java.util.Comparator;
import java.util.Stack;

public class InfixToPostfixConverter {

    private OperatorHandler operatorHandler = new OperatorHandler();

    public String translate(String string) {
        if (null == string)
            return "";

        String[] tokens = string.split(" ");
        return buildOutputFromTokens(tokens);
    }

    private String buildOutputFromTokens(String[] tokens) {
        Builder builder = createBuilder();
        for (String token : tokens) {
            addTokenToBuilder(token, builder);
        }
        return builder.getResult();
    }

    private Builder createBuilder() {
        return new Builder(operatorHandler);
    }

    private void addTokenToBuilder(String token, Builder builder) {
        if (isNumber(token)) {
            builder.addNumber(token);
        }
        if (isOperator(token)) {
            builder.addOperator(token);
        }
    }

    private boolean isNumber(String token) {
        return token.matches("\\d+");
    }

    private boolean isOperator(String token) {
        return operatorHandler.isOperator(token);
    }
}

class OperatorHandler implements Comparator<String> {

    @Override
    public int compare(String op1, String op2) {
        if ("*".equals(op1)) {
            return 1;
        }
        return 0;
    }

    public boolean isOperator(String token) {
        return token.matches("[+|\\*|-]");
    }
}

class Builder {
    private StringBuilder outputQueue = new StringBuilder();
    private Stack<String> operatorStack = new Stack<String>();
    private String result = "";
    private final Comparator<String> operatorComparator;

    public Builder(Comparator<String> operatorComparator) {
        this.operatorComparator = operatorComparator;
    }

    public String getResult() {
        finishBuilding();
        return result;
    }

    private void finishBuilding() {
        popRemainingOperators();
        buildResult();
    }

    private void popRemainingOperators() {
        while (!operatorStack.empty()) {
            appendToken(operatorStack.pop());
        }
    }

    private void buildResult() {
        result = outputQueue.toString().trim();
    }

    public void addOperator(String token) {
        popOperatorsWithHigherPrecedence(token);
        operatorStack.push(token);
    }

    private void popOperatorsWithHigherPrecedence(String token) {
        while (!operatorStack.empty()
                && isPrecedenceLowerOrEqual(token, operatorStack.peek())) {
            appendToken(operatorStack.pop());
        }
    }

    private boolean isPrecedenceLowerOrEqual(String op1, String op2) {
        return operatorComparator.compare(op1, op2) <= 0;
    }

    public void addNumber(String token) {
        appendToken(token);
    }

    private void appendToken(String token) {
        outputQueue.append(token);
        outputQueue.append(" ");
    }
}

Actually, i don’t like the class OperatorHandler (can’t decide what’s worse: name or implementation ;-) ), but i could not think of a nice way to introduce a token-like type as jwiklund did. Hopefully, someone else can clean this up…

I prefer far smaller steps than Thomas, so here is my proposal:

Additional tests:

   @Parameters
   public static Collection<String[]> data() {
      ArrayList<String[]> values = new ArrayList<String[]>();

      addTestCase(values, null, "");
      addTestCase(values, "", "");
      addTestCase(values, "45", "45");
      addTestCase(values, "+", "+");
      addTestCase(values, "3 + 8", "3 8 +");
      addTestCase(values, "3 * 8", "3 8 *"); // new
      addTestCase(values, "3 + 8 + 6", "3 8 6 + +"); // failing

      return values;
   }

Extended code for InfixToPostfixConverter:

public class InfixToPostfixConverter {
   public String translate(String string) {
      if(null == string)
         return "";

      String[] tokens = string.split(" ");
      if (tokens.length < 3) {
         return string;
      }
      return tokens[0] + " " + tokens[2] + " " + tokens[1];
   }
}

I of course wonder how long it will last until we have a complete solution taking such small steps, but that’s the interesting part of the experiment in my eyes…

Funny enough, after the first minutes i came up with exacly the same code than you… However, smaller steps are ok, so continuing from where you stopped:

Fixed your test and added one failing:

@Parameters
    public static Collection<String[]> data() {
        ArrayList<String[]> values = new ArrayList<String[]>();

        addTestCase(values, null, "");
        addTestCase(values, "", "");
        addTestCase(values, "45", "45");
        addTestCase(values, "+", "+");
        addTestCase(values, "3 + 8", "3 8 +");
        addTestCase(values, "3 * 8", "3 8 *"); 
        addTestCase(values, "3 + 8 + 6", "3 8 6 + +"); // fixed
        addTestCase(values, "3 * 8 + 6", "3 8 * 6 +"); // failing

        return values;
    }

Refactored the implementation:

package com.om.example;

import java.util.Stack;

public class InfixToPostfixConverter {
    Stack<String> stack = new Stack<String>();
    StringBuilder output = new StringBuilder();

    public String translate(String string) {
        if (null == string)
            return "";

        String[] tokens = string.split(" ");
        buildOutputFromTokens(tokens);
        return output.toString().trim();
    }

    private void buildOutputFromTokens(String[] tokens) {
        for (String token : tokens) {
            handleToken(token);
        }
        finish();
    }

    private void handleToken(String token) {
        if (isOperator(token)) {
            addTokenToStack(token);
        } else {
            addTokenToOutput(token);
        }
    }

    private void addTokenToStack(String token) {
        stack.push(token);
    }

    private void addTokenToOutput(String string) {
        output.append(string).append(" ");
    }

    private boolean isOperator(String string) {
        return "+".equals(string) || "*".equals(string);
    }

    private void finish() {
        while (!stack.empty()) {
            addTokenToOutput(stack.pop());
        }
    }
}

I must admit that I have run too often through your ShuntingYard tutorial, Brett. I added a test case for parantheses after fixing the precedence case. While doing so I was thinking about whether 3 + 8 + 6 gets 3 8 6 + + or 3 8 + 6 +. Here’s me code:

InfixToPostfixConverterTest:

package com.om.example;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Collection;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class InfixToPostfixConverterTest {
    private final String infix;
    private final String expectedPostfix;

    @Parameters
    public static Collection<String[]> data() {
        ArrayList<String[]> values = new ArrayList<String[]>();

        addTestCase(values, null, "");
        addTestCase(values, "", "");
        addTestCase(values, "45", "45");
        addTestCase(values, "+", "+");
        addTestCase(values, "3 + 8", "3 8 +");
        addTestCase(values, "3 * 8", "3 8 *");
        addTestCase(values, "3 + 8 + 6", "3 8 6 + +");
        addTestCase(values, "3 * 8 + 6", "3 8 * 6 +"); // fixed
        addTestCase(values, "( 42 )", "42"); // failing

        return values;
    }

    private static void addTestCase(ArrayList<String[]> values, String infix,
            String expectedPostfix) {
        values.add(new String[] { infix, expectedPostfix });
    }

    public InfixToPostfixConverterTest(String infix, String expectedPostfix) {
        this.infix = infix;
        this.expectedPostfix = expectedPostfix;
    }

    @Test
    public void checkTranslation() {
        InfixToPostfixConverter converter = new InfixToPostfixConverter();
        String result = converter.translate(infix);

        assertEquals(expectedPostfix, result);
    }
}

InfixToPostfixConverter:

package com.om.example;

import java.util.Stack;

public class InfixToPostfixConverter {
    Stack<String> stack = new Stack<String>();
    StringBuilder output = new StringBuilder();

    public String translate(String string) {
        if (null == string)
            return "";

        String[] tokens = string.split(" ");
        buildOutputFromTokens(tokens);
        return output.toString().trim();
    }

    private void buildOutputFromTokens(String[] tokens) {
        for (String token : tokens) {
            handleToken(token);
        }
        finish();
    }

    private void handleToken(String token) {
        if (isOperator(token)) {
            if (!stack.empty() && precedenceOf(token) < precedenceOf(stack.peek())) {
                finish();
            }
            addTokenToStack(token);
        } else {
            addTokenToOutput(token);
        }
    }

    private int precedenceOf(String token) {
        if ("*".equals(token)) return 10;
        if ("+".equals(token)) return 1;
        return 0;
    }

    private void addTokenToStack(String token) {
        stack.push(token);
    }

    private void addTokenToOutput(String string) {
        output.append(string).append(" ");
    }

    private boolean isOperator(String string) {
        return "+".equals(string) || "*".equals(string);
    }

    private void finish() {
        while (!stack.empty()) {
            addTokenToOutput(stack.pop());
        }
    }
}

I think you’re right, Markus. When considering a non-commutative operation like minus: 3 8 – 6 – = 3 – 6 – 8 = -11 != 1 = 3 8 6 – - , so i changed the test you mentioned and added a new one for minus. Next, i added a test to check the bug introduced by the lines

if (!stack.empty() && precedenceOf(token) < precedenceOf(stack.peek())) {
                finish(); // empties the stack
            }

and fixed the code for both. Finally i implemented parenthesis handling by ignoring them and added a test to force the next poster to do a better job ;-)

@Parameters
    public static Collection<String[]> data() {
        ArrayList<String[]> values = new ArrayList<String[]>();

        addTestCase(values, null, "");
        addTestCase(values, "", "");
        addTestCase(values, "45", "45");
        addTestCase(values, "+", "+");
        addTestCase(values, "3 + 8", "3 8 +");
        addTestCase(values, "3 * 8", "3 8 *");
        addTestCase(values, "3 + 8 + 6", "3 8 + 6 +"); // changed
        addTestCase(values, "3 * 8 + 6", "3 8 * 6 +");
        addTestCase(values, "3 - 8 - 6", "3 8 - 6 -"); // new
        addTestCase(values, "3 + 8 * 6 * 2", "3 8 6 * 2 * +"); // new
        addTestCase(values, "( 42 )", "42"); // fixed
        addTestCase(values, "3 * ( 4 + 8 )", "3 4 8 + *"); // failing
        return values;
    }

And converter:

package com.om.example;

import java.util.Stack;

public class InfixToPostfixConverter {
    Stack<String> stack = new Stack<String>();
    StringBuilder output = new StringBuilder();

    public String translate(String string) {
        if (null == string)
            return "";

        String[] tokens = string.split(" ");
        buildOutputFromTokens(tokens);
        return output.toString().trim();
    }

    private void buildOutputFromTokens(String[] tokens) {
        for (String token : tokens) {
            handleToken(token);
        }
        finish();
    }

    private void handleToken(String token) {
        if (isOperator(token)) {
            handleOperator(token);
        } else if (isNumber(token)) {
            handleNumber(token);
        }
    }

    private void handleOperator(String token) {
        while (stackContainsOperatorOfHigherPrecedence(token)) {
            addTokenToOutput(stack.pop());
        }
        addTokenToStack(token);
    }

    private boolean stackContainsOperatorOfHigherPrecedence(String token) {
        if (stack.isEmpty()) {
            return false;
        }
        return precedenceOf(token) <= precedenceOf(stack.peek());
    }

    private boolean isNumber(String token) {
        return token.matches("\\d+");
    }

    private void handleNumber(String token) {
        addTokenToOutput(token);
    }

    private int precedenceOf(String token) {
        if ("*".equals(token))
            return 10;
        if ("+".equals(token))
            return 1;
        if ("-".equals(token))
            return 1;
        return 0;
    }

    private void addTokenToStack(String token) {
        stack.push(token);
    }

    private void addTokenToOutput(String string) {
        output.append(string).append(" ");
    }

    private boolean isOperator(String string) {
        return "+".equals(string) || "-".equals(string) || "*".equals(string);
    }

    private void finish() {
        while (!stack.empty()) {
            addTokenToOutput(stack.pop());
        }
    }
}

Looks like you guys are tackling it pretty well.

To the issue of whether operators of the same precedence are lazily or aggressively processed, consider for source material:

• the algorithm I pointed to
• describing a test that shows one way is better than another
• the tests define expected behavior, you write the tests, so by extension, you define it

on a calculator, for a series of additions, the thing that will drive one way versus the other is the size of the stack

My next step involves:

• introducing the helper classes PrecedenceChecker and TokenClassifier: InfixToPostfixConverter was getting too long and had too many responsibilities in my eyes. As I’m quite bad as finding good class names I’d be happy to have those renamed ;-)
• Handling parentheses to fix the failing test
• Adding a failing test using parentheses without separating spaces around them. I think we should address this issue before we dive deeper into the implementation as the spaces feel extremely artificial and therefore ugly.

Here the new and changed classes:

package com.om.example;

public class TokenClassifier {
   private static boolean is(String expected, String token) {
      return expected.equals(token);
   }
   public static boolean isLeftParenthesis(String token) {
      return is("(", token);
   }

   public static boolean isNumber(String token) {
      return token.matches("\\d+");
   }

   public static boolean isOperator(String token) {
      return is("+", token) || is("-", token) || is("*", token);
   }

   public static boolean isRightParenthesis(String token) {
      return is(")", token);
   }
}

package com.om.example;

public class PrecedenceChecker {
   private static int precedenceOf(String token) {
      if ("*".equals(token))
         return 10;
      if ("+".equals(token) || "-".equals(token))
         return 1;
      throw new RuntimeException("Token \"" + token + "\"'s precedence is not yet defined");
   }

   public static boolean hasLowerOrSamePrecedence(String operator1, String operator2) {
      return precedenceOf(operator1) <= precedenceOf(operator2);
   }
}

The new converter using these classes and handling parentheses:

package com.om.example;

import java.util.Stack;

public class InfixToPostfixConverter {
   Stack<String> stack = new Stack<String>();
   StringBuilder output = new StringBuilder();

   public String translate(String string) {
      if (null == string)
         return "";

      String[] tokens = string.split(" ");
      buildOutputFromTokens(tokens);
      return output.toString().trim();
   }

   private void buildOutputFromTokens(String[] tokens) {
      for (String token : tokens) {
         handleToken(token);
      }
      finish();
   }

   private void handleToken(String token) {
      if (TokenClassifier.isOperator(token)) {
         handleOperator(token);
      } else if (TokenClassifier.isLeftParenthesis(token)) {
         handleLeftParenthesis();
      } else if (TokenClassifier.isRightParenthesis(token)) {
         handleRightParenthesis();
      } else if (TokenClassifier.isNumber(token)) {
         handleNumber(token);
      }
   }

   private void handleLeftParenthesis() {
      addTokenToStack("(");
   }

   private void handleRightParenthesis() {
      while (!TokenClassifier.isLeftParenthesis(stack.peek())) {
         addTokenToOutput(stack.pop());
      }
      stack.pop();
   }

   private void handleOperator(String token) {
      while (stackContainsOperatorOfHigherPrecedence(token)) {
         addTokenToOutput(stack.pop());
      }
      addTokenToStack(token);
   }

   private boolean stackContainsOperatorOfHigherPrecedence(String operator) {
      if (stack.isEmpty()) {
         return false;
      }
      String topOfStack = stack.peek();
      if (TokenClassifier.isLeftParenthesis(topOfStack)) {
         return false;
      }
      return PrecedenceChecker.hasLowerOrSamePrecedence(operator, topOfStack);
   }

   private void handleNumber(String token) {
      addTokenToOutput(token);
   }

   private void addTokenToStack(String token) {
      stack.push(token);
   }

   private void addTokenToOutput(String string) {
      output.append(string).append(" ");
   }

   private void finish() {
      while (!stack.empty()) {
         addTokenToOutput(stack.pop());
      }
   }
}

The new test class with two tests for PrecedenceChecker:

package com.om.example;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class PrecedenceCheckerTest {
   private final String op1;
   private final String op2;
   private final Boolean op1HasLowerOrSamePrecedence;

   @Parameters
   public static Collection<Object[]> data() {
      ArrayList<Object[]> values = new ArrayList<Object[]>();

      addTestCase(values, "+", "+", true); // new test
      addTestCase(values, "*", "+", false); // new test
      return values;
   }

   private static void addTestCase(List<Object[]> values, String op1, String op2, boolean op1HasLowerOrSamePrecedence) {
      values.add(new Object[] { op1, op2, op1HasLowerOrSamePrecedence });
   }

   public PrecedenceCheckerTest(String op1, String op2, Boolean op1HasLowerOrSamePrecedence) {
      this.op1 = op1;
      this.op2 = op2;
      this.op1HasLowerOrSamePrecedence = op1HasLowerOrSamePrecedence;
   }

   @Test
   public void checkPrecedence() {
      assertEquals(op1HasLowerOrSamePrecedence, PrecedenceChecker.hasLowerOrSamePrecedence(op1, op2));
   }
}

And finally the fixed test and a new failing test for the converter:

   @Parameters
   public static Collection<String[]> data() {
      ArrayList<String[]> values = new ArrayList<String[]>();

      addTestCase(values, null, "");
      addTestCase(values, "", "");
      addTestCase(values, "45", "45");
      addTestCase(values, "+", "+");
      addTestCase(values, "3 + 8", "3 8 +");
      addTestCase(values, "3 * 8", "3 8 *");
      addTestCase(values, "3 + 8 + 6", "3 8 + 6 +");
      addTestCase(values, "3 * 8 + 6", "3 8 * 6 +");
      addTestCase(values, "3 - 8 - 6", "3 8 - 6 -");
      addTestCase(values, "3 + 8 * 6 * 2", "3 8 6 * 2 * +");
      addTestCase(values, "( 42 )", "42");
      addTestCase(values, "3 * ( 4 + 8 )", "3 4 8 + *"); // fixed
      addTestCase(values, "(42)", "42"); // failing
      return values;
   }

A final note: I feel more new unit tests would have been required before extracting the two new classes, meaning I shouldn’t have taken such a big step – but I was too impatient to refrain myself from doing it, so I guess I added to the technical debt of our little project – shame on me ;-).

In preparation for the “advanced parsing” you requested with the failing test, i did some refactorings trying to separate the construction of the token stream from it’s usage. During this task, i merged the two classes PrecedenceChecker and TokenClassifier into the class Token and changed InfixToPostfixConverter to use the Token type instead of Strings. Then i could extract a Tokenizer class responsible for the conversion from a String to an Iterable of Tokens.

However, after this about 30 minutes of refactorings, i now am unshure if this is too much overhead for this problem… So i stopped at this point (which means, the last test still fails) to ask you guys: What do you think? revert the changes i made and try some other way or continue from that point?

Here comes the code (omitting the unchanged InfixToPostfixConverterTest):

package com.om.example;

public class Token {
    private final String token;

    public Token(String token) {
        this.token = token;
    }

    public boolean hasLowerOrSamePrecedence(Token other) {
        return precedence() <= other.precedence();
    }

    private int precedence() {
        if ("*".equals(token))
            return 10;
        if ("+".equals(token) || "-".equals(token))
            return 1;
        throw new RuntimeException("Token \"" + token
                + "\"'s precedence is not yet defined");
    }

    public boolean isLeftParenthesis() {
        return is("(");
    }

    public boolean isNumber() {
        return token.matches("\\d+");
    }

    public boolean isOperator() {
        return is("+") || is("-") || is("*");
    }

    public boolean isRightParenthesis() {
        return is(")");
    }

    private boolean is(String expected) {
        return expected.equals(token);
    }

    @Override
    public String toString() {
        return token;
    }
}

package com.om.example;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class TokenPrecedenceTest {
    private final Token op1;
    private final Token op2;
    private final Boolean op1HasLowerOrSamePrecedence;

    @Parameters
    public static Collection<Object[]> data() {
        ArrayList<Object[]> values = new ArrayList<Object[]>();

        addTestCase(values, new Token("+"), new Token("+"), true); // new test
        addTestCase(values, new Token("*"), new Token("+"), false); // new test
        return values;
    }

    private static void addTestCase(List<Object[]> values, Token op1,
            Token op2, boolean op1HasLowerOrSamePrecedence) {
        values.add(new Object[] { op1, op2, op1HasLowerOrSamePrecedence });
    }

    public TokenPrecedenceTest(Token op1, Token op2,
            Boolean op1HasLowerOrSamePrecedence) {
        this.op1 = op1;
        this.op2 = op2;
        this.op1HasLowerOrSamePrecedence = op1HasLowerOrSamePrecedence;
    }

    @Test
    public void checkPrecedence() {
        assertEquals(op1HasLowerOrSamePrecedence, op1
                .hasLowerOrSamePrecedence(op2));
    }
}

public interface Tokenizer {
    public Iterable<Token> tokenize(String input);
}

public class SimpleTokenizer implements Tokenizer {

    public Iterable<Token> tokenize(String input) {
        String[] tokens = input.split(" ");
        List<Token> tokenList = new ArrayList<Token>(tokens.length);
        for (String token : tokens) {
            tokenList.add(new Token(token));
        }
        return tokenList;
    }
}

package com.om.example;

import java.util.Stack;

public class InfixToPostfixConverter {
    private final Stack<Token> stack = new Stack<Token>();
    private final StringBuilder output = new StringBuilder();
    private final Tokenizer tokenizer = new SimpleTokenizer();

    public String translate(String input) {
        if (null == input)
            return "";

        Iterable<Token> tokens = tokenizer.tokenize(input);
        buildOutputFromTokens(tokens);
        return output.toString().trim();
    }

    private void buildOutputFromTokens(Iterable<Token> tokens) {
        for (Token token : tokens) {
            handleToken(token);
        }
        finish();
    }

    private void handleToken(Token token) {
        if (token.isOperator()) {
            handleOperator(token);
        } else if (token.isLeftParenthesis()) {
            handleLeftParenthesis(token);
        } else if (token.isRightParenthesis()) {
            handleRightParenthesis();
        } else if (token.isNumber()) {
            handleNumber(token);
        }
    }

    private void handleLeftParenthesis(Token token) {
        stack.push(token);
    }

    private void handleRightParenthesis() {
        while (!stack.peek().isLeftParenthesis()) {
            addTokenToOutput(stack.pop());
        }
        stack.pop();
    }

    private void handleOperator(Token token) {
        while (stackContainsOperatorOfHigherPrecedence(token)) {
            addTokenToOutput(stack.pop());
        }
        stack.push(token);
    }

    private boolean stackContainsOperatorOfHigherPrecedence(Token operator) {
        if (stack.isEmpty()) {
            return false;
        }
        Token topOfStack = stack.peek();
        if (topOfStack.isLeftParenthesis()) {
            return false;
        }
        return operator.hasLowerOrSamePrecedence(topOfStack);
    }

    private void handleNumber(Token token) {
        addTokenToOutput(token);
    }

    private void addTokenToOutput(Token token) {
        output.append(token.toString()).append(" ");
    }

    private void finish() {
        while (!stack.empty()) {
            addTokenToOutput(stack.pop());
        }
    }
}

Thomas: For my part I’m happy with your refactorings – except for the Tokenizer interface which doesn’t seem necessary.

I’ve already prepared the next step (with 6 new tests: 5 new ones and a failing one – twice as many as defined to “compensate” for the missing tests in your step) but would like to wait for Brett’s opinion about our “cheating” before going any further.

ErikFK

How about this for an updated rule:

• If you are adding tests to verify a refactoring (change in structure, no new behavior), then it’s cool.

Sound reasonable?

Here come 5 simple tests for Thomas’ Token class:

package com.om.example;

import static org.junit.Assert.assertTrue;

import org.junit.Test;

public class TokenTypeTest {
   @Test
   public void testIsLeftParenthesis() {
      assertTrue(new Token("(").isLeftParenthesis()); // new
   }

   @Test
   public void testIsNumber() {
      assertTrue(new Token("123").isNumber()); // new
   }

   @Test
   public void testPlusIsOperator() {
      assertTrue(new Token("+").isOperator()); // new
   }

   @Test
   public void testMinusIsOperator() {
      assertTrue(new Token("-").isOperator()); // new
   }

   @Test
   public void testIsRightParenthesis() {
      assertTrue(new Token(")").isRightParenthesis()); // new
   }
}

Here are the tests for the converter (one fixed, one new that fails):

   @Parameters
   public static Collection<String[]> data() {
      ArrayList<String[]> values = new ArrayList<String[]>();

      addTestCase(values, null, "");
      addTestCase(values, "", "");
      addTestCase(values, "45", "45");
      addTestCase(values, "+", "+");
      addTestCase(values, "3 + 8", "3 8 +");
      addTestCase(values, "3 * 8", "3 8 *");
      addTestCase(values, "3 + 8 + 6", "3 8 + 6 +");
      addTestCase(values, "3 * 8 + 6", "3 8 * 6 +");
      addTestCase(values, "3 - 8 - 6", "3 8 - 6 -");
      addTestCase(values, "3 + 8 * 6 * 2", "3 8 6 * 2 * +");
      addTestCase(values, "( 42 )", "42");
      addTestCase(values, "3 * ( 4 + 8 )", "3 4 8 + *");
      addTestCase(values, "(42)", "42"); // fixed
      addTestCase(values, "(3 + 4) / (9 + 7)", "3 4 + 9 7 + /"); // failing
      return values;
   }

The code change in the Tokenizer (which is now a class and replaces SimpleTokenizer):

package com.om.example;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Tokenizer {

   public Iterable<Token> tokenize(String input) {
      String[] tokens = input.split(" ");
      List<Token> tokenList = new ArrayList<Token>(tokens.length);
      for (String tokenCandidate : tokens) {
         StringTokenizer tokenizer = new StringTokenizer(tokenCandidate, "()", true);
         while (tokenizer.hasMoreTokens()) {
            tokenList.add(new Token(tokenizer.nextToken()));
         }
      }
      return tokenList;
   }
}

and in the converter itself (only the creation of the Tokenizer was modified):

package com.om.example;

import java.util.Stack;

public class InfixToPostfixConverter {
   private final Stack<Token> stack = new Stack<Token>();
   private final StringBuilder output = new StringBuilder();
   private final Tokenizer tokenizer = new Tokenizer();

   public String translate(String input) {
      if (null == input)
         return "";

      Iterable<Token> tokens = tokenizer.tokenize(input);
      buildOutputFromTokens(tokens);
      return output.toString().trim();
   }

   private void buildOutputFromTokens(Iterable<Token> tokens) {
      for (Token token : tokens) {
         handleToken(token);
      }
      finish();
   }

   private void handleToken(Token token) {
      if (token.isOperator()) {
         handleOperator(token);
      } else if (token.isLeftParenthesis()) {
         handleLeftParenthesis(token);
      } else if (token.isRightParenthesis()) {
         handleRightParenthesis();
      } else if (token.isNumber()) {
         handleNumber(token);
      }
   }

   private void handleLeftParenthesis(Token token) {
      stack.push(token);
   }

   private void handleRightParenthesis() {
      while (!stack.peek().isLeftParenthesis()) {
         addTokenToOutput(stack.pop());
      }
      stack.pop();
   }

   private void handleOperator(Token token) {
      while (stackContainsOperatorOfHigherPrecedence(token)) {
         addTokenToOutput(stack.pop());
      }
      stack.push(token);
   }

   private boolean stackContainsOperatorOfHigherPrecedence(Token operator) {
      if (stack.isEmpty()) {
         return false;
      }
      Token topOfStack = stack.peek();
      if (topOfStack.isLeftParenthesis()) {
         return false;
      }
      return operator.hasLowerOrSamePrecedence(topOfStack);
   }

   private void handleNumber(Token token) {
      addTokenToOutput(token);
   }

   private void addTokenToOutput(Token token) {
      output.append(token.toString()).append(" ");
   }

   private void finish() {
      while (!stack.empty()) {
         addTokenToOutput(stack.pop());
      }
   }
}

Ok, Tests first:

    @Parameters
    public static Collection<String[]> data() {
        ArrayList<String[]> values = new ArrayList<String[]>();

        addTestCase(values, null, "");
        addTestCase(values, "", "");
        addTestCase(values, "45", "45");
        addTestCase(values, "+", "+");
        addTestCase(values, "3 + 8", "3 8 +");
        addTestCase(values, "3 * 8", "3 8 *");
        addTestCase(values, "3 + 8 + 6", "3 8 + 6 +");
        addTestCase(values, "3 * 8 + 6", "3 8 * 6 +");
        addTestCase(values, "3 - 8 - 6", "3 8 - 6 -");
        addTestCase(values, "3 + 8 * 6 * 2", "3 8 6 * 2 * +");
        addTestCase(values, "( 42 )", "42");
        addTestCase(values, "3 * ( 4 + 8 )", "3 4 8 + *");
        addTestCase(values, "(42)", "42");
        addTestCase(values, "(3 + 4) / (9 + 7)", "3 4 + 9 7 + /");// fixed
        addTestCase(values, "1 ^ 2 ^ 3", "1 2 3 ^ ^"); // new
        addTestCase(values, "1 ^ 2 * 3 ^ 4", "1 2 ^ 3 4 ^ *"); // new
        addTestCase(values, "3+4", "3 4 +"); // fails
        return values;
    }

And production code (Ohter classes are uncanged):

package com.om.example;

public class Token {
    private final String token;
    private enum TokenType {
        NUMBER, OPERATOR, LEFT_PARENTHESIS, RIGHT_PERENTHESIS;
    }
    private TokenType type;
    private boolean leftAssociative = false;
    private int precedence = -1;

    public Token(String token) {
        this.token = token;
        determineMetaInfo();
    }

    private void determineMetaInfo() {
        if (is("+") || is("-")) {
            type = TokenType.OPERATOR;
            leftAssociative = true;
            precedence = 1;
        } else if (is("*") || is("/")) {
            type = TokenType.OPERATOR;
            leftAssociative = true;
            precedence = 10;
        } else if (is("^")) {
            type = TokenType.OPERATOR;
            leftAssociative = false;
            precedence = 20;
        } else if (is("(")) {
            type = TokenType.LEFT_PARENTHESIS;
        } else if (is(")")) {
            type = TokenType.RIGHT_PERENTHESIS;
        } else if (token.matches("\\d+")) {
            type = TokenType.NUMBER;
        } else {
            throw new IllegalArgumentException("Unknown token " + token);
        }
    }

    public boolean hasLowerOrEqualPrecedence(Token other) {
        if (isLeftAssociative()) {
            return precedence() <= other.precedence();
        } else {
            return false;
        }
    }

    public boolean isLeftAssociative() {
        return leftAssociative;
    }

    public int precedence() {
        return precedence;
    }

    public boolean isLeftParenthesis() {
        return TokenType.LEFT_PARENTHESIS == type;
    }

    public boolean isNumber() {
        return TokenType.NUMBER == type;
    }

    public boolean isOperator() {
        return TokenType.OPERATOR == type;
    }

    public boolean isRightParenthesis() {
        return TokenType.RIGHT_PERENTHESIS == type;
    }

    private boolean is(String expected) {
        return expected.equals(token);
    }

    public String getToken() {
        return token;
    }
}

Some remarks:

• You might note the changes to Token, that introduced quite a lot of ugliness to this class. In my opinion, this shows that there is a difference between numbers and all other kinds of tokens (tokens which may be pushed to the stack need other methods, etc). When considering this together with the method handleToken() from InfixToPostfixConverter with it’s repeated if(isBla(token)) handleBla(token), i think it’s quite clear, that here some kind of type structure for tokens tries to emerge. Unfortunately i could not think of a good name for the type of tokens that can live on the stack, so i did not refactor more.
• There is a problem with Token.hasLowerOrEqualPrecedence(Token): the last line was precedence() < other.precedence(), but because currently there is no other right-associative operator, this always evaluates to false. If we only could find a better name…
• There seems to be some duplication between the tokenizer and the token class. Both do string-parsing which i think will be even more obvious after implementing the next test.
• I’m not sure what to think about the two Token-Tests: Token is the biggest class in the project, so i feel there should be tests for it. On the other hand, neither of the two tests increases code coverage by a single line. Both tests seem rather incomplete in that they cover only approx. 78,5% of Token.[1] Ok, we could add more tests to increase coverage and to fully specify Token’s behavior, but than again, if we make a mistake in Token it very likely breaks one of the tests for InfixToPostfixConverter, too. So here seems to be a tradeof between the documentation aspect of a unit-test and it’s … well, testing aspect? Maybe someone with more TDD experience could comment on this one…

However, sorry for this rather longish post and happy coding for whoever picks up ;-)

1 Actually, emma reports only ~75% due to the uncovered instructions generated by the compiler for the enumeration type…

I did very little new for this step: correcting the failing test and adding similar tests for other operators – leaving one failing. The new tests are therefore:

   @Parameters
   public static Collection<String[]> data() {
       ArrayList<String[]> values = new ArrayList<String[]>();

       addTestCase(values, null, "");
       addTestCase(values, "", "");
       addTestCase(values, "45", "45");
       addTestCase(values, "+", "+");
       addTestCase(values, "3 + 8", "3 8 +");
       addTestCase(values, "3 * 8", "3 8 *");
       addTestCase(values, "3 + 8 + 6", "3 8 + 6 +");
       addTestCase(values, "3 * 8 + 6", "3 8 * 6 +");
       addTestCase(values, "3 - 8 - 6", "3 8 - 6 -");
       addTestCase(values, "3 + 8 * 6 * 2", "3 8 6 * 2 * +");
       addTestCase(values, "( 42 )", "42");
       addTestCase(values, "3 * ( 4 + 8 )", "3 4 8 + *");
       addTestCase(values, "(42)", "42");
       addTestCase(values, "(3 + 4) / (9 + 7)", "3 4 + 9 7 + /");
       addTestCase(values, "1 ^ 2 ^ 3", "1 2 3 ^ ^");
       addTestCase(values, "1 ^ 2 * 3 ^ 4", "1 2 ^ 3 4 ^ *");
       addTestCase(values, "3+4", "3 4 +"); // fixed
       addTestCase(values, "3-4", "3 4 -"); // new
       addTestCase(values, "3*4", "3 4 *"); // new
       addTestCase(values, "3/4", "3 4 /"); // failing
       return values;
   }

I extended the tokenizer class as follows:

package com.om.example;

import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Tokenizer {

   public Iterable<Token> tokenize(String input) {
      String[] tokens = input.split(" ");
      List<Token> tokenList = new ArrayList<Token>(tokens.length);
      for (String tokenCandidate : tokens) {
         StringTokenizer tokenizer = new StringTokenizer(tokenCandidate, "()+-*", true); // modified
         while (tokenizer.hasMoreTokens()) {
            tokenList.add(new Token(tokenizer.nextToken()));
         }
      }
      return tokenList;
   }
}

I also noticed that a few changes where missing in the classes Thomas provided in the previous step:

• hasLowerOrSamePrecedence was renamed to hasLowerOrEqualPrecedence but the code modifications in other classes than Token were not provided.
• toString needs to be implemented in Token to return the token field – as the tests otherwise fail.

As all these are only minor problems that are obvious to correct I’m not providing the modified classes.

I feel that we (or at least I) have bigger issues with the challenge itself. For example: Thomas’ points in his latest post are interesting and worth discussing – but I don’t think it would really make sense to try to address them here, as answers would require a few more blog entries – and we want to write a program to solve a problem here, don’t we? ;-).

What I want to say is the following: I totally miss the interaction with my peer. We don’t have a common strategy – how could we as we don’t talk about it? and writing about it is just not the same… – and therefore I find it hard to stay focused and motivated. I discover his move with the next post and can partially “read his thoughts” from the code, but the most important part is missing. As a consequence I miss the feeling of progress in solving the task, and the positive feedback loop of “real” pairing. It probably requires a quite specific state of mind to TDD/pair like this – or maybe it’s simply not possible.

To address (a very small part of) the issues Thomas is raising: I tend to think that we’ve taken too big steps every now and then (especially when introducing new classes). With the same amount of code we have now, I’d have written far more unit tests than we currently have.

Hi all,

I have been following this thread for the last week. Currently I am at university and have been looking for something which I could use to help me develop my OOP and TDD skills. This has been of great value to me. Anyway, as I say i have only been follwoing along so far but today I decided to try my own solution. It perhaps differs too much from the last solution. Feedback would be much appreciated – specifically if there are any big weaknesses in my design over the previous solution.

New tests:

   @Parameters
   public static Collection<String[]> data() {
       ArrayList<String[]> values = new ArrayList<String[]>();

       addTestCase(values, null, "");
       addTestCase(values, "", "");
       addTestCase(values, "45", "45");
       addTestCase(values, "+", "+");
       addTestCase(values, "3 + 8", "3 8 +");
       addTestCase(values, "3 * 8", "3 8 *");
       addTestCase(values, "3 + 8 + 6", "3 8 + 6 +");
       addTestCase(values, "3 * 8 + 6", "3 8 * 6 +");
       addTestCase(values, "3 - 8 - 6", "3 8 - 6 -");
       addTestCase(values, "3 + 8 * 6 * 2", "3 8 6 * 2 * +");
       addTestCase(values, "( 42 )", "42");
       addTestCase(values, "3 * ( 4 + 8 )", "3 4 8 + *");
       addTestCase(values, "(42)", "42");
       addTestCase(values, "(3 + 4) / (9 + 7)", "3 4 + 9 7 + /");
       addTestCase(values, "1 ^ 2 ^ 3", "1 2 3 ^ ^");
       addTestCase(values, "1 ^ 2 * 3 ^ 4", "1 2 ^ 3 4 ^ *");
       addTestCase(values, "3+4", "3 4 +");
       addTestCase(values, "3-4", "3 4 -");
       addTestCase(values, "3*4", "3 4 *");
       addTestCase(values, "3/4", "3 4 /"); // fixed
       addTestCase(values, "(3+(4-5))*6", "3 4 5 - + 6 *"); // new
       addTestCase(values, "3+4*2/(1-5)^2^3", "3 4 2 * 1 5 - 2 3 ^ ^ / +"); // new
       addTestCase(values, "f(3)", "3 f"); // failing
       return values;
   }

Tokenizer

package com.sam.converter;

import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Tokenizer {

   public String[] tokenize(String input) {
      String[] tokens = input.split(" ");
      List<String> tokenList = new LinkedList<String>();
      for (String tokenCandidate : tokens) {
         StringTokenizer tokenizer = new StringTokenizer(tokenCandidate, "(+-*/^)", true);
         while (tokenizer.hasMoreTokens()) {
            tokenList.add(tokenizer.nextToken());
         }
      }
      return (String[])tokenList.toArray(new String[0]);
   }
}

Operator:

package com.sam.converter;

import java.util.HashMap;
import java.util.Map;

public class Operator
{
    private Map<String, Integer> operatorPrecedence = new HashMap<String, Integer>();

    public Operator()
    {
        initializeOperators();
    }

    private void initializeOperators()
    {
        operatorPrecedence.put("+", 1);
        operatorPrecedence.put("-", 1);
        operatorPrecedence.put("*", 10);
        operatorPrecedence.put("/", 10);
        operatorPrecedence.put("^", 100);
    }

    public boolean isOperator(String token)
    {
        return operatorPrecedence.containsKey(token);
    }

    public boolean isPrecedenceGreater(String opA, String opB)
    {
        if(opA.equals("^") && opB.equals("^"))
            return true;
        return (operatorPrecedence.get(opA) - operatorPrecedence.get(opB) > 0);
    }
}

Converter:

package com.sam.converter;

import java.util.Stack;

public class InfixToPostfixConverter
{
    private String postFixExpression = "";
    private Operator operator = new Operator();
    private Stack<String> operatorStack = new Stack<String>();

    public String translate(String givenInfixExpression)
    {
        if( null == givenInfixExpression )
            return "";

        Tokenizer tokenizer = new Tokenizer();
        String[] tokens = tokenizer.tokenize(givenInfixExpression);
        buildPostfixFromTokens(tokens);
        return postFixExpression.trim();
    }

    private void buildPostfixFromTokens(String[] tokens)
    {
        for( String token : tokens )
        {
            handleToken(token);
        }
        finishBuildingPostfix();
    }

    private void handleToken(String token)
    {
        if( isNumber(token) )
        {
            appendToPostfixExpression(token);
        }
        else if( isLeftParenthesis(token) )
        {
            handleLeftParenthesis();
        }
        else if( isRightParenthesis(token) )
        {
            handleRightParenthesis();
        }
        else if( isOperator(token) )
        {
            handleOperator(token);
        }
    }

    private boolean isLeftParenthesis(String token)
    {
        return token.equals("(");
    }

    private void handleLeftParenthesis()
    {
        addToStack("(");
    }

    private boolean isRightParenthesis(String token)
    {
        return token.equals(")");
    }

    private void handleRightParenthesis()
    {
        String testToken = operatorStack.pop();
        while( !isLeftParenthesis(testToken) )
        {
            appendToPostfixExpression(testToken);
            testToken = operatorStack.pop();
        }
    }

    private void handleOperator(String token)
    {
        if( !operatorStack.isEmpty()
                && !isLeftParenthesis(operatorStack.peek())
                && !tokenPrecedenceIsGreaterThanStack(token) )
        {
            appendToPostfixExpression(operatorStack.pop());
        }
        addToStack(token);
    }

    private boolean isNumber(String token)
    {
        return token.matches("\\d+");
    }

    private void appendToPostfixExpression(String token)
    {
        postFixExpression += token + " ";
    }

    private boolean isOperator(String token)
    {
        return operator.isOperator(token);
    }

    private void addToStack(String token)
    {
        operatorStack.push(token);
    }

    private void finishBuildingPostfix()
    {
        while( !operatorStack.isEmpty() )
        {
            appendToPostfixExpression(operatorStack.pop());
        }
    }

    private boolean tokenPrecedenceIsGreaterThanStack(String token)
    {
        return operator.isPrecedenceGreater(token, operatorStack.peek());
    }

}

I wanted to create another class for the token handling code in the converter class but couldn’t think of a good way to do it. As I say feedback would be much appreciated.

?? ? ????

I dont even remember how i reached your site but it doesnt matter, cause i’m so happy i found it, it really made me think, keep up the good work.

she is not the happier

Great news! White iphone 4 Conversion Kit is now avaible! With hottest White color outlook can certainly catch your eyes and heart!

Haile Electric Industrial Co. Ltd. is the leading manufacturer and exporter of cold room,axial fan,condensing unit,centrifugal fan,shaded pole motor and refrigeration products in China.

Code is useful.

internette görüntülü olarak okey oyunu oyna, gerçek kisilerle tanis, turnuva heyecanini yasa.

????

??

Ltd. is the leading manufacturer and exporter of cold room,axial fan,condensing unit,centrifugal fan,shaded pole motor and refrigeration products in China.high quality headphones new design headphones

Designer fashion women replica shoulder bag from China for sale on line

Create the ultimate Home Theater Projector with a digital projector from InFocus in vvme. Then came the announcement on July 28-the industry’s first LCD-based 3D 1080p lcd projector was on its way. If you want an LCD projector for your beautiful LCD Projector Screen, you should take a look at the choices available at Go vvme. Shop and compare InFocus Meeting Room Projector and find supplies for your InFocus.

iPhone MP3 to Ringtone Maker can convert MP3 to iPhone/iPhone OS 3.0/3.1 Ringtone, even convert any video/audio to iphone ringtone.

What is next? We also want to know. It is really a good example that most of the programmer should think about this. If we want to do much better for the code. I should understand it. right? You are very good at this and show us good coding idea.

MANYADEAL.COM is professional for Ballast for HID? The kit comes complete with a Electronic HID Ballast, and it is Plug-n-Play. All necessary hardware for installation is included. Combined HID Slim Ballast and starter unit for better performance and easy installation for 55W Ballast.

Remote Ping-Pong Challenge: Your turn, who’s next? (Java) 30 good post101

Remote Ping-Pong Challenge: Your turn, who’s next? (Java) 31 hoo,good article!!I like the post!147

Our life is modifying promptly with the ralph lauren sale of the society. The modification is mostly come seal the fashionable goods according to the modification in fashion Pas Cher Women’s Ralph Lauren sale Vuitton Sacs. Well, otherwise, it Men’s Ralph Lauren shirts differs in many aspects due to ones gravy style. The gravy style broadly articulating demonstrates the personality and individuality of people.