Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
36 lines (31 sloc) 1.37 KB
package io.jacobappleton.compilers.regex
class ShuntingYard(val operatorPrecedence: Map[Char, Int]) {
def toPostfix(s: String): String = toPostfix(s.toList, List(), "")
def isOperator(x: Char) = operatorPrecedence.contains(x)
def hasLowerPrecedence(a: Char, b: Char) = operatorPrecedence(a) <= operatorPrecedence(b)
private def toPostfix(input: List[Char], operators: List[Char], output: String): String = {
input match {
case Nil =>
operators match {
case Nil => output
case oh :: ot => toPostfix(input, ot, output :+ oh)
}
case ih :: it =>
if (isOperator(ih)) {
if (operators.nonEmpty && operators.head != '(' && hasLowerPrecedence(ih, operators.head)) {
val operatorsWithHigherPrecedence = operators.takeWhile(o => o != '(' && hasLowerPrecedence(ih, o))
toPostfix(it, ih +: operators.diff(operatorsWithHigherPrecedence), output ++ operatorsWithHigherPrecedence)
} else {
toPostfix(it, ih +: operators, output)
}
} else {
input match {
case Nil => ""
case '(' :: t => toPostfix(t, '(' +: operators, output)
case ')' :: t => toPostfix(t, operators.dropWhile(_ != '(').tail, output ++ operators.takeWhile(_ != '('))
case h :: t => toPostfix(t, operators, output :+ h)
}
}
}
}
}