目录

• 概要
• 问题
• 拆解问题
• 解决问题
• 从左到右计算
• 计算
• 从左到右
• + -拆分左右
• * /拆分左右
• ()整体
• 优化
• 完整代码
• 总结

概要

本文以一个 的解题思路，来分享如何解决问题。

解决的过程，可以作为解决工作中一般问题的通用思路。

希望同学有所收获。

问题

通过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 / 4
• 1 * 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))

总结

解决一般问题的通用思路：

• 拆分问题
• 基于问题拆分场景，根据不同的情况编写逻辑
• 优化代码，分析代码中重复的工作等等

同时我们也要拓展编程相关基本知识，不断学习。这样在面对问题时，可以快速想到可能的解决方案。 例如上面的问题，同学对数据结构有所了解的话，则分析小括号可以迅速想到用栈去解决。另外一点就是编译原理中也有讲到扫描运算表达式时，从右到左扫描。