概要
本文以一个 🌰 的解题思路，来分享如何解决问题。
解决的过程，可以作为解决工作中一般问题的通用思路。
希望同学有所收获。
问题
通过JS解析数学表达式字符串。
(1 + (2 - (3 * 4 / 5 + 6 - (7 + 8))) + (9 - 10) * 11 + 12) + 13
表达式中包含基本的数学运算符号+ 、 - 、 * 、 /和()小括号，数字都是正整数。
下面记录了个人的思考过程。
拆解问题
正常在做数学运算的时候，一般都是先进行左侧的运算，拿左边的运算结果继续和右边的继续运算。从左到右运算时，可能会遇到不同的操作符。
如果遇到
+、-，直接对运算符左右两侧数字进行加减运算，拿到结果后和下一个继续运算。如果遇到了
*、/，则优先计算乘除，在进行加减运算。如果遇到了
()，则小括号内的表达式被视为一个整体参与运算，在得到运算结果后再参与小括号外的运算。
以上是对一个程序问题场景的拆分，我们可以得到下面几个原则
- 运算是从左到右。
- 表达式中
+、-，直接拆分成左右两个 - 表达式中
*、/，则*、/可以被视为一个整体做优先计算。如都是*、/同上。 - 表达式中
()，被视为一个整体
JS解析数学表达式，被拆解为上面的四个原则，即是我们需要解决的问题。所以在遇到一个大的问题时，我们第一步应该是对问题进行拆解。
在对一个个小问题进行解答的时候，我们就把一个大的问题解决了。
下面逐一解决这四个问题。
解决问题
从左到右计算
从左到右计算，有两个关键点从左到右和计算。
计算
我们先分析计算，在进行+ - * /计算时，即利用运算符号对两侧数字进行运算。下面用一个图表示下1+2
这样就确定了一个运算操作的基本数据结构，即二叉🌲。中间节点存储运算符号，left节点储存左侧的数值，right节点存储右边的数值。
从左到右
这里举一个简单的加法运算表达式1 + 2 + 3 + 4来分析从左到右。我们从左到右遍历这个这个表达式，可以得到下图二叉🌲。
但是遍历这样的数据结构得到的运算过程是从右到左（深度遍历先计算 3 + 4 一直到 1）。所以我们尝试从右到左遍历这个表达式，可以得到下图。
现在我们就明确了编码需要做的具体事项，即从右到左遍历表达式，形成一个二叉🌲。基本的代码如下：
const expression = 'xxxx';
const parse = (expression, l = 0, r = expression.length - 1) => {
for (let i = r; i >= l; i--) {
const v = expression[i];
let isNumber = true;
if (i === l) {
if (isNumber) {
return {
type: 'number',
value: Number(expression.slice(l, r + 1).trim()),
};
}
}
if (/[0-9]/.test(v) || v === ' ') {
continue;
}
isNumber = false;
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
}
}+ -拆分左右
对+ -进行左右拆分，这个可以基于上面的代码，稍调整下逻辑即可：
...
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
...更改为
...
if (v === '+' || v === '-') {
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
}
...* /拆分左右
相较于+ - 拆分左右，* /更加复杂些。我们应该先拆分场景。
可以整理出两个场景，仅包含* /和混合运算。
1 + 2 * 3 / 41 * 2 * 3 / 4
我们在从右到左遍历表达式时，我们在遇到* /，需要继续向左遍历，判断表达式左边是否有+ - 。
如果遇到了+ -，则按照 + -拆分左右 的原则解析。
如果是仅包含 * /，则我们需要拿遇到的第一个运算符/，拆分左右。
我们调整下parse的逻辑
...
let firstTimeOrDivideOperator = null; // 记录遇到的第一个 * / 运算符
let firstTimeOrDivideOperatorIdx = null; // 记录遇到的第一个 * / 运算符的位置
...
// 遍历到最左侧，判断 * / 左边是否有 + -
if (i === l) {
...
// * / 拆分，需要遍历到最左侧，所里拆分逻辑写这里
return {
type: firstTimeOrDivideOperator,
left: parse(expression, i, firstTimeOrDivideOperatorIdx - 1),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
...
if ((v === '*' || v === '/') && !firstTimeOrDivideOperator) {
firstTimeOrDivideOperator = v
firstTimeOrDivideOperatorIdx = i
}()整体
()被视为一个整体，首先我们要知道哪两个括号是一对。一个表达式如果剔除了+ - * /后，剩下的部分可能是这个样子(()(()))。
我们从右到左分析这个字符串，在整个字符串中，遇到的第一个(，右侧离它最近的那个)，它们俩就是一对。然后我们将这一对()剔除。重复上面的操作即：
(()(()))(()(--))(()----)(------)--------
分析上面的步骤，我们可以知道，如果遇到)我们记录下来，如果遇到(，则将将最近的)剔除。对数据结构敏感的同学，一定会想到栈。
同时我们要记录下(、)位置信息。
我们调整下parse的逻辑
const stock = []; // 先进后出，每一次出栈，即一对 ()
const parenthesesPairPosition = {}
...
let parenthesesDep = 0; // 记录小括号深度
...
if (v === ')') {
stock.push(i)
parenthesesDep++
} else if (v === '(') {
const last = stock.pop()
parenthesesPairPosition[i] = last
parenthesesDep--
}
if (i === l) {
...
if (parenthesesPairPosition[i] === r) {
return parse(expression, l + 1, r - 1)
}
...
}
...优化
优化一般是减少重复的工作。
我们可以快速定位上面解决问题内容的 * / 拆分左右 部分有重复的工作。
1 + 2 * 3 / 4 在从右向左搜索字符串串时，第一遍我们就知道了连续的* /，第二遍我可以不用遍历到最左侧，按照搜索到的第一个* /拆分左右即可。
优化上面的代码：
const parse = (expression, l = 0, r = expression.length - 1, skipSearchTimeOrDivide = false) => {
...
let firstTimeOrDivideOperator = null; // 记录遇到的第一个 * / 运算符
let firstTimeOrDivideOperatorIdx = null; // 记录遇到的第一个 * / 运算符的位置
for (let i = r; i >= l; i--) {
...
// skipSearchTimeOrDivide 为 true 表示表达式是连续的 * /
if (skipSearchTimeOrDivide && firstTimeOrDivideOperator) {
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
if (i === l) {
...
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
...
if ((v === '*' || v === '/') && !firstTimeOrDivideOperator) {
firstTimeOrDivideOperator = v
firstTimeOrDivideOperatorIdx = i
}
}
}完整代码
补充了剔除两侧空格和小括号、运算和细节。
const stock = []; // 先进后出，每一次出栈，即一对 ()
const parenthesesPairPosition = {}
// 剔除两侧空格
const removeBlank = (expression, l, r) => {
while (expression[l] === ' ') {
l++
}
while (expression[r] === ' ') {
r--
}
return [l, r]
}
// 剔除两侧小括号
const removeParentheses = (l, r) => {
if (parenthesesPairPosition[l] === r) return [++l, --r]
return [l, r]
}
const parse = (expression, l = 0, r = expression.length - 1, skipSearchTimeOrDivide = false) => {
let isNumber = true;
let parenthesesDep = 0; // 记录小括号深度
let firstTimeOrDivideOperator = null; // 记录遇到的第一个 * / 运算符
let firstTimeOrDivideOperatorIdx = null; // 记录遇到的第一个 * / 运算符的位置
[l, r] = removeBlank(expression, l, r);
[l, r] = removeParentheses(l, r);
for (let i = r; i >= l; i--) {
const v = expression[i];
if (v === ')') {
stock.push(i)
parenthesesDep++
} else if (v === '(') {
const last = stock.pop()
parenthesesPairPosition[i] = last
parenthesesDep--
}
// skipSearchTimeOrDivide 为 true 表示表达式是连续的 * /
if (skipSearchTimeOrDivide && firstTimeOrDivideOperator) {
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
if (i === l) {
if (isNumber) {
return {
type: 'number',
value: Number(expression.slice(l, r + 1).trim()),
};
}
if (parenthesesPairPosition[i] === r) {
return parse(expression, l + 1, r - 1)
}
// * / 拆分，需要遍历到最左侧，所里拆分逻辑写这里
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
if (/[0-9]/.test(v) || v === ' ') {
continue;
}
isNumber = false;
// parenthesesDep === 0 进行表达式分析的时候要确保是同一层级
if (parenthesesDep === 0 && (v === '+' || v === '-')) {
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
}
if (parenthesesDep === 0 && (v === '*' || v === '/') && !firstTimeOrDivideOperator) {
firstTimeOrDivideOperator = v
firstTimeOrDivideOperatorIdx = i
}
}
}
const exec = ast => {
const recursion = ast => {
if (ast.type === '+') {
return recursion(ast.left) + recursion(ast.right)
} else if (ast.type === '-') {
return recursion(ast.left) - recursion(ast.right)
} else if (ast.type === '*') {
return recursion(ast.left) * recursion(ast.right)
} else if (ast.type === '/') {
return recursion(ast.left) / recursion(ast.right)
} else if (ast.type === 'number') {
return ast.value
}
}
return recursion(ast)
}
const expression = '(1 + (2 - (3 * 4 / 5 + 6 - (7 + 8))) + (9 - 10) * 11 + 12) + 13'
console.log(exec(parse(expression)) === eval(expression))总结
解决一般问题的通用思路：
- 拆分问题
- 基于问题拆分场景，根据不同的情况编写逻辑
- 优化代码，分析代码中重复的工作等等
同时我们也要拓展编程相关基本知识，不断学习。这样在面对问题时，可以快速想到可能的解决方案。 例如上面的问题，同学对数据结构有所了解的话，则分析小括号可以迅速想到用栈去解决。另外一点就是编译原理中也有讲到扫描运算表达式时，从右到左扫描。
到此这篇关于JavaScript 解析数学表达式的过程详解的文章就介绍到这了,更多相关js解析表达式内容请搜索阿兔在线工具以前的文章或继续浏览下面的相关文章希望大家以后多多支持阿兔在线工具！
