四则运算之中缀转后缀

[zhuanyongxigua]

前置知识：前缀、中缀和后缀表达式。

以224. 基本计算器来作为例子说明中缀转后缀的过程。

难点：

1. 合法的中缀表达式有哪些。
2. 熟练的知晓中缀表达式转换为后缀之后的样子；

在编程语言中 1++1 是不合法的，因为 ++ 本身是一个运算符，不能有二义性。而 1+-1 是合法的，与 -1+1 等价。在上述题目中，虽然两者均不合法，无需考虑，但是，+2+(-2) 这样写是合法的，是有点麻烦的地方。

对于中缀转换为后缀之后的样子，可以举个例子：1+2*(3+4*(5+6*7))。对于后缀表达式，无需使用括号来表达优先级，从左到右第一个操作符就是第一个需要执行的运算，然后在找下一个最左的操作符，以此类推。所以在中缀转后缀的过程中，我们就需要找出中缀表达式中第一个执行的运算符，把它放到后缀表达式的最左端即可。在 1+2*(3+4*(5+6*7)) 中，第一个被执行的应该是最右端的 6*7 其他的都需要等待它出了结果才能继续计算。下一个是 5+，以此类推，最后得到的后缀表达式应该是 1234567*+*+*+。对于后缀表达式的计算，有简单一些的150. 逆波兰表达式求值题目。

接下来就可以开始考虑转换了。

1. 对于数字，可以立刻加入到后缀表达式中。因为后缀表达式的运算的优先级的关键在于操作符，所以只要操作符的次序正确，数字的顺序并不是问题。
2. 对于操作符，由于有优先级的问题，同上述的例子，需要排好操作符的顺序。当前的操作符能否执行，取决于下一个操作符的优先级是否比当前的高，如果下一个更高，那下一个操作符就会抢走当前操作符右边的数字。如果下一个较高优先级的操作符已经执行了，那当前的操作符一定可以执行了。我们需要用一个数据结构来维护这些操作符，它的任务是比较最后一个被维护的操作符与当前被解析出来的操作符的优先级，如果前者的优先级大于等于后者，则前者可以进入后缀表达式中。如果前者的优先级低于后者，则需要把前者保存起来，之后紧跟着在它之后被维护的操作符进入后缀表达式中。答案呼之欲出，后进先出的数据结构，就是栈。
3. 对于括号，是一种不能出现在后缀表达式中的带有优先级的特殊操作符。对于左括号，可以直接入栈，它不参与运算，只是作为一个标识，优先级最低（需要注意的是，这里说的这个优先级是用来帮助维护栈内的操作符的，跟中缀四则运算中的的优先级不是一个东西）。对于右括号，遇到了之后，我们就知道了，括号里面的内容一定要先算完，所以需要一直弹出栈顶的操作符，直到遇到左括号这个标识为止。右括号无需入栈，也就无所谓优先级。这里面不好理解的地方，可能是在左括号入栈之后，遇到有括号之前这段时间内，会有一些操作符出栈了，其实没关系，这是预期的情况，可以把括号内的表达式想象成一个独立的四则运算的表达式，同时想象用一个新的栈来维护，遇到右括号说明要结束了，栈里面还剩下的都是优先级最低的，可以最后全部出栈了。
4. 对于相对特殊的1+(-1)的情况，可能会出现的地方有两个，一个是整个表达式开始的第一个字符，另一个出现左括号之后的第一个字符。可以通过在他们之前补零来解决。

综上：

// 后缀表达式的计算函数，可以直接用来解：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
function evalRPN (tokens) {
  const stack = []
  for (let i = 0; i < tokens.length; i++) {
    const token = tokens[i]
    if (
      token !== '+'
      && token !== '-'
      && token !== '*'
      && token !== '/'
    ) {
      stack.push(Number(token))
    } else {
      const right = stack.pop()
      const left = stack.pop()
      let result = 0
      if (token === '+') {
        result = left + right
      } else if (token === '-') {
        result = left - right
      } else if (token === '*') {
        result = left * right
      } else {
        result = left / right
        if (result >= 0) {
          result = Math.floor(result)
        } else {
          result = Math.ceil(result)
        }
      }
      stack.push(result)
    }
  }
  return stack.pop()
}

function getPriority (op) {
  if (op === '+' || op === '-') return 1
  if (op === '*' || op === '/') return 2
  return 0
}

// 补零
function pushZero (s, i, tokens) {
  let j = i + 1
  while (s[j] === ' ') j++
  const nextChar = s[j]
  if (getPriority(nextChar) !== 0) {
    tokens.push('0')
  }
}

// 与“150. 逆波兰表达式求值”的输入为解析好的 token 数组不同，这一题的输入是字符串表达式，需要自己解析其中的数字，数字不只有一位数字。
function parseNum (s, i, tokens) {
  let val = 0
  let j = i
  while (s[j] >= '0' && s[j] <= '9') {
    val = val * 10 + Number(s[j])
    j++
  }
  if (j === i) {
    return -1
  }
  tokens.push(String(val))
  return j
}

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  const tokens = []
  const opsStack = []
  pushZero(s, -1, tokens)
  for (let i = 0; i < s.length; i++) {
    const numResult = parseNum(s, i, tokens)
    if (numResult !== -1) {
      i = numResult - 1
      continue
    }

    const char = s[i]

    if (char === ' ') continue

    if (char === '(') {
      opsStack.push(char)
      pushZero(s, i, tokens)
      continue
    }
    if (char === ')') {
      while (opsStack.length !== 0 && opsStack[opsStack.length - 1] !== '(') {
        tokens.push(opsStack.pop())
      }
      opsStack.pop()
      continue
    }

    while (opsStack.length !== 0 && getPriority(opsStack[opsStack.length - 1]) >= getPriority(char)) {
      tokens.push(opsStack.pop())
    }
    opsStack.push(char)
  }
  while (opsStack.length !== 0) {
    tokens.push(opsStack.pop())
  }
  return evalRPN(tokens)
};

为了拆分模块，难免会造成一些性能上损失，但总体复杂度不变，依然是 O(n)，所以这不是什么大问题。

直接递归

如果对上面的思路很熟悉了，那借用一部分来直接递归也是可以的。当前的操作符能否执行，取决于下一个操作符的优先级是否高于当前的。那么如果下一个优先级更高，甚至遇到括号，就直接递归好了。

function getPriority (op) {
  if (op === '+' || op === '-') return 1
  if (op === '*' || op === '/') return 2
  return 0
}

function parseNum (s, i, tokens) {
  let val = 0
  let j = i
  while (s[j] >= '0' && s[j] <= '9') {
    val = val * 10 + Number(s[j])
    j++
  }
  if (j === i) {
    return -1
  }
  tokens.push(val)
  return j
}

export function getBracketEnd (s, index) {
  const stack = ['(']
  for (let i = index + 1; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push('(')
    } else if (s[i] === ')') {
      stack.pop()
      if (stack.length === 0) {
        return i
      }
    }
  }
}

export function parse (s, start, end) {
  const tokens = []
  for (let i = start; i <= end; i++) {
    const numResult = parseNum(s, i, tokens)
    if (numResult !== -1) {
      i = numResult - 1
      continue
    }
    const char = s[i]

    if (char === ' ') continue

    if (char === '(') {
      const bracketEndIndex = getBracketEnd(s, i)
      const bracketTokens = parse(s, i + 1, bracketEndIndex - 1)
      tokens.push(bracketTokens)
      i = bracketEndIndex
      continue
    }

    tokens.push(char)
  }
  return tokens
}

function cal (left, op, right) {
  if (op === '+') {
    return left + right
  } else if (op === '-') {
    return left - right
  } else if (op === '*') {
    return left * right
  } else {
    const result = left / right
    if (result >= 0) {
      return Math.floor(result)
    } else {
      return Math.ceil(result)
    }
  }
}

function calTokens (tokens) {
  let val = tokens[0]
  let i = 1
  // 处理类似"-1 + 1"的情况
  if (typeof val === 'string') {
    val = 0
    i = 0
  } else if (typeof val === 'object') { // 处理类似"(1 + 1)"的情况
    val = calTokens(val)
  }
  while (i < tokens.length) {
    const token = tokens[i]
    if (getPriority(tokens[i + 2]) > getPriority(token)) {
      let right = calTokens(tokens, i + 1)[0]
      return cal(val, token, right)
    } else {
      let right = tokens[i + 1]
      if (typeof right === 'object') {
        right = calTokens(right)
      }
      if (typeof val === 'object') {
        val = calTokens(val)
      }
      val = cal(val, token, right)
      i = i + 2
    }
  }
  return val
}

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function(s) {
  const tokens = parse(s, 0, s.length - 1)
  // 在这里打印 tokens，就很容易明白了
  // console.log(tokens)
  return calTokens(tokens)
};

我写的这个思路，由于会有这两行代码：

const bracketEndIndex = getBracketEnd(s, i)
const bracketTokens = parse(s, i + 1, bracketEndIndex - 1)

确认括号的结尾之后还有再解析一遍，所以会比较慢，复杂度是 O(mn)，m 是括号的数量，n 是字符串的长度。