JS 实现 中缀表达式转化成后缀表达式

中缀表达式 → 后缀表达式 / 逆波兰表达式

数据结构：栈

转化过程：

1. 创建两个栈s1，s2

   s1用来存储运算符

   s2用来存储中间结果

2. 遍历表达式：

   1. 当遇到数字时，推入s2

   2. 当遇到运算符时：

      1. 若s1为空，或s1栈顶非运算符即 ( 和 ) ，推入s1

      2. 与s1栈顶运算符比较：

         低于栈顶：推入s1

         等于栈顶：推入s2

         高于栈顶：弹出栈顶，将栈顶推入s2，循环直到该运算符弹入任意栈

   3. 处理 ( 和 )

      1. 如果为 (，推入s1
      2. 如果为 ) ，将s1的栈顶不断的出栈并入栈到s2中，直到s1栈顶为 ( 时停止，并将 ( 出栈丢弃

3. 重复 2 里面的所有过程，直到表达式遍历结束

4. 将s2中的栈顶依次出栈并入栈到s1中

5. 将s1中的栈顶依次出栈并输出，即得到后缀表达式（逆波兰式）

JS 实现：

function infixToSuffix(infix) {
  let symbol = [],
    value = [],
    res = ''
  infix.split('').forEach((item) => {
    switch (true) {
      case /\d/.test(item):
        value.push(item)
        break
      case /[+\-*/]/.test(item):
        while (symbol.length + 1) {
          if (!symbol.length || !/[+\-*/]/.test(symbol[symbol.length - 1])) {
            // 栈顶为空或非运算符
            symbol.push(item) // 弹入栈1
            break
          }
          if (/[*/]/.test(item) && /[+\-]/.test(symbol[symbol.length - 1])) {
            // 比栈顶低
            symbol.push(item) // 弹入栈1
            break
          }
          if (/[+\-]/.test(item) && /[*/]/.test(symbol[symbol.length - 1])) {
            // 比栈顶高
            value.push(symbol.pop()) // 弹出栈顶，栈顶弹入栈2
            continue
          }
          // 等于栈顶
          value.push(item) // 弹入栈2
          break
        }
        break
      case /\(/.test(item):
        symbol.push(item)
        break
      case /\)/.test(item):
        while (symbol.length) {
          let mid = symbol.pop()
          if (mid !== '(') {
            value.push(mid)
          } else break
        }
        break
      default:
    }
  })
  while (value.length) {
    symbol.push(value.pop())
  }
  while (symbol.length) {
    res += symbol.pop()
  }
  return res
}
console.log(infixToSuffix('(3+4)*5-6')) // 34+5*6-
console.log(infixToSuffix('1+2*3+(4*5+6)*7')) // 123*+45*6+7*+

补充：

• 栈：先进后出

• 队列：先进先出

• 堆：树形数据结构

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。