一道编程题的思考

昨天碰到了一道编程题，这道题目印象还挺深刻，记得还是读大学的时候，室友都已入睡自己还在熬夜写C++代码，当时AC的题目与这道题目类似(过去太久了记得是写个计算器)，题目放在代码文件里删了，大概就是输入一个字符串到程序里，该程序模拟计算器解析字符串并进行加、减、乘、除运算。

　　昨天自己写的代码是通过三次循环，第一次循环将字符串解析成数字和操作符存入数组，第二次循环遍历数组处理乘法和除法运算，第三次循环再次遍历数组计算加法和减法运算。用了三次循环这肯定是非常差劲的解法，导致昨夜睡前思来想去睡不着，由于最近笔者开源项目发布新版本，干了几天4点睡，加上这道刺头更睡不着了，笔者秉持有刺必须拔掉的原则把夜里想的思路实现下，通过一次循环加递归方式实现(附完整代码)

输入：只包含+、-、*、/的完整表达式字符串

样例1:

• input: 0 +1 + 2
• output: 3

样例2:

• input: 2*3 + 3*4
• output: 18

样例2:

• input: 4/3 - 10
• output: -9

实现思路其实大差不差，对比如下：

1. 一次性扫描改成动态扫描，昨天版本代码第一次循环是为了扫描字符串将数字和操作符分别提取出来，动态扫描通过游标current记录每次扫描到的值，碰到操作符直接进行处理；
2. 昨日版本由于是一次性扫描的，因此操作符的处理按照操作符优先级用了两次循环分别处理，现在版本也是按操作符优先级分两种情况处理，不过没有额外的循环:
   • 处理加法减法：当扫描到加减法操作符，则操作符滞后的字符串可以理解为一个新的表达式，因此用递归方式实现，由于递归方式是倒叙处理表达式的，因此需要用正负标志(flag)标记上一步表达式的操作，加法默认正标记，减法则为负标记。
   • 处理乘法除法：使用一次性扫描由于数字扫描的滞后性，因此通过闭包函数handle辅助处理，当扫描完滞后性的数字后再执行handle方法
3. 昨日的三次循环版本开发用时三十几分钟，这次的递归版本开发用时一个小时，递归版本用时主要花在调试上，如正负标志和current与ans的关系上。

三次循环版本文件删了没法复原，以下是递归版本代码：

const log = false;

const wrap = (func, name) => {
  return (...params) => {
    const ret = func(...params);
    if (log) console.log(`操作符：${name}，入参：${params}，结果：${ret}`);
    return ret;
  }
}

const operator = {
  '+': wrap((x, y) => x + y, '+'),
  '-': wrap((x, y) => x - y, '-'),
  '*': wrap((x, y) => x * y, '*'),
  '/': wrap((x, y) => Math.floor(x / y), '/'),
}

function main(str, flag = 1, deep = 0) {
  let ans = null, current = null, handle = null;
  for (let i = 0; i < str.length; i++) {
    if (/\d/.test(str[i])) {
      if (current === null) {
        current = Number(str[i]);
      } else {
        current = current * 10 + Number(str[i]);
      }
    } else if (operator[str[i]]) {
      if (ans === null) ans = current;
      if (handle) {
        ans = handle(current);
        handle = null;
      }
      if (['+', '-'].includes(str[i])) {
        ans = operator[str[i]](ans, flag * main(str.slice(i + 1), str[i] === '+' ? 1 : -1, deep + 1));
        current = null;
        break;
      } else {
        handle = ((left) => {
          return (right) => {
            return operator[str[i]](left, right);
          }
        })(ans);
      }
      current = null;
    }
  }
  if (handle) ans = handle(current);
  else if (current) ans = current;
  if (log) console.log(`表达式：${str}，结果：${ans}`);
  return ans;
}

console.log(main(' 0 +1 + 2 ')); // 3
console.log(main(' 2*3 + 3*4')); // 18
console.log(main(' 4 /3 - 10 ')); // -9
console.log(main(' 100 /3 - 10 + 523 * 0 * 22 / 6 + 100 ')); // 123
console.log(main(' 55 - 5 - 10 -30 -2 ')); // 8