precedence-parser.js

const POWER = {
  '+': 1,
  '-': 1,
  '*': 2,
  '/': 2,
  '^': 3,
};

function parse(input) {
  let affix = 'prefix'
  let stack = []
  let nodes = []

  const prevPower = () => POWER[nodes.at(-1)?.[0] ?? -1] ?? 0
  
  // lower the binding power to an amount, you can imagine this as finally applying the invisible `)`'s and connecting the nodes together in reverse
  // for example a node list of [ + * ^ ] would change it to be like [+ [* [^]]]
  // an important aspect is that it will only apply these changes to the power level
  function lowerPower(toPower) {
    let last
    for (let i = 1; i < nodes.length + 1; i++) {
      console.log(i);
      if (prevPower() < toPower) break
      last = nodes.pop()
      
      let lastNode = nodes.at(-1);
      if(lastNode != null) lastNode[2] = last
    }
    return last
  }

  for(const token of input.split(' ')) {
    switch (affix) {
      case 'prefix': {
        stack.push(token)
        affix = 'infix'
        break
      }
      case 'infix': {
        // if then current power is greater than the previous node's power
        if (POWER[token] > prevPower()) {
          nodes.push([token, stack.pop()])
        } else {
          nodes.at(-1)[2] = stack.pop()
          const last = lowerPower(POWER[token])
          nodes.push([token, last])
        }

        affix = 'prefix'
        break
      }
    }
  }
  nodes.at(-1).push(stack.pop())
  for(let i = 1; i < nodes.length; i++) lowerPower(-1)
  return nodes[0]
}

const mapArray = (a, fnA, fnV) => Array.isArray(a) ? fnA(a.map(v => mapArray(v, fnA, fnV))) : fnV(a)

let input = '1 + 2 * 3 ^ 4 + 5 / 6'
let nodes = parse(input)
console.log(nodes, mapArray(nodes, ([o, l, r]) => `(${l} ${o} ${r})`, i => ({'^':'**'}[i] ?? i)))