Last active
August 15, 2022 23:21
-
-
Save ichenhe/a438769a2c40947d2d3717541e21e007 to your computer and use it in GitHub Desktop.
Kotlin 数学表达式解析(支持函数与负号)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
See: https://juejin.cn/post/6957336568046714917