题目描述

存在字符串 '11+2-34+5/24+10/5'，现在需要将高优先级运算，用小括号包裹起来，例如结果为 '11+2-(34)+(5/24)+(10/5)'。注意可能会出现连续的乘除运算，需要包裹到一起

思路解析

1. 使用正则匹配，匹配到运算符和数字，然后替换；
2. 遍历 + 双指针方式，通过快指针查找符合，通过慢指针记录上一次的数字开始；
3. 两次遍历方式，先找出所有符号，然后基于符号关系添加括号

代码实现

1. 正则实现， 简单但理解比较难些

function addBracket(str) {
  // \d 匹配数字
  // +  至少有一个数字
  // [*|/] 匹配 * 或者 / 符合
  // ([*|/]\d+)? 连续的 * / 符合
  return str.replace(/(\d+[*|/]\d+([*|/]\d+)?)/g, `($1)`);
}

2. 遍历 + 双指针方式，通过快指针查找符合，通过慢指针记录上一次的数字开始

function addBracket(str) {
  let fast = 1; // 快指针，遇到符合是判断优先级；
  let slow = 0; // 慢指针，用于标识数字的开始；
  let isInBracket = false; // 辨识是否在括号中，遇到低优先符号时，需要结束
  const isHigherOperater = char => ['*', '/'].includes(char);
  const isLowerOperater = char => ['+', '-'].includes(char);

  let res = ''
  while (fast < str.length) {
    if (isHigherOperater(str[fast])) {
      if (!isInBracket) {
        isInBracket = true;
        res += `(${str.slice(slow, fast + 1)}`;
        // fast 是符号，则下一个为数字
        slow = fast + 1;
      }
    } else if (isLowerOperater(str[fast])) {
      res += str.slice(slow, fast);
      if (isInBracket) {
        res += ')'
        isInBracket = false;
      }
      // 遇到低优先级符号时，需要先判断是否添加 )，不然符合会添加到括号内
      res += str[fast];
      slow = fast + 1;
    }
    fast++;
  }
  res += str.slice(slow, fast);
  if (isInBracket) {
    res += ')';
  }
  return res;
}

3. 两次遍历方式，先找出所有符号，然后基于符号关系添加括号

function addBracket(str) {
  const operaters = [];
  const isHigherOperater = char => ['*', '/'].includes(char);
  const isLowerOperater = char => ['+', '-'].includes(char);

  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    if (isHigherOperater(char) || isLowerOperater(char)) {
      operaters.push(char);
    }
  }
  let currentOpIdx = 0;
  let endOp = isHigherOperater(operaters[currentOpIdx]);
  let res = endOp ? '(' : '';
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    // 符号插入逻辑相对复杂一点：
    // 例如 + * + 需要在第一个 + 后面添加 (, 然后需要在第二个 + 前面添加 )
    if (char === operaters[currentOpIdx]) {
      if (endOp && isLowerOperater(char)) {
        res += ')';
        endOp = false;
      }
      res += char;
      //  判断是否需要添加括号的添加为当前为低优先级符号，下一个为高优先级的符号
      //  * * 不用处理
      //  + * 需要在 + 后添加 (
      //  * + 需要在 + 前添加 )，上面已经处理
      //  + + 不需要处理
      if (isHigherOperater(operaters[currentOpIdx + 1]) && isLowerOperater(char)) {
        res += '(';
        endOp = true;
      }
      currentOpIdx++;
    } else {
      res += char;
    }
  }
  if (endOp) {
    res += ')';
  }
  return res;
}