以前、プログラミング学び直しシリーズとして Kotlinによる逆ポーランド記法四則演算機 を作った。その続きとして、Kotlin/JVMで中置記法の計算式を逆ポーランド記法に変換するコードを書いた。

enum class Operator(
    val value: Char
) {
    ADD('+'),
    SUB('-'),
    MUL('*'),
    DIV('/'),
    BRACKET_OPEN('('),
    BRACKET_CLOSE(')'),
    //
    ;

    fun match(x: Char?): Boolean
            = this.value == x

    fun match(x: String?): Boolean
            = x?.length == 1 && match(x.first())

    fun str(): String
            = value.toString()

}

// `char`がいずれかの演算記号と合致するか
fun Char.isOperator(): Boolean
        = Operator.values().map { it.value }.contains(this)

data class Node(
    val expr: List<String>,
    val left: Node? = null,
    val right: Node? = null
)

fun main(args: Array<String>) {
    val expr = tokenize(args[0])

    val tree = process(
        Node(expr)
    )

    println(
        traversePostOrder(tree).joinToString(" ")
    )
}

fun tokenize(src: String): List<String> {
    val tokens: MutableList<String> = mutableListOf()
    var currentNumbers = ""

    repeat(src.length) { i ->
        val x = src[i]

        if (x.isWhitespace()) {
            return@repeat // 空白は削除
        } else if (x.isOperator()) {
            if (currentNumbers.isNotEmpty()) {
                // 何かしらの記号だった場合、ここまでの連続した数値をtokenとして追加
                tokens.add(currentNumbers)
            }
            currentNumbers = ""
            tokens.add(x.toString()) // 記号を追加
        } else {
            currentNumbers += x // 連続した数値を記録
        }
    }

    // 終端まで来たら残った内容を追加
    if (currentNumbers.isNotEmpty()) {
        tokens.add(currentNumbers)
    }

    return tokens
}

// 再帰で自身より下位の数式を処理
fun process(tree: Node): Node {
    val expr = removeMostOuterBrackets(tree.expr)
    val i = searchLowPriorityOperatorPosition(expr)

    if (i == null) {
        return tree.copy(expr) // 自身より下位が無ければ括弧を削除したものを返し終了
    } else {
        return Node(
            expr = listOf(expr[i]), // 最も優先度が低く右側の記号
            left = process(Node(
                expr.slice(0 .. (i - 1)) // 頭から記号の手前まで
            )),
            right = process(Node(
                expr.slice((i + 1) .. (expr.size - 1)) // 記号直後から終端まで
            ))
        )
    }
}

// 両側の括弧が対応していれば削除する
fun removeMostOuterBrackets(expr: List<String>): List<String> {
    if (!Operator.BRACKET_OPEN.match(expr.firstOrNull()))
        return expr // 最初が括弧でなければ削除する必要が無い

    var nest = 0

    repeat(expr.size) { i ->
        when (expr[i]) {
            Operator.BRACKET_OPEN.str() -> {
                nest++
            }
            Operator.BRACKET_CLOSE.str() -> {
                nest--

                // 最後の文字に来る前に開始した括弧が全て閉じられてしまった場合、両側の削除は不要 (できない)
                if (i != (expr.size - 1) && nest == 0)
                    return expr
            }
        }
    }

    return removeMostOuterBrackets(
            expr.slice(1 .. (expr.size - 2) )
    )
}

// 最も優先順位の低い演算子を探す
fun searchLowPriorityOperatorPosition(expr: List<String>): Int? {
    var ret: Int? = null
    var lastPriority = Int.MAX_VALUE // 優先順位の低いものがほしいため

    var nest = 0
    var priority = 0

    repeat(expr.size) {
        when (expr[it]) {
            Operator.ADD.str(), Operator.SUB.str() ->
                priority = 1
            Operator.MUL.str(), Operator.DIV.str() ->
                priority = 2
            Operator.BRACKET_OPEN.str() -> run {
                nest++
                return@repeat
            }
            Operator.BRACKET_CLOSE.str() -> run {
                nest--
                return@repeat
            }
            else -> run { return@repeat }
        }

        // 優先順位が低く、かつ最も後に登場したものを最後に返す
        if (0 == nest && priority <= lastPriority) { // ネスト0 = 優先順位が低い
            lastPriority = priority
            ret = it
        }
    }

    return ret
}

// 後行順序訪問
fun traversePostOrder(tree: Node): List<String> {
    var ret: MutableList<String> = mutableListOf()

    tree.left?.let { ret.addAll(traversePostOrder(it)) }
    tree.right?.let { ret.addAll(traversePostOrder(it)) }

    return ret + tree.expr
}

たとえば以下のように入力すると:

(((3+3+4)*(334+(3/3-4))*(3*3*4)+(3+3-4))*(3-34)+(3-(3+4)))*(3-34)+(3-(3-4))

以下のように出力される:

3 3 + 4 + 334 3 3 / 4 - + * 3 3 * 4 * * 3 3 + 4 - + 3 34 - * 3 3 4 + - + 3 34 - * 3 3 4 - - +

さて、これを担当している授業で高校生に教えようとしているのだが、どう説明していこうかな。