1

I am looking for an algorithm to convert a postfix expressions to infix expressions but with minimal parentheses.

I am asking it here after searching Google Stack Overflow. I only found a single answer to my question but it was in Java and I don't understand that language. I am looking for a algorithm but if you can give a JavaScript or Python (the only languages I understand) implementation I will be very thankful to you.

This is what I have been able to do on the base of my current understanding.

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`
}

But this code is giving unexpected results.

Jongware
  • 22,200
  • 8
  • 54
  • 100
Chief VOLDEMORT
  • 89
  • 1
  • 15
  • Please link the java post you found. Notice that the *algorithm* will be the same. – Bergi Jan 02 '18 at 13:19
  • Instead of calling these things "friends", you should give your infix operators a precedence and an associativity. – Bergi Jan 02 '18 at 13:20
  • @bergi https://stackoverflow.com/a/35897601/8641677 No algorithm :( – Chief VOLDEMORT Jan 02 '18 at 13:38
  • @bergi I didn't had a good name so I named it friends but does it really matter what I call the variable – Chief VOLDEMORT Jan 02 '18 at 13:39
  • 1
    Of course it matters what you call variables, as that makes the code readable and understandable to your fellow programmers, like those you're asking here on StackOverflow, and to your future self. – Bergi Jan 02 '18 at 14:05
  • Can you add some examples of your current output and what it should be? – Jongware Jan 02 '18 at 15:16
  • @ChiefVOLDEMORT The linked answer has an algorithm — expressed as a Java class. IMHO that code should be fairly ”readable” for someone with JavaScript and Python knowledge. – BlackJack Jan 11 '18 at 16:36

1 Answers1

3

Ok I fixed the problem myself. Thought I shall write the answer for future use and other users. The answer is based on the algorithm in this SO answer.

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)
Chief VOLDEMORT
  • 89
  • 1
  • 15