There are many different ways to write mathematical equations. Infix notation is probably the most popular and yields expressions like:
2 * (3 + 5)
Some people like to work with a postfix notation (often called Reverse Polish Notation or just RPN) though, which doesn't require parentheses for the same equation:
2 3 5 + *
You can compare the results of these equations using the Unix utilities bc (infix) and dc (postfix):
$ bc <<< '2 * (3 + 5)'
16
$ dc <<< '2 3 5 + * p'
16
The "p" instruction tacked onto the end of the expression for dc just tells it to print the result.
This week's quiz is to write a script that translates postfix expressions into the equivalent infix expression. In the simplest form, your script should function as such:
$ ruby postfix_to_infix.rb '2 3 +'
2 + 3
At minimum, try to support the four basic math operators: +, -, *, and /. Feel free to add others though. For numbers, remember to accept decimal values.
You can count on the postfix expressions having spaces between each term, if you like. While dc is content with 2 3+p, you don't have to support it unless you want to.
For an added bonus, try to keep the parentheses added to infix expressions to the minimum of what is needed. For example, prefer these results:
$ ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
56 * (34 + 213.7) - 678
$ ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
1 + (56 + 35) / (16 - 9)
to these:
$ ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
((56 * (34 + 213.7)) - 678)
$ ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
(1 + ((56 + 35) / (16 - 9)))
Posting equations and your output is not a spoiler.
Quiz Summary
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:
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:
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...
