将postfix（反向抛光表示法）表达式转换为具有最小括号的中缀

Question

我正在寻找一种算法，将后缀表达式转换为中缀表达式，但括号最小。

我在搜索谷歌堆栈溢出后问这里。我只找到了一个问题的答案，但它是用Java编写的，我不懂那种语言。我正在寻找一种算法，但如果你能提供JavaScript或Python（我理解的唯一语言）实现，我将非常感谢你。

这是我根据目前的理解能够做到的。

const postfixToInfix = RPN => {
  let convert = RPN.replace(/\^/g,'**').split(/\s+/g).filter(el => !/\s+/.test(el) && el !== '')
  let stack = []
  let result = []
  let friends = {"+" : ["+","-","*","/"],"-":[],"/":["*"],"*":["/","*"],"**":["+","-","*","/"]}
  convert.forEach(symbol => {
    if(!isNaN(parseFloat(symbol)) && isFinite(symbol)){
      result.push(symbol)
    }
    else if (Object.keys(friends).includes(symbol)) {
      a = result.pop()
      b = result.pop()
      if(stack.length !==0){
          if(friends[symbol].includes(stack.pop())){
            result.push(`${b} ${symbol} ${a}`)
            stack.push(symbol)
          }
          else{
            result.push(`(${b}) ${symbol} ${a}`)
            stack.push(symbol)
          }
      }
      else {result.push(`${b} ${symbol} ${a}`);stack.push(symbol)}
    }
    else throw `${symbol} is not a recognized symbol`
  })
  if(result.length === 1) return result.pop()
  else throw `${RPN} is not a correct RPN`
}

但这段代码给出了意想不到的结果。

Answer 1

好的，我自己解决了这个问题。以为我会写下未来使用和其他用户的答案。答案是基于this SO回答的算法。

const postfixToInfix = RPN => {
  let convert = RPN.replace(/\^/g,'**').split(/\s+/g).filter(el => !/\s+/.test(el) && el !== '')
  let stack = []
  let result = []
  let precedence = {null : 4 ,'**':3 ,'/' : 2,'*': 2,'+':1,'-':1 }
  convert.forEach(symbol => {
    let stra,strb
    if(!isNaN(parseFloat(symbol)) && isFinite(symbol)){
      result.push(symbol)
      stack.push(null)
    }
    else if (Object.keys(precedence).includes(symbol)) {
      let [a,b,opa,opb] = [result.pop(),result.pop(),stack.pop(),stack.pop()]
      if(precedence[opb] < precedence[symbol]) {
         strb = `(${b})`
      }
      else{
         strb = `${b}`
      }
      if((precedence[opa] < precedence[symbol]) || ((precedence[opa] === precedence[symbol]) && ["/","-"].includes(symbol) )){
         stra = `(${a})`
      }
      else {
         stra = `${a}`
      }
      result.push(strb +symbol + stra)
      stack.push(symbol)
  }
    else throw `${symbol} is not a recognized symbol`
  })
  if(result.length === 1) return result.pop()
  else throw `${RPN} is not a correct RPN`
}
console.log(postfixToInfix('1 2 3 - + 4 5 - 6 7 - 8 + / * ')) //(1+2-3)*(4-5)/(6-7+8)