49 lines
1.3 KiB
Scala
49 lines
1.3 KiB
Scala
import scala.util.control.Breaks._
|
|
|
|
object ShuntingYard {
|
|
|
|
def main(args: Array[String]): Unit = {
|
|
val infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
|
|
println(s"infix: $infix")
|
|
println(s"postfix: ${infixToPostfix(infix)}")
|
|
}
|
|
|
|
def infixToPostfix(infix: String): String = {
|
|
val ops = "-+/*^"
|
|
val sb = new StringBuilder
|
|
val s = scala.collection.mutable.Stack[Int]()
|
|
|
|
infix.split("\\s").foreach { token =>
|
|
if (token.nonEmpty) {
|
|
val c = token.head
|
|
val idx = ops.indexOf(c)
|
|
|
|
if (idx != -1) {
|
|
if (s.isEmpty) s.push(idx)
|
|
else {
|
|
breakable({
|
|
while (s.nonEmpty) {
|
|
val prec2 = s.top / 2
|
|
val prec1 = idx / 2
|
|
if (prec2 > prec1 || (prec2 == prec1 && c != '^')) sb.append(ops(s.pop)).append(' ')
|
|
else break
|
|
}
|
|
});
|
|
s.push(idx)
|
|
}
|
|
} else if (c == '(') {
|
|
s.push(-2) // -2 stands for '('
|
|
} else if (c == ')') {
|
|
// until '(' on stack, pop operators.
|
|
while (s.top != -2) sb.append(ops(s.pop)).append(' ')
|
|
s.pop()
|
|
} else {
|
|
sb.append(token).append(' ')
|
|
}
|
|
}
|
|
}
|
|
while (s.nonEmpty) sb.append(ops(s.pop)).append(' ')
|
|
sb.toString
|
|
}
|
|
}
|