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