Skip to content

Instantly share code, notes, and snippets.

@EmmanuelMess
Last active October 28, 2018 00:34
Show Gist options
  • Save EmmanuelMess/22ca82b4f4683af0a6b7732e344ae238 to your computer and use it in GitHub Desktop.
Save EmmanuelMess/22ca82b4f4683af0a6b7732e344ae238 to your computer and use it in GitHub Desktop.
A calculator using shunting yard and inverse polish (aka postfix) notation
import java.math.BigInteger
import java.util.*
import kotlin.IllegalArgumentException
sealed class Values(value: Any) {
data class Boolean(val value: kotlin.Boolean): Values(value) {
override fun toString() = value.toString()
}
data class Decimal(val value: BigInteger): Values(value) {
override fun toString() = value.toString()
}
}
enum class TokenType(val precedence: Int) {
VAL(14),
SUM(3), SUB(3),
MULT(4), DIV(4),
EQ(0)
}
sealed class Token(val token: TokenType) {
class Eq: Token(TokenType.EQ)
data class Op(val op: TokenType, val f: (BigInteger, BigInteger) -> BigInteger): Token(op)
data class Value(val value: Values): Token(TokenType.VAL)
}
fun Char.toToken() = when(this) {
'+' -> Token.Op(TokenType.SUM, BigInteger::add)
'-' -> Token.Op(TokenType.SUB, BigInteger::subtract)
'*' -> Token.Op(TokenType.MULT, BigInteger::multiply)
'/' -> Token.Op(TokenType.DIV, BigInteger::divide)
'=' -> Token.Eq()
else -> throw IllegalArgumentException()
}
fun shuntingYard(parse: String): Queue<Token> {
val queue: Queue<Token> = LinkedList<Token>()
val stack = Stack<Token>()
parse.forEach { ch ->
when {
ch.isWhitespace() -> return@forEach
ch.isDigit() -> {
queue.offer(Token.Value(Values.Decimal(BigInteger.valueOf((ch - '0').toLong()))))
}
listOf('t', 'f').contains(ch) -> {
queue.offer(Token.Value(Values.Boolean(ch == 't')))
}
listOf('+', '-', '*', '/', '=').contains(ch) -> {
val op = ch.toToken()
while(stack.isNotEmpty() && op.token.precedence <= stack.peek().token.precedence) {
queue.add(stack.pop() as Token)
}
stack.push(op)
}
else -> throw IllegalStateException()
}
}
while (stack.isNotEmpty()) {
queue.add(stack.pop())
}
return queue
}
fun calculateIPN(queue: Queue<Token>): Values {
val tempStack = Stack<Token>()
while (queue.isNotEmpty()) {
when (queue.peek().token) {
TokenType.VAL -> {
val tok = queue.poll() as Token.Value
tempStack.push(tok)
}
TokenType.SUM, TokenType.SUB, TokenType.MULT, TokenType.DIV -> {
val op = (queue.remove() as Token.Op).f
val a = ((tempStack.pop() as Token.Value).value as Values.Decimal).value
val b = ((tempStack.pop() as Token.Value).value as Values.Decimal).value
tempStack.add(Token.Value(Values.Decimal(op(a, b))))
}
TokenType.EQ -> {
queue.remove()
val aRaw = (tempStack.pop() as Token.Value).value
val bRaw = (tempStack.pop() as Token.Value).value
if(aRaw is Values.Decimal && bRaw is Values.Decimal) {
tempStack.add(Token.Value(Values.Boolean(aRaw.value == bRaw.value)))
} else if(aRaw is Values.Boolean && bRaw is Values.Boolean) {
tempStack.add(Token.Value(Values.Boolean(aRaw.value == bRaw.value)))
} else {
tempStack.add(Token.Value(Values.Boolean(false)))
}
}
}
}
if(queue.isNotEmpty()) {
throw IllegalArgumentException()
}
return (tempStack.pop() as Token.Value).value
}
fun main(args: Array<String>) {
println(calculateIPN(shuntingYard("t")))
println(calculateIPN(shuntingYard("5 + 5")))
println(calculateIPN(shuntingYard("5 + 6 * 3 + 6")))
println(calculateIPN(shuntingYard("2 + 2 = 5")))
println(calculateIPN(shuntingYard("t = f")))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment