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…