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 commercials? 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).
package org.jadcon.expression
def infixExpression = '5.5 + ((6 + 2) * 4) - -3 * 1.5'
def postfixExpression = '5.5 6 2 + 4 * -3 1.5 * - +'
def expectedResult = 42
assert computePostfix(postfixExpression) == expectedResult
assert computeInfix(infixExpression) == expectedResult
def computePostfix(postfixExpression) {
def stack = []
postfixExpression.split().each { token ->
if (token.isNumber()) {
stack.add(token)
} else {
def b = stack.pop().toBigDecimal()
def a = stack.pop().toBigDecimal()
stack.add(Operator.valueFrom(token).calculate(a, b))
}
}
stack.pop()
}
def computeInfix(infixExpression) {
computePostfix(ShuntingYardAlgorithm.convertToPostfix(infixExpression))
}
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.
package org.jadcon.expression
class ShuntingYardAlgorithm {
def static convertToPostfix(infixExpression) {
def output = []
def stack = []
evenSpaceAroundParens(infixExpression).split().each { token ->
processToken(token, output, stack)
}
while (!stack.isEmpty()) {
output.add stack.pop()
}
output.join(' ')
}
def static processToken(token, output, stack) {
if (token.isNumber()) {
output.add token
} else {
switch (token) {
case "(":
stack.add token
break
case ")":
while (stack.last() != "(") {
output.add stack.pop()
}
stack.pop() // pop the left paren and ignore it
break
default:
def operator = Operator.valueFrom(token)
while (!stack.isEmpty() &&
stack.last().is(Operator) &&
operator <= stack.last()) {
output.add stack.pop()
}
stack.add operator
}
}
}
def static evenSpaceAroundParens(string) {
def output = []
string.each { letter ->
if (!output.isEmpty() && letter != ' ') {
def last = output.last()
if (isParen(letter) && last != ' ') {
output.add ' '
} else if (isParen(last)) {
output.add ' '
}
}
output.add letter
}
output.join()
}
def static isParen(letter) {
letter == '(' || letter == ')'
}
}
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).
package org.jadcon.expression
enum Operator {
PLUS('+', 0, { a, b -> a + b }),
MINUS('-', 0, { a, b -> a - b }),
MULTIPLY('*', 1, { a, b -> a * b }),
DIVIDE('/', 1, { a, b -> a / b })
String value
int precedence
Closure calculate
private Operator(String value, int precedence, Closure calculate) {
this.value = value
this.precedence = precedence
this.calculate = calculate
}
def static valueFrom(string) {
for (operator in Operator.values()) {
if (operator.value == string) {
return operator
}
}
throw new IllegalArgumentException("invalid operator ${string}")
}
def int compareTo(other) {
precedence <=> other.precedence
}
def String toString() {
value
}
}
Coding the shunting yard algorithm was fun exercise in Groovyness.