From: James Koppel <jamesbkoppel@...>
Date: 2007-12-03T01:40:44+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

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
  
  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
  
  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  
        (self.el==left.el and not LEFT_ASSOCS[left.el]))
    r= "(#{r})" if right.respond_to?(:el) and (PREC[right.el]<PREC[self.el] or 
        (self.el==right.el and not RIGHT_ASSOCS[right.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

puts TreeNode.from_postfix(ARGV.first.split(/ /)).to_minparen_infix

----- Original Message ----
From: Ruby Quiz <james@grayproductions.net>
To: ruby-talk ML <ruby-talk@ruby-lang.org>
Sent: Friday, November 30, 2007 7:28:17 AM
Subject: [QUIZ] Postfix to Infix (#148)


The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this
 quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps
 everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz
 message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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.






      ____________________________________________________________________________________
Get easy, one-click access to your favorites. 
Make Yahoo! your homepage.
http://www.yahoo.com/r/hs