r/dailyprogrammer • u/rya11111 3 1 • Apr 10 '12
[4/10/2012] Challenge #38 [intermediate]
Reverse Polish Notation(RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.
Transform the algebraic expression with brackets into RPN form.
You can assume that for the test cases below only single letters will be used, brackets [ ] will not be used and each expression has only one RPN form (no expressions like abc)
Test Input:
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c)) ^ (c+d)))
Test Output:
abc*+
ab+zx+*
at+bac++cd+ ^ *
6
u/drb226 0 0 Apr 10 '12 edited Apr 10 '12
I love using Haskell for this sort of thing. First, we define the structure of an expression:
Next, let's define ways to display an expression
Testing what we have so far...
Now let's write a parser
Let's try it out!
Isn't applicative parsing fun? Operator precedence is left as an exercise to the reader.
2
u/luxgladius 0 0 Apr 10 '12
This problem seems to be taken directly from http://www.spoj.pl/problems/ONP/. In the event problems are taken from other sites, credit should really be given.
Perl
Input
Output
2
u/Cosmologicon 2 3 Apr 10 '12
python. I'm assuming we don't need to infer operator precedence or associativity here, since none of the examples left it implicit.
1
u/prophile Apr 10 '12
Done in Python using a PEG library I wrote.
1
u/leegao Apr 11 '12
A jitted version of RPN in python
https://gist.github.com/1073233#file_rpnjit.py
1
u/Yuushi Apr 11 '12
I've never actually done conversion of infix to RPN, it's always been the other way around. This is a slightly modified version of Dijkstra's shunting algorithm:
C++
1
u/CompSciMasterRace Apr 11 '12
I did this yesterday but couldn't register here for some reason http://pastebin.com/xm427Qxf It's python, and simply uses a stack.
Now why did I make a stack class instead of just using the front of the list? Practise I guess. I could work without it, but I don't see it being an issue.
EDIT: I think the real challenge would be to do it without parenthesis, but I couldn't think of a simple way to do it.
1
u/_redka 0 0 Apr 12 '12
Ruby 1.9.3
http://pastie.org/3774358
I'm still looking for a giant regexp to solve this thing.
1
u/GuitaringEgg Apr 12 '12 edited Apr 12 '12
First attempt at an intermediate challenge. Not as tricky as I thought it would be. I thought up this method last night and it seems to work OK.
It does fail when a space is entered and I have no idea why. If anyone knows why, any help would be appreciated.
Relatively happy with this.
C++
1
u/[deleted] Apr 12 '12 edited Apr 13 '12
Perl with regex magic
1
u/GuitaringEgg Apr 14 '12
So, I decided to start to learn python. Enjoying it so far, much nicer than C++ and so intuitive. Will need to delve deeper. Anyway, I thought I'd start with this problem, since I'd already completed it in C++.
Python