From: Ruby Quiz <james@...>
Date: 2007-12-06T21:34:59+09:00
Subject: [SUMMARY] Postfix to Infix (#148)

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 Koppel 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...