Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Shunting Yard algorithm implementation for a rudimentary Regex pattern language.
package io.jacobappleton.compilers.regex
class ShuntingYard(val operatorPrecedence: Map[Char, Int]) {
def toPostfix(s: String): String = toPostfix(s, "", "")
def isOperator(x: Char) = operatorPrecedence.contains(x)
def hasLowerPrecedence(a: Char, b: Char) = operatorPrecedence(a) <= operatorPrecedence(b)
private def toPostfix(input: String, operators: String, output: String): String = {
input match {
case "" =>
operators match {
case "" => output
case _ => toPostfix(input, operators.tail, output :+ operators.head)
}
case _ =>
if (isOperator(input.head)) {
if (operators.nonEmpty && operators.head != '(' && hasLowerPrecedence(input.head, operators.head)) {
val operatorsWithHigherPrecedence = operators.takeWhile(o => hasLowerPrecedence(input.head, o))
toPostfix(input.tail, input.head +: operators.diff(operatorsWithHigherPrecedence), output ++ operatorsWithHigherPrecedence)
} else {
toPostfix(input.tail, input.head +: operators, output)
}
} else {
input.head match {
case '(' => toPostfix(input.tail, input.head +: operators, output)
case ')' => toPostfix(input.tail, operators.dropWhile(_ != '(').tail, output ++ operators.takeWhile(_ != '('))
case _ => toPostfix(input.tail, operators, output :+ input.head)
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.