Skip to content

Instantly share code, notes, and snippets.

@sergeyklay
Last active May 30, 2020 09:17
Show Gist options
  • Save sergeyklay/53f2a8a7342e721ca8f8a7b8b3e8311a to your computer and use it in GitHub Desktop.
Save sergeyklay/53f2a8a7342e721ca8f8a7b8b3e8311a to your computer and use it in GitHub Desktop.
Reverse Polish Notation
import java.util.Stack
import java.lang.Long.parseLong
fun String.isNumeric(): Boolean {
return try {
parseLong(this)
true
} catch (e: NumberFormatException) {
false
}
}
fun eval(t: String, op1: Long, op2: Long): Long {
return when (t) {
"+" -> op1 + op2
"-" -> op1 - op2
"*" -> op1 * op2
"/" -> op1 / op2
"|" -> op1 or op2
"&" -> op1 and op2
"^" -> op1 xor op2
"<<" -> op1 shl op2.toInt()
">>" -> op1 shr op2.toInt()
else -> throw UnsupportedOperationException(
"Invalid expression: $op1 $t $op2"
)
}
}
fun calc(stack: Stack<Long>, expr: String): Long {
expr.split("\\s+".toRegex()).forEach {
if (it.isNumeric()) {
stack.push(parseLong(it))
} else {
if (stack.size < 2) {
throw UnsupportedOperationException(
"Invalid expression: not enough operands"
)
}
val op2 = stack.pop()
val op1 = stack.pop()
stack.push(eval(it, op1, op2))
}
}
return stack.pop()
}
fun main() {
val exprs = arrayOf(
"7 2 3 * -",
"1 2 + 4 * 3 +",
"3 4 + 5 2 - *",
"7 3 ^ 15 72 - +",
"12 12 25 | &",
"1 212 0 << <<",
"-68 4 212 1 >> + -"
)
val stack = Stack<Long>()
for (expr in exprs) {
println("$expr = ${calc(stack, expr)}")
}
}
@sergeyklay
Copy link
Author

sergeyklay commented May 29, 2020

Output:

7 2 3 * - = 1
1 2 + 4 * 3 + = 15
3 4 + 5 2 - * = 21
7 3 ^ 15 72 - + = -53
12 12 25 | & = 12
1 212 0 << << = 1048576
-68 4 212 1 >> + - = -178

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment