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…