From: Konrad Meyer <konrad@...>
Date: 2007-12-03T07:33:14+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

--nextPart3665733.80YLWN0RR7
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Quoth Ruby Quiz:
> The three rules of Ruby Quiz:
>=20
> 1.  Please do not post any solutions or spoiler discussion for this quiz=
=20
until
> 48 hours have passed from the time on this message.
>=20
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>=20
> http://www.rubyquiz.com/
>=20
> 3.  Enjoy!
>=20
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps=20
everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz=20
message,
> if you can.
>=20
> -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
=2D=3D-=3D-=3D
>=20
> There are many different ways to write mathematical equations.  Infix=20
notation
> is probably the most popular and yields expressions like:
>=20
> 	2 * (3 + 5)
>=20
> Some people like to work with a postfix notation (often called Reverse=20
Polish
> Notation or just RPN) though, which doesn't require parentheses for the s=
ame
> equation:
>=20
> 	2 3 5 + *
>=20
> You can compare the results of these equations using the Unix utilities bc
> (infix) and dc (postfix):
>=20
> 	$ bc <<< '2 * (3 + 5)'
> 	16
> 	$ dc <<< '2 3 5 + * p'
> 	16
>=20
> The "p" instruction tacked onto the end of the expression for dc just tel=
ls=20
it
> to print the result.
>=20
> This week's quiz is to write a script that translates postfix expressions=
=20
into
> the equivalent infix expression.  In the simplest form, your script should
> function as such:
>=20
> 	$ ruby postfix_to_infix.rb '2 3 +'
> 	2 + 3
>=20
> At minimum, try to support the four basic math operators:  +, -, *, and /=
=2E =20
=46eel
> free to add others though.  For numbers, remember to accept decimal value=
s.
>=20
> You can count on the postfix expressions having spaces between each term,=
 if=20
you
> like.  While dc is content with 2 3+p, you don't have to support it unles=
s=20
you
> want to.
>=20
> For an added bonus, try to keep the parentheses added to infix expression=
s=20
to
> the minimum of what is needed.  For example, prefer these results:
>=20
> 	$ 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)
>=20
> to these:
>=20
> 	$ 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)))
>=20
> Posting equations and your output is not a spoiler.

The obvious solution to removing all unnecessary parentheses is to remove a=
ll=20
possible permutations of them from a string, eval() them all, and check to=
=20
make sure they get the right number :-).

Just kidding,
=2D-=20
Konrad Meyer <konrad@tylerc.org> http://konrad.sobertillnoon.com/

--nextPart3665733.80YLWN0RR7
Content-Type: application/pgp-signature; name=signature.asc 
Content-Description: This is a digitally signed message part.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)

iD8DBQBHUzKtCHB0oCiR2cwRAvwfAJsHeX7XjfjrZACrStgfQ0njPTNEAQCff64f
/VBUj+tjMhvSEy8HdDMWeSA=
=9bBG
-----END PGP SIGNATURE-----

--nextPart3665733.80YLWN0RR7--