Parsing/Shunting-yard algorithm: Difference between revisions
Added Kotlin
(Added Kotlin) |
|||
Line 2,453:
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + </pre>
=={{header|Kotlin}}==
{{trans|Java}}
<lang scala>// version 1.2.0
import java.util.Stack
/* To find out the precedence, we take the index of the
token in the OPS string and divide by 2 (rounding down).
This will give us: 0, 0, 1, 1, 2 */
const val OPS = "-+/*^"
fun infixToPostfix(infix: String): String {
val sb = StringBuilder()
val s = Stack<Int>()
val rx = Regex("""\s""")
for (token in infix.split(rx)) {
if (token.isEmpty()) continue
val c = token[0]
val idx = OPS.indexOf(c)
// check for operator
if (idx != - 1) {
if (s.isEmpty()) {
s.push(idx)
}
else {
while (!s.isEmpty()) {
val prec2 = s.peek() / 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.peek() != -2) sb.append(OPS[s.pop()]).append(' ')
s.pop()
}
else {
sb.append(token).append(' ')
}
}
while (!s.isEmpty()) sb.append(OPS[s.pop()]).append(' ')
return sb.toString()
}
fun main(args: Array<String>) {
val es = listOf(
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3",
"( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
)
for (e in es) {
println("Infix : $e")
println("Postfix : ${infixToPostfix(e)}\n")
}
}</lang>
{{out}}
<pre>
Infix : 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Infix : ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
Postfix : 1 2 + 3 4 + ^ 5 6 + ^
</pre>
=={{header|Liberty BASIC}}==
| |||