Asp Forum
Home
|
Login
|
Register
|
Search
Forums
>
comp.lang.ruby
Re: [QUIZ] Postfix to Infix (#148
James Koppel
12/3/2007 11:19:00 PM
My solution failed on "3 5 * 5 8 * /," but I think I found a few changes that fixed that. Here's more new solution:
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
(PREC[self.el]==PREC[left.el] and not LEFT_ASSOCS[self.el])) #change in this line
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])) #change in this line
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.rub...
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.
____________________________________________________________________________________
Be a better pen pal.
Text or chat with friends inside Yahoo! Mail. See how.
http://overview.mail....
Servizio di avviso nuovi messaggi
Ricevi direttamente nella tua mail i nuovi messaggi per
Re: [QUIZ] Postfix to Infix (#148
Inserendo la tua e-mail nella casella sotto, riceverai un avviso tramite posta elettronica ogni volta che il motore di ricerca troverà un nuovo messaggio per te
Il servizio è completamente GRATUITO!
x
Login to ForumsZone
Login with Google
Login with E-Mail & Password