Port of schuchert.wikispaces.com


Katas.ShuntingYardAlgorithm

Katas.ShuntingYardAlgorithm

Background

The Shunting Yard Algorithm, written by Dijkstra, converts an infix expression into a post-fix expression. For example, the expression:

\(3 + 4\) becomes \(3\;4\;+\)

Precedence and Associativity

What makes this difficult is that operators, generally, have some notion of precedence in most languages. For example, multiplication typically has a higher precedence than addition. So the expression 3 + 5 * 6 is 33 (multiplication happens first) rather than 40.

There’s also the issue of associativity. For example, 3 + 4 + 5 happens left-to-right, or it is left-associative. On the other hand, assignment is right-associative. For example, a = b = c = 4, all values receive the value 4 because c = 4 is performed first, while b is assigned to theresult of the assignment of c, which is 4.

For the purposes of this exercise, consider these precedence rules from C++.

Note: This kata is in flux, I’ve added the link to the C++ operators but the examples use ^ as “to the power of” rather than bitwise negate. Follow the examples until I update the list of tests.

Examples

Here is a series of examples with expected results:


title: Katas.ShuntingYardAlgorithm.examples —

Example Infix Expression Expected Postfix Result Notes
empty string empty string A good place to start, you’ll create the basic translator class and get a value back.
null empty string Make sure you handle one error case, a null string, by returning a reasonable default value of an empty string.
45 45 Make sure you can handle a simple, literal number. This test may work out of the box, if not, it should be simple to get it to work.
+ + Make sure you can handle a simple operator. This test will probably work out of the box after getting the previous test to pass. Later on, this test represents a error case of sorts since there are no operands for this operator.
3 + 8 3 8 + Your first “real” test, can you perform some basic translation?
2 + 9 - 6 2 9 + 6 - You probably hard-coded the first example, this makes you do a little more work. And it adds a second operator to boot.
2 + 9 * 6 2 9 6 * + This is the first example where operator precedence makes a difference.
2 * 10 ^ 6 2 10 6 ^ * The ^ (raised to the power of) operator is typically a right-associative operator.
2 ^ 3 ^ 4 2 3 4 ^ ^ This was a bit of a dud test I added. It immeidately passed. Might consider leaving this one out.
a ^ 3 a 3 ^ I want my expression evaluator to handle symbols as well as literal numbers. This example forces that behavior.
(3 + 4) 3 4 + Handle ()’s. First, simply remove them.
(3 + 4) * 5 3 4 + 5 * Now make sure that ()s change the order of evaluation since + typically happensafter *.
(3+(4-5))*6 3 4 5 - + 6 * A more complex example to verify that the solution is general. Also notice that the spaces between separate tokens has been removed. You’ll need to handle both with and without spaces.
f(3) 3 f This is an example of a function call. Notice, this forces “look ahead” in your algorithm because you do not know if something is a function or a variable unless you look ahead to the next token.
f(g(4)) 4 g f Is your solution general enough to handle nested functions?
f(3, 4, 19) 3 4 19 f Can your solution handle multiple parameters to a function call?
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 3 4 2 * 1 5 - 2 3 ^ ^ / + This example is taken from the Shunting Yard Algorithm writeup on wikipedia.
f(4+5,1+a^2,(8+b)*10) 4 5 + 1 a 2 ^ + 8 b + 10 * f I added this some time later. It incorporates just about everything already done and it specifically pushes handling multiple parameters to a function correctly. I expected this to take some time, but it really did not take much (a few minutes).

One Approach

The examples above are taken from a recent (June 2009) personal walk-through of the algorithm. I was surprised by my results and the ease with which I was able to implement the algorithm.

I recommend the following approach when trying this problem:

One note, when I worked on this, I used Java with JUnit 4’s parameterized tests. Here’s what the final test file looks like:

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, "2 + 9 - 6", "2 9 + 6 -");
      addTestCase(values, "2 + 9 * 6", "2 9 6 * +");
      addTestCase(values, "2 * 10 ^ 6", "2 10 6 ^ *");
      addTestCase(values, "2 ^ 3 ^ 4", "2 3 4 ^ ^");
      addTestCase(values, "a ^ 3", "a 3 ^");
      addTestCase(values, "(3 + 4)", "3 4 +");
      addTestCase(values, "(3 + 4) * 5", "3 4 + 5 *");
      addTestCase(values, "(3+(4-5))*6", "3 4 5 - + 6 *");
      addTestCase(values, "f(3)", "3 f");
      addTestCase(values, "f(g(4))", "4 g f");
      addTestCase(values, "f(3, 4, 19)", "3 4 19 f");
      addTestCase(values, "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3", "3 4 2 * 1 5 - 2 3 ^ ^ / +");
      addTestCase(values, "3+4*2/(1-5)^2^3", "3 4 2 * 1 5 - 2 3 ^ ^ / +");
      addTestCase(values, "f(4+5,1+a^2,(8+b)*10)","4 5 + 1 a 2 ^ + 8 b + 10 * f");

      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);
   }
}

This worked OK, but occasionally I wanted to run just one test. This does not seem to be supported, so I had to comment out various lines in thedata() method. The next time I work on this, I’ll probably use individual test methods.

Getting Started

Here is one possible start to this problem (with the first three tests added and passing):

The Test

Note: Occasionally I experiment with different ways of writing unit tests with JUnit. This is one such example where I attempt to simulate the domain specific language used by cucumber.

package com.om.shuntingyardalgorithm;

import static junit.framework.Assert.assertEquals;

import org.junit.Test;

public class PostfixToInfixTranslatorTest {
   private PostfixToInfixTranslator translator = new PostfixToInfixTranslator();
   private String givenInfixExpression;
   private String actualPostfixResult;

   private void given(String infixExpression) {
      this.givenInfixExpression = infixExpression;
   }

   private void whenTranslating() {
      actualPostfixResult = translator.convert(givenInfixExpression);
   }

   private void thenTheResultShouldBe(String expectedPostfixResult) {
      assertEquals(expectedPostfixResult, actualPostfixResult);
   }

   @Test
   public void itShouldReturnAnEmptyStringWhenGivenAnEmptyString() {
      given("");
      whenTranslating();
      thenTheResultShouldBe("");
   }

   @Test
   public void itShouldReturnAnEmptyStringWhenGivenNull() {
      given(null);
      whenTranslating();
      thenTheResultShouldBe("");
   }

   @Test
   public void itShouldReturnLiteralNumberWhenGivenLiteralNumber() {
      given("45");
      whenTranslating();
      thenTheResultShouldBe("45");
   }
}

The Production Code

And here’s the results after the first three tests:

package com.om.shuntingyardalgorithm;

public class PostfixToInfixTranslator {
   public String convert(String givenInfixExpression) {
      if (givenInfixExpression == null)
         return "";

      return givenInfixExpression;
   }
}

Hints

I take the approach of splitting the expression into individual tokens and then processing them one by one. To do this, I use regular expressions and to format the output, I use String.format(…). Here are a few hints along those lines:

What We Accomplished

Here’s a zip of the source files we created during the dojo: dojo.zip

Here’s a version I’ve worked on a bit more: ShuntingYardAlgorithm.zip


Comments

" Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.