Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Kotlin 数学表达式解析(支持函数与负号)
import java.util.*
import kotlin.math.abs
import kotlin.math.sin
class MathParser {
companion object {
private const val ZERO_CODE = '0'.toInt() // 便于通过字符串编码快速 char -> int
private const val TOKEN_NULL: Short = -1
private const val TOKEN_NUM: Short = 1
private const val TOKEN_LP: Short = 2
private const val TOKEN_RP: Short = 3
private const val TOKEN_OP: Short = 4 // 操作符,包括函数操作符
private const val TOKEN_SP: Short = 4 // 函数分隔符
private const val OP_LP: Short = 0 // (
private const val OP_ADD: Short = 1 // +
private const val OP_MIN: Short = 2 // -
private const val OP_MUL: Short = 3 // *
private const val OP_DIV: Short = 4 // /
private const val OP_N: Short = 5 // ~ (负号)
// ----------------以上 OP 的编号必须与 priority 数组下标一致
private const val OP_FUN_ABS: Short = 10 // abs
private const val OP_FUN_SIN: Short = 11 // sin
/** 判断是否是函数操作符。 */
private fun isFunOp(op: Short): Boolean = op >= 10
}
// 函数只能出现在数学模式中,函数的返回值必须是数字,且不可以与其他数字字符拼接成新数字。
/**
* 表示 `(+-x/~` 的优先级。`true` 表示高于。例如 `p[1][3]=true` 表示x的优先级大于+。其中 `~` 表示负号。
*
* 下标与 `OP_*` 常量一致。
*/
private val priority = arrayOf(
// ( + - * / ~
booleanArrayOf(false, true, true, true, true, true), // (
booleanArrayOf(false, false, false, true, true, true), // +
booleanArrayOf(false, false, false, true, true, true), // -
booleanArrayOf(false, false, false, false, false, true), // *
booleanArrayOf(false, false, false, false, false, true), // /
booleanArrayOf(false, false, false, false, false, true), // ~ (负号)
)
private val numStack = Stack<Double>()
private val opStack = Stack<Short>()
private var fraction = 0.0 // 当前已经识别到数字字符表示的小数位数,0表示未进入小数模式,0.1表示十分位
private var fractionMode
get() = fraction != 0.0
set(value) {
fraction = if (!value) {
0.0
} else {
if (fraction == 0.0) 1.0
else throw IllegalStateException()
}
}
private var num = 0.0
private var readingNumFlag = false // 是否正处于解析数字的过程中
/** 用于解析标识符。 */
private val idBuilder = StringBuilder(10)
private var readingIdFlag = false // 是否正处于解析函数名的过程中
fun parse(str: String): Double {
val s = "($str)" // 为了算法一致性确保最外层由括号包裹
var i = 0
/** 上一个成功解析的单词类型,用于判定减号语义。 */
var preTokenType = TOKEN_NULL
while (i < s.length) {
val c = s[i]
if (c == ' ' || c == '\n' || c == '\t') {
i++ // 跳过空白字符
continue
}
if (c.isLetter() || (readingIdFlag && (c.isDigit() || c == '_'))) {
// 标识符部分。标识符必须是字母开头,只能是字母数字下划线。
readingIdFlag = true
idBuilder.append(c)
i++
continue
} else if (readingIdFlag) {
// 结束标识符解析模式并压栈
when (val id = idBuilder.toString()) {
"pi" -> {
preTokenType = TOKEN_NUM
numStack.push(Math.PI)
}
"e" -> {
preTokenType = TOKEN_NUM
numStack.push(Math.E)
}
"abs" -> {
preTokenType = TOKEN_OP
eatFunction(OP_FUN_ABS)
}
"sin" -> {
preTokenType = TOKEN_OP
eatFunction(OP_FUN_SIN)
}
else -> throw ParseException("Unknown identifier $id.")
}
resetReadIdFlag()
// 当前字符尚未消耗,这里不能 continue
}
if (c == '.') {
readingNumFlag = true
if (fractionMode) throw ParseException() // 不能有连续的点.
fractionMode = true
i++
continue
}
if (c.isDigit()) {
readingNumFlag = true
if (!fractionMode) {
num = num * 10 + c.toInt() - ZERO_CODE
} else {
fraction /= 10
num += (c.toInt() - ZERO_CODE) * fraction
}
i++
continue
}
// 不是数字或小数字符
if (readingNumFlag) {
// 结束数字解析模式并压栈
preTokenType = TOKEN_NUM
numStack.push(num)
resetReadNumberFlag()
// 当前字符尚未消耗,这里不能 continue
}
if (c == ',') {
eatSeparator()
preTokenType = TOKEN_SP
i++
continue
}
if (isOp(c)) {
eatOp(c, preTokenType)
preTokenType = when (c) {
'(' -> TOKEN_LP
')' -> TOKEN_RP
else -> TOKEN_OP
}
i++
continue
}
}
return numStack.pop()
}
/**
* 处理运算符。函数内不需要自行调用 `i++`。
*
* @param c 运算符,可能的值参考 [isOp]。
* @param preToken 上一个解析的单词类型,值为 `TOKEN_` 常量。
*/
private fun eatOp(c: Char, preToken: Short) {
while (true) {
if (c == ')') {
// 将栈中元素依次出栈入队,直到左括号,括号出栈不入队。
// 此时若栈顶元素是函数,则出栈入队
while (!opStack.isEmpty() && opStack.peek() != OP_LP) {
calc(opStack.pop())
}
if (opStack.isEmpty())
throw ParseException("parentheses do not match.")
opStack.pop()
if (!opStack.isEmpty() && isFunOp(opStack.peek())) {
calc(opStack.pop())
}
return
}
var c1 = c
if (c == '-') {
if (preToken == TOKEN_NUM)
c1 = '-'
else if (preToken == TOKEN_LP || preToken == TOKEN_OP || preToken == TOKEN_SP)
c1 = '~'
else if (preToken == TOKEN_RP)
c1 = if (numStack.isEmpty()) '~' else '-'
else
throw ParseException("Wrong '-' position.")
}
if (c1 == '(' || opStack.isEmpty() || opStack.peek() == OP_LP) {
// 若A为空|A是左括号|B是左括号,则B入栈。
opStack.push(op2d(c1))
return
}
if (preThan(op2d(c1), opStack.peek())) {
// 若B优先级大于A,则B入栈。
opStack.push(op2d(c1))
return
}
// 否则A出栈入队循环,直到满足上述条件之一。
calc(opStack.pop())
}
}
/**
* 处理函数操作符。函数内不需要自行调用 `i++`。
*
* @param opFun 操作符代码。
*/
private fun eatFunction(opFun: Short) {
opStack.push(opFun)
}
/**
* 处理函数参数分隔符。函数内不需要自行调用 `i++`。
*/
private fun eatSeparator() {
while (opStack.peek() != OP_LP) {
calc(opStack.pop())
}
}
/**
* 根据给定操作符执行操作。自行判断 [numStack] 状态并进行相应操作。
*
* @param op 操作符。
*/
private fun calc(op: Short) {
when (op) {
OP_ADD -> numStack.push(numStack.pop() + numStack.pop())
OP_MIN -> {
val t = numStack.pop()
numStack.push(numStack.pop() - t)
}
OP_MUL -> numStack.push(numStack.pop() * numStack.pop())
OP_DIV -> {
val t = numStack.pop()
numStack.push(numStack.pop() / t)
}
OP_N -> {
numStack.push(-1 * numStack.pop())
}
OP_FUN_ABS -> numStack.push(abs(numStack.pop()))
OP_FUN_SIN -> numStack.push(sin(numStack.pop()))
else -> throw ParseException("Cannot recognize operator $op. ")
}
}
/** 判断是否是运算符,包括括号()不包括点.。*/
private fun isOp(c: Char): Boolean = c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/'
/** 将操作符转为数字以便高效存入[opStack]。 */
private fun op2d(c: Char): Short = when (c) {
'(' -> OP_LP
'+' -> OP_ADD
'-' -> OP_MIN
'*' -> OP_MUL
'/' -> OP_DIV
'~' -> OP_N
else -> throw IllegalArgumentException("$c is not an operator")
}
/** 判断 [op1] 是否比 [op2] 优先级更高。不支持函数操作符。 */
private fun preThan(op1: Short, op2: Short): Boolean {
if (isFunOp(op1) || isFunOp(op2)) throw IllegalArgumentException("Function op is not supported.")
return priority[op2.toInt()][op1.toInt()]
}
/**
* 重置解析数字标记。将解除数字解析状态并重置相关变量。
*/
private fun resetReadNumberFlag() {
fractionMode = false
readingNumFlag = false
num = 0.0
}
/**
* 重置解析标识符标记。
*/
private fun resetReadIdFlag() {
readingIdFlag = false
idBuilder.clear()
}
class ParseException(s: String? = null) : RuntimeException(s)
}
@liangchenhe55

This comment has been minimized.

Copy link
Owner Author

@liangchenhe55 liangchenhe55 commented May 2, 2021

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment