Groovy Algorithms: Shunting Yard

Groovy's sugary syntax makes coding algorithms -- dare I say it -- fun.  The shunting yard algorithm, invented by Dutch computer scientist Edsger Dijkstra, is used to parse mathematical expressions.  You might have picked up on this already, but computers and people think differently.  We commonly use infix notation to write mathematical expressions.  It is what you learned in school.  For example: "3 * (2 + 3)".  Makes sense to you, but it is inefficient for a computer to process.  Things like operator precedent and nested parenthesis make infix rather messy.  A more efficient format is postfix or Reverse Polish notation.  In postfix, the operands are listed first, and then the operator.  For example: "2 3 + 3 *".  This eliminates the need for parenthesis, and allows you to calculate the expression using just a single stack to hold operands and intermediate results.  Why didn't we learn this in school?  I don't know.  Why aren't we using the metric system yet?  Why doesn't Siri on my iPhone understand anything I say even though it works great in the commericals?  Life's little mysteries.  Back to shunting yard.  Here is my Groovy implementation of it.

The main class is ExpressionSolver.  The computePostfix method (line 7) shows how easy it is to calculate a postfix expression with a single stack and single pass through the tokens in the expression.  It delegates the work of converting from infix to postfix to the appropriately named ShuntingYardAlgorithm class (line 21).

1:  package org.jadcon.expression  
2:  def infixExpression = '5.5 + ((6 + 2) * 4) - -3 * 1.5'  
3:  def postfixExpression = '5.5 6 2 + 4 * -3 1.5 * - +'  
4:  def expectedResult = 42  
5:  assert computePostfix(postfixExpression) == expectedResult   
6:  assert computeInfix(infixExpression) == expectedResult  
7:  def computePostfix(postfixExpression) {  
8:       def stack = []  
9:       postfixExpression.split().each { token ->  
10:            if (token.isNumber()) {  
11:                 stack.add(token)  
12:            } else {  
13:                 def b = stack.pop().toBigDecimal()  
14:                 def a = stack.pop().toBigDecimal()  
15:                 stack.add(Operator.valueFrom(token).calculate(a, b))  
16:            }  
17:       }  
18:       stack.pop()  
19:  }  
20:  def computeInfix(infixExpression) {  
21:       computePostfix(ShuntingYardAlgorithm.convertToPostfix(infixExpression))  
22:  }  

The ShuntingYardAlgorithm class coverts an expression from infix to postfix.  It requires two stacks: an output stack and a working stack.  The main logic is in the processToken method (line 14) which loops through each token.  Operands go directly on the output stack.  Operators and parenthesis are placed on the working stack to get correctly ordered when placed on the output stack.

1:  package org.jadcon.expression  
2:  class ShuntingYardAlgorithm {  
3:       def static convertToPostfix(infixExpression) {  
4:            def output = []  
5:            def stack = []  
6:            evenSpaceAroundParens(infixExpression).split().each { token ->  
7:                 processToken(token, output, stack)  
8:            }  
9:            while (!stack.isEmpty()) {  
10:                 output.add stack.pop()  
11:            }  
12:            output.join(' ')  
13:       }  
14:       def static processToken(token, output, stack) {  
15:            if (token.isNumber()) {  
16:                 output.add token  
17:            } else {  
18:                 switch (token) {                           
19:                      case "(":  
20:                           stack.add token  
21:                           break  
22:                      case ")":  
23:                           while (stack.last() != "(") {  
24:                                output.add stack.pop()  
25:                           }  
26:                           stack.pop() // pop the left paren and ignore it  
27:                           break  
28:                      default:  
29:                           def operator = Operator.valueFrom(token)  
30:                           while (!stack.isEmpty() &&  
31:                                     stack.last().is(Operator) &&  
32:                                     operator <= stack.last()) {  
33:                                output.add stack.pop()  
34:                           }  
35:                           stack.add operator  
36:                 }  
37:            }  
38:       }  
39:       def static evenSpaceAroundParens(string) {  
40:            def output = []  
41:            string.each { letter ->  
42:                 if (!output.isEmpty() && letter != ' ') {  
43:                      def last = output.last()  
44:                      if (isParen(letter) && last != ' ') {  
45:                           output.add ' '  
46:                      } else if (isParen(last)) {   
47:                           output.add ' '  
48:                      }  
49:                 }  
50:                 output.add letter  
51:            }  
52:            output.join()  
53:       }  
54:       def static isParen(letter) {  
55:            letter == '(' || letter == ')'  
56:       }  
57:  }  

The final class is Operator which is an enumeration of operators.  Groovy makes this code pretty tight using closures.  Even threw in a spaceship comparison operator for good measure (line 24).

1:  package org.jadcon.expression  
2:  enum Operator {  
3:       PLUS('+', 0, { a, b -> a + b }),   
4:       MINUS('-', 0, { a, b -> a - b }),   
5:       MULTIPLY('*', 1, { a, b -> a * b }),   
6:       DIVIDE('/', 1, { a, b -> a / b })  
7:       String value  
8:       int precedence  
9:       Closure calculate  
10:       private Operator(String value, int precedence, Closure calculate) {  
11:            this.value = value  
12:            this.precedence = precedence  
13:            this.calculate = calculate  
14:       }  
15:       def static valueFrom(string) {  
16:            for (operator in Operator.values()) {  
17:                 if (operator.value == string) {  
18:                      return operator  
19:                 }  
20:            }  
21:            throw new IllegalArgumentException("invalid operator ${string}")  
22:       }  
23:       def int compareTo(other) {  
24:            precedence <=> other.precedence       
25:       }  
26:       def String toString() {  
27:            value  
28:       }  
29:  }  

Coding the shunting yard algorithm was fun exercise in Groovyness.