题解 | 表达式求值

object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 返回表达式的值
        * @param s string字符串 待计算的表达式
        * @return int整型
    */
    fun solve(s: String): Int  {
        // write code here
        return evaluateExpr(s)
    }

val OP_MAP = mapOf(
    "+" to 1,
    "-" to 1,
    "*" to 2,
    "/" to 2,
)

data class TokenList(
    val tokens: List<String>,
    var position: Int,
) {
    fun nextToken() = tokens[position++]
    fun peek() = tokens[position]
    fun isEnd() = position == tokens.size
}

fun String.toTokens(): TokenList {
    val tokens = mutableListOf<String>()
    val buffer = StringBuilder()
    for (i in indices) {
        val ch = this[i]
        when {
            ch.isDigit() -> {
                buffer.append(ch)
            }

            ch in listOf(' ', '\t') -> {
                if (buffer.isNotEmpty()) {
                    tokens.add(buffer.toString())
                    buffer.clear()
                }
            }

            ch in listOf('+', '-', '*', '/', '(', ')') -> {
                if (buffer.isNotEmpty()) {
                    tokens.add(buffer.toString())
                    buffer.clear()
                }
                tokens.add(ch.toString())
            }

            else -> error("Unexpected character '$ch' in this at position $i")
        }
    }
    if (buffer.isNotEmpty()) {
        tokens.add(buffer.toString())
    }
    return TokenList(tokens, 0)
}

data class ParseContext(
    val tokens: TokenList,
    var currentAst: Ast? = null,
)

abstract class AbsParser {
    abstract fun isMatch(ctx: ParseContext): Boolean
    abstract fun parse(ctx: ParseContext): Ast

    protected val parsers = mutableListOf<AbsParser>()

    fun addParser(parser: AbsParser) {
        parsers.add(parser)
    }
}

class NumAstParser : AbsParser() {
    override fun isMatch(ctx: ParseContext): Boolean {
        val token = ctx.tokens.peek()
        return token.matches("\\d+".toRegex())
    }

    override fun parse(ctx: ParseContext): Ast {
        val token = ctx.tokens.nextToken()
        val numAst = NumAst().also { it.value = token.toInt() }
        getLastUnfinishedAst(ctx.currentAst)?.let {
            it.right = numAst
            return ctx.currentAst!!
        }
        ctx.currentAst = numAst
        return numAst
    }
}

class BinOpAstParser : AbsParser() {
    override fun isMatch(ctx: ParseContext): Boolean {
        val token = ctx.tokens.peek()
        return token in OP_MAP.keys
    }

    override fun parse(ctx: ParseContext): Ast {
        val token = ctx.tokens.nextToken()
        val binOp = BinOpAst().apply { op = token }
        ctx.currentAst?.let { it as? BinOpAst }?.let {
            if (binOp.weight > it.weight) {
                val tmp = it.right
                it.right = binOp
                binOp.left = tmp
                return it
            }
        }
        binOp.left = ctx.currentAst
        ctx.currentAst = binOp
        return binOp
    }
}

fun getLastUnfinishedAst(currentAst: Ast?): BinOpAst? {
    if (null == currentAst) return null
    if (currentAst is BinOpAst) {
        if (null == currentAst.right) return currentAst
        return getLastUnfinishedAst(currentAst.right)
    } else if (currentAst is SubAst) {
        return getLastUnfinishedAst(currentAst.content)
    } else if (currentAst is NumAst) {
        return null
    }
    throw IllegalStateException("unexpected ast in getLastUnfinishedAst $currentAst")
}

class SubAstParser : AbsParser() {
    val exprParser: AbsParser
        get() = parsers[0]

    override fun isMatch(ctx: ParseContext): Boolean {
        val token = ctx.tokens.peek()
        return token == "("
    }

    override fun parse(ctx: ParseContext): Ast {
        ctx.tokens.nextToken() // consume left parenthesis
        val subCtx = ParseContext(ctx.tokens)
        val ast = exprParser.parse(subCtx)
        ctx.tokens.nextToken() // consume right parenthesis
        val subAst = SubAst().apply { content = ast }
        getLastUnfinishedAst(ctx.currentAst)?.let {
            it.right = subAst
            return ctx.currentAst!!
        }
        ctx.currentAst = subAst
        return subAst
    }
}

class MetaOrParser : AbsParser() {

    override fun isMatch(ctx: ParseContext): Boolean = parsers.any { it.isMatch(ctx) }

    override fun parse(ctx: ParseContext): Ast = parsers.first { it.isMatch(ctx) }.parse(ctx)
}

class MetaMaybeParser : AbsParser() {
    val parser: AbsParser
        get() = parsers[0]
    override fun isMatch(ctx: ParseContext): Boolean {
        return true
    }

    override fun parse(ctx: ParseContext): Ast {
        if (ctx.tokens.isEnd() || !parser.isMatch(ctx)) return ctx.currentAst!!
        return parser.parse(ctx)
    }
}

class MetaSequenceParser : AbsParser() {
    override fun isMatch(ctx: ParseContext): Boolean {
        return parsers[0].isMatch(ctx)
    }

    override fun parse(ctx: ParseContext): Ast =
        parsers.fold(NumAst() as Ast) { _, parser ->
            parser.parse(ctx)
        }
}

class MetaConstConsumeParser(val consumeToken: String) : AbsParser() {
    override fun isMatch(ctx: ParseContext): Boolean {
        return consumeToken == ctx.tokens.peek()
    }

    override fun parse(ctx: ParseContext): Ast {
        ctx.tokens.nextToken()
        return ctx.currentAst!!
    }

}

// expr = num | sumExpr [binOp expr]
// subExpr = '(' expr ')'

abstract class Ast {
    protected val children: MutableList<Ast?> = mutableListOf()
    abstract fun eval(): Int
}

class NumAst : Ast() {
    var value: Int = 0
    override fun eval() = value
    override fun toString() = "N($value)"
}

class BinOpAst() : Ast() {
    init {
        children.add(null) // left
        children.add(null) // right
    }

    var op: String = ""
    var left: Ast?
        get() = children[0]
        set(value) {
            children[0] = value
        }
    var right: Ast?
        get() = children[1]
        set(value) {
            children[1] = value
        }
    val weight: Int
        get() = OP_MAP[op] ?: throw IllegalArgumentException("Invalid operator: $op")


    override fun eval(): Int {
        val cv = children.map { it?.eval() ?: throw IllegalStateException("Null param for $op") }
        val lv = cv[0]
        val rv = cv[1]
        return when (op) {
            "+" -> lv + rv
            "-" -> lv - rv
            "*" -> lv * rv
            "/" -> lv / rv
            else -> throw IllegalArgumentException("Invalid operator: $op")
        }
    }

    override fun toString() = "Bin(op=$op,l=$left,r=$right)"
}

class SubAst : Ast() {
    init {
        children.add(null)
    }

    var content: Ast?
        get() = children[0]
        set(value) {
            children[0] = value
        }

    override fun eval(): Int {
        return content?.eval() ?: throw IllegalStateException("no content for SubAst!")
    }
    override fun toString() = "Sub($content)"
}


fun evaluateExpr(expr: String): Int {
    val tokenList = expr.toTokens()

    val ctx = ParseContext(tokenList)

    val parser = metaSequenceParser parser@{
        addParser(metaOrParser {
            addParser(numAstParser())
            addParser(subAstParser { addParser(this@parser) })
        })
        addParser(metaMaybeParser {
            addParser(metaSequenceParser {
                addParser(binOpAstParser())
                addParser(this@parser)
            })
        })
    }

    val ast = parser.parse(ctx)
    return ast.eval()
}

fun metaSequenceParser(block: MetaSequenceParser.() -> Unit) = MetaSequenceParser().apply(block)

fun metaOrParser(block: MetaOrParser.() -> Unit) = MetaOrParser().apply(block)

fun metaMaybeParser(block: MetaMaybeParser.() -> Unit) = MetaMaybeParser().apply(block)

fun subAstParser(block: SubAstParser.() -> Unit) = SubAstParser().apply(block)

fun numAstParser() = NumAstParser()

fun binOpAstParser() = BinOpAstParser()
}