A Shunting Yard algorithm implementation for a rudimentary Regex pattern language.

ShuntingYard.scala

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