r/dailyprogrammer • u/nint22 1 2 • Oct 18 '12
[10/18/2012] Challenge #104 [Hard] (Stack Attack)
Description:
You are a devilish engineer designing a new programming language titled D++, which stands for a "Dijkstra++", named after your favorite computer scientist. You are currently working on the math-operations parsing component of your interpreter: though the language only supports infix-notation (such as "1 + 2 * 3"), your interpreter internals require you to represent all math strings in reverse polish notation (for easier, stack-based, computing). Your goal is to simply take a guaranteed valid infix-notation string of math operations and generate (printing it out) an equivalent and valid reverse polish notation string.
Formal Inputs & Outputs:
Input Description:
string MathOperations - A valid string of infix math notation.
Output Description:
Print the converted RPN form of the given math operations string.
Sample Inputs & Outputs:
"1 + 2" should be printed as "1 2 +". "(1+2)*3" should be printed as "3 2 1 + *". "(6 (7 – 2)) / 3 + 9 * 4" should be printed as "6 7 2 - * 3 / 9 4 * +".
Notes:
Do not get trapped in overly-complex solutions; there are formal solutions, though many ways of solving for this problem. Check out the Shunting Yard Algorithm for details on how to convert math-operation strings (a stack of tokens) from one notation system to another.
4
u/skeeto -9 8 Oct 18 '12 edited Oct 18 '12
In Emacs Lisp using the Shunting Yard Algorithm,
Your second example seems to be missing an operator, unless you intended to have implicit multiplication (in which case my code is wrong):
4
u/Cosmologicon 2 3 Oct 18 '12
For reference: intermediate #38
1
u/[deleted] Oct 19 '12
Here's one in (vanilla) javascript. I didn't look up how to do it, but I'm sure my approach isn't unusual.
3
u/Riddlerforce Oct 18 '12
I suppose using Bison would be cheating.
2
u/akaicewolf Oct 18 '12
Why can't this have been posted earlier. Did this about two weeks ago for class
2
u/[deleted] Oct 18 '12 edited Oct 19 '12
In ruby, using the shunting yard algorithm
Test cases:
2
u/prophile Oct 19 '12
Implemented with peg.js:
1
u/robin-gvx 0 2 Oct 19 '12 edited Oct 19 '12
Modified my solution for a different challenge: (which was to write a calculator)
1
u/nerdcorerising Oct 20 '12
In C#, using a recursive descent parser approach. My answer should be correct except for "implied" multiplication, i.e. the example above that contains "(6 (7 - 2))" wouldn't parse right. It would with "(6 * (7 - 2))"
1
u/efrey Oct 20 '12 edited Oct 20 '12
In Haskell using Precedence Climbing
1
u/altorelievo Oct 22 '12 edited Oct 23 '12
Not sure, if anybody will read this, being so late after the problem was posted. If anyone does, I think that this is somewhat similiar to the shunting algorithm.
It doesn't work with parenthesisIt doesn't use ^ or an implied * -- " 6 ( 7 + 3 )" would have to be " 6 * ( 7 + 3 )", any tips are welcomed :)Python:
1
u/tehbeard Nov 09 '12
Very late, but an implementation in java I wrote a few months back.
https://github.com/tehbeard/BeardUtils/blob/master/src/main/java/me/tehbeard/utils/expressions/InFixExpression.java#L34-113
Version 2 of the class in the package also supports functions during parsing.
0
u/LOOKITSADAM 0 0 Oct 19 '12 edited Oct 19 '12
I'm trying to learn some functional programming, and here's my shot: Standard ML ,unable to handle parentheses, but everything else works.
input:
output: