text: # Converting from postfix to infix
  
  What would be a good algorithm for converting from postfix to infix? I've searched and searched but I only get algorithms for converting from infix to postfix. They're going to be decently similar algorithms correct? I also want to incorporate parenthesis. For example, (((13 - 1) / 2)(3 + 5)). Thank you!
  
  • Maintain a stack 1. if you read a value push it to stack 2. if you read an operator, pop 2 values(say a,b) and push "(a operator b)" back to stack Seems like it will do – Sunny Agrawal Sep 27 '13 at 14:24
  
  Here's the postfix version:-
  
  ``````13 1 - 2 / 3 5 + *
  ``````
  
  To convert, parse it like an ordinary postfix parser, but store elements on the stack as a string, not as values:-
  
  ``````"13"
  "1"
  "-"
  ``````
  
  when you get an operator, like above, convert to a single string and put parenthesis around it:-
  
  ``````"(13-1)"
  ``````
  
  continuing:-
  
  ``````"(13-1)"
  "2"
  "/"
  ``````
  
  becomes:-
  
  ``````"((13-1)/2)"
  ``````
  
  continuing:-
  
  ``````"((13-1)/2)"
  "3"
  "5"
  "+"
  ``````
  
  becomes:-
  
  ``````"((13-1)/2)"
  "(3+5)"
  ``````
  
  finally:-
  
  ``````"((13-1)/2)"
  "(3+5)"
  "*"
  ``````
  
  ends up as:-
  
  ``````"((13-1)/2)*(3+5)"
  ``````
  
  you could treat "*" as a special case and omit it from the combined version.
  
  We start with an empty stack. Assuming the postfix expression is correct :
  
  • Read the atomic tokens and put them on stack
  • when you reach an operator, pop n elements from the stack where n is the arity of the operator, format it correctly, put the brackets around it and push the resolution back to the stack
  • when there's nothing to read, the stack should contain exactly one element with the result
  
  For instance :
  
  input : `2,3,+,5,-,8,*`
  
  Stack contains after each step :
  
  `````` 2
  2,3
  (2+3)
  (2+3),5
  ((2+3)-5)
  ((2+3)-5),8
  (((2+3)-5)*8)
  ``````
  
  This would be my approach
  
  ``````while(input.hasNext()) {
  if (symbol is operand) {
  stack.push(symbol)
  } else { // the symbol is an operator
  if (stack.count < 2) {
  ERROR too few operands
  } else {
  op2 = stack.pop();
  op1 = stack.pop();
  piece = "("+op1+symbol+op2+")";
  stack.push(piece);
  }
  }
  }
  
  if (stack.count == 1) {
  stack.pop() is the INFIX
  } else {
  ERROR
  }
  ``````
  
  Of course if you want to consider unary operators, the conditions have to be a little more structured to consider the stack with a single element
  
  Here is a full Ruby implementation of the algorithm mentioned:
  
  ``````#!/usr/bin/env ruby
  
  parts = gets.strip.split(/ +/)
  
  stack = [ ]
  
  parts.each do |part|
  if part =~ /\D/  # it's a binary operation
  right_operand = stack.pop
  left_operand = stack.pop
  stack.push("(#{left_operand} #{part} #{right_operand})")
  else             # it's a number
  stack.push(part)
  end
  end
  
  if stack.size == 1
  result = stack[0][1..-2]  # remove outer parentheses
  puts result
  exit(0)
  else
  puts "parse error, stack does not contain exactly one element"
  exit(1)
  end
  ``````
  
  Use like this:
  
  ``````echo '13 1 - 2 / 3 5 + *' | ruby postfix-to-infix.rb
  ``````
  
  This example produces the result:
  
  ``````((13 - 1) / 2) * (3 + 5)
  ``````