okuzawatsの日記

Android / Kotlin Enthusiast 🤖

Implement Reverse Polish Notation with Kotlin

Implemented a calculator by Reverse Polish Notation with Kotlin.

I defined some operators as token. The tokens are numbers and the four arithmetic operators. I thought numbers and operators should be distinguished, so defined Token class as sealed class, and defined Number and Operator as subclasses of Token class. Number is a data class that has a value of BigDecimal. Operator has subclasses such as Plus which represents the four arithmetic operators. The subclasses of Operator has a function that takes two parameters of Number and returns the result of calculation.

sealed class Token {

  data class Number(val value: BigDecimal) : Token() {
    override fun toString(): String = value.toPlainString()
  }

  sealed class Operator : Token() {

    abstract fun execute(lhs: Number, rhs: Number): Number

    object Plus : Operator() {
      override fun execute(lhs: Number, rhs: Number) = Number(value = lhs.value.plus(rhs.value))
    }

    object Minus : Operator() {
      override fun execute(lhs: Number, rhs: Number) = Number(value = lhs.value.minus(rhs.value))
    }

    object Multiply : Operator() {
      override fun execute(lhs: Number, rhs: Number)  = Number(value = lhs.value.multiply(rhs.value))
    }

    object Divide : Operator() {
      override fun execute(lhs: Number, rhs: Number)  = Number(value = lhs.value.divide(rhs.value))
    }
  }
}

Here implements a function to execute calculation, which receives an array of Token and returns Number. When a caliulation is completed, the Stack has only one Number, else throws exception. The function runs the array and pushes Number to the Stack if an element of the array is Number. Or if an element of the array is Operator, the function pops two Numbers to execute an operation then pushed the result to the Stack.

fun calculate(tokens: Array<Token>): Token.Number {
  val stack = Stack<Token.Number>()

  for (token in tokens) {
    when (token) {
      is Token.Number -> {
        // if it is Number, push it to the Stack
        stack.push(token)
      }
      is Token.Operator -> {
        // if it is Operator, execute the operation
        val rhs = stack.pop() // rhs is at the first of the Stack
        val lhs = stack.pop() // lhs is at the second of the Stack
        stack.push(token.execute(lhs = lhs, rhs = rhs)) // push the result to the Stack
      }
    }
  }

  if (stack.size == 1) {
    return stack.pop()
  } else {
    throw IllegalArgumentException("illegal token combination")
  }
}

Here it works.

val tokens = arrayOf<Token>(
  Token.Number(value = BigDecimal.valueOf(1.0)),
  Token.Number(value = BigDecimal.valueOf(2.0)),
  Token.Operator.Plus,
  Token.Number(value = BigDecimal.valueOf(3.0)),
  Token.Number(value = BigDecimal.valueOf(4.0)),
  Token.Operator.Multiply,
  Token.Operator.Divide,
)

val result = calculate(tokens)

println(result) // 0.25

#Kotlin

About me 😎

profile

茨城県つくば市在住のソフトウェアエンジニアです。専門領域はAndroidアプリ開発で、特にアーキテクチャに興味があります。某社でAndroidアプリ開発のテックリードをしています。

Jetpack ComposeによるAndroid MVVMアーキテクチャ入門の著者です。

👉 もっと詳しく

Writing 📝

Android MVVMアーキテクチャ入門

Androidアプリ開発の初学者に向けた、MVVM(Model-View-ViewModel)アーキテクチャの入門書を書きました。初学者の方を確実にネクストレベルに引き上げる技術書です。

👉 もっと詳しく

See Also 👀