reverse-polish.js

// calc([6, 5, 2, 3, '+', 8, '*', '+', 3, '+', '*']) // 288
function calc (a) {
  const stack = []
  const methods = {
    '+': (a, b) => b + a,
    '-': (a, b) => b - a,
    '*': (a, b) => b * a,
    '/': (a, b) => b / a,
  }
  let current
  while (current = a.shift()) {
    if (typeof current === 'number') {
      stack.push(current)
    } else {
      const func = methods[current]
      stack.push(func(stack.pop(), stack.pop()))
    }
  }
  console.log(stack[0])
}

function convert (mid) {
  console.log(mid.join(' '))
  const result = []
  const stack = []
  const methods = ['(', ')', '*', '/', '+', '-']
  const orders = {
    '*': 2,
    '/': 2,
    '+': 1,
    '-': 1,
  }
  let current
  while (current = mid.shift()) {
    if (!methods.includes(current)) { // is number
      result.push(current)
    } else if (current === '(') {
      stack.push(current)
    } else if (current === ')') {
      let t
      while (t = stack.pop()) {
        if (t === '(') break
        result.push(t)
      }
    } else {
      let prev
      while (prev = stack.pop()) {
        if (orders[prev] >= orders[current]) {
          result.push(prev)
        } else {
          stack.push(prev)
          break
        }
      }
      stack.push(current)
    }
  }
  let left
  while (left = stack.pop()) {
    result.push(left)
  }
  console.log(result.join(' '))
}
// convert(['a', '+', 'b', '*', 'c', '+', '(', 'd', '*', 'e', '+', 'f', ')', '*', 'g'])
// a b c * + d e * f + g * +

function Node (val, left, right) {
  this.val = val
  this.left = left
  this.right = right
}

function totree (arr) {
  const methods = ['+', '-', '*', '/']
  const stack = []
  let current
  while (current = arr.shift()) {
    if (!methods.includes(current)) { // is number
      stack.push(new Node(current))
    } else {
      const right = stack.pop()
      const left = stack.pop()
      stack.push(new Node(current, left, right))
    }
  }
  return stack.pop()
}
// console.log(JSON.stringify(totree(['a', 'b', '+', 'c', 'd', 'e', '+', '*', '*'])))