# Postfix to Infix (#148)

**URL:** <https://www.ruby-forum.com/t/postfix-to-infix-148/122308>\
**Category:** Ruby\
**Created:** [December 6, 2007, 1:36pm UTC](https://www.ruby-forum.com/t/postfix-to-infix-148/122308 "2007-12-06T13:36:00Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 6, 2007, 1:36pm UTC](https://www.ruby-forum.com/t/postfix-to-infix-148/122308/1 "2007-12-06T13:36:00Z")

</div>

The big advantage of postfix expressions is that they are built with a  
stack in  
mind. This turns out to be a powerful way to do math both for computers  
and  
humans. HP makes some great RPN calculators that literally display a  
stack on  
the screen and give you the tools the manipulate it. To handle the  
expression:

2 3 +

on a calculator like that, you could type a two followed by the enter  
key to  
push the number onto the stack. Similarly, three and enter pushes that  
number,  
shifting the two up a slot. Finally, pressing the plus key pops two  
values from  
the stack, performs the requested operation, and pushes the result back  
onto the  
stack.

We can solve this problem just like that. We only need to change that  
final  
step to push an equivalent infix expression back to the stack, instead  
of some  
mathematical result. Here is some code from Jesús that does just that:

stack = []  
expr = ARGV.join(" ")  
expr.split(/ /).each do |x|  
case x  
when \*%w{+ \* - /}  
op2 = stack.pop  
op1 = stack.pop  
stack.push “(#{op1} #{x} #{op2})”  
else  
stack.push x  
end  
end  
puts stack.pop

Note that the first line creates the key data structure, our stack.  
From there  
the code iterates over each chunk of the expression. When the chunk  
isn’t an  
operator it must be a number and push()ed onto the stack by the else  
clause.  
For operators, two values are pop()ped, transformed into an infix  
String, and  
pushed back onto the stack. The first operand pop()ped is actually the  
right-hand side operand, so it’s important to remember to reverse them  
as Jesús  
does here. The final line of code just pop()s and prints the final  
element from  
the stack which will be our infix expression.

This code solves the problem and produces perfectly accurate  
translations. The  
only downside is that it adds a lot of parentheses to ensure the order  
of  
evaluation is handled correctly. While that’s not at all wrong, the  
expressions  
could be a little prettier if we drop some of the unneeded symbols.

To do that, we need to make our stack a little smarter. James K.  
sent in a  
solution that reads the postfix expression like we have already seen,  
but  
instead of building Strings as the results it builds a custom syntax  
tree  
object. That object is smart enough to convert itself into an infix  
expression  
with minimal parentheses. Let’s examine how that works.

Here’s the start of the code:

PREC = {:+ =\> 0,:- =\> 0,:\* =\> 1,😕 =\> 1,:% =\> 1,:^ =\> 2}  
LEFT\_ASSOCS = {:+ =\> true, :- =\> true, :\* =\> true, 😕 =\> true,  
:% =\> true, :^ =\> false}  
RIGHT\_ASSOCS = {:+ =\> true, :- =\> false, :\* =\> true, 😕 =\> false,  
:% =\> false, :^ =\> true}

class TreeNode  
attr\_accessor :el,:left,:right  
def initialize(el,left,right)  
@el,@left,@right=el,left,right  
end

```
# ...

```

We are looking at two things here. First, we have some tables for  
future checks  
against operator precedence and associativity. We will see how these  
get put to  
use when we examine the conversion code. Note that this code supports  
two  
additional operations: modulo division and exponents.

The rest of the code lays out the design for a node in the syntax tree.  
Each  
node has an element, or operator, as well as the subexpressions to the  
left and  
right. These subexpresions can be Float objects or additional nodes in  
the  
tree.

Here is the method that constructs the syntax tree:

```
# ...

def TreeNode.from_postfix(exp_arr)
  stack = []
  exp_arr.each do |exp_str|
    if PREC.keys.include? exp_str.to_sym
      op2,op1 = stack.pop,stack.pop
      stack.push(TreeNode.new(exp_str.to_sym,op1,op2))
    else
      stack.push(exp_str.to_f)
    end
  end
  stack.first
end

# ...

```

You’ve seen this code before. It’s almost identical to Jesús’s  
solution. The  
primary difference here is that the code is converting to Float and  
TreeNode  
objects, instead of working in Strings. The stack still guides the  
process, but  
the result is an abstract syntax tree.

Once we have a tree, we need the code to convert it to an infix  
expression:

```
# ...

def to_minparen_infix
  l,r = [left,right].map{|o|o.to_minparen_infix}
  l = "(#{l})" if left.respond_to?(:el) and
                  ( PREC[left.el]<PREC[self.el] or
                    ( PREC[self.el]==PREC[left.el] and
                      not LEFT_ASSOCS[self.el] ) )
  r= "(#{r})" if right.respond_to?(:el) and
                 ( PREC[right.el]<PREC[self.el] or
                   ( PREC[self.el]==PREC[right.el] and
                     not RIGHT_ASSOCS[self.el] ) )
  l+" #{self.el} "+r
end

```

end

class Float  
def to\_minparen\_infix  
if self%1==0  
to\_i.to\_s  
else  
to\_s  
end  
end  
end

# …

The conversion for a given node isn’t too hard to understand. First,  
convert  
the left and right subexpressions. For Floats this amounts to the  
helper method  
that Stringifies them with or without trailing decimal digits at the  
bottom of  
the code. For another TreeNode this is just a recursive process.

Once we have the minimal left and right subexpression the question  
becomes, do  
they need parentheses? The middle lines of TreeNode#to\_minparen\_infix  
sort this  
out. If a subexpression isn’t a simple Float (which won’t have an el()  
method)  
and it has a precedence lower than us or the same us when we aren’t a  
left  
associative operator, parentheses are added. A similar check then is  
made for  
the right side using the right associativity table. With any needed  
parenthesis  
in place, the expression is simply the left subexpression followed by  
our  
operator and the right subexpression.

The application code just needs to hand-off the argument to the program  
and  
trigger the conversion of the root node. The result of that conversion  
can be  
printed as a final infix expression with minimal parentheses. Here’s  
that code:

# …

puts TreeNode.from\_postfix(ARGV.first.split(/ /)).to\_minparen\_infix

thanks. My +

Tomorrow we will teach Ruby to tie knots in our words…