Back to Questions
3.2k
views3
comments
Convert infix to postfix expression
f#functional

Hi,
I want to write a converter who transforms an infix expression like "a+b-c" in postfix notation like "a b + c -"!
I only want to know how you would try to handle this, not the algorithm :-), how is your approach to this?

What elements of F# should I use? Discriminated Unions? Pattern Matching?
I already have an idea but I don't know if this is the correct one in the sense of functional programming :-).

Thank you for your help!

Greets
MarioTP

.

Hi,
If you're doing this more as an excercise, then starting with FParsec (and parser combinators) may be difficult. I found them hard to understand until I implemented them myself :-).

I think the general approach you can use is to define a discriminated union type to represent the expression. For example something like this:

1
2
3

type Expression = 
  | Variable of string
  | BinaryOperator of string * Expression * Expression

Then you need to turn the string you get as an input into a value of this discriminated union. For example:

1

let expr = BinaryOperator("+", Variable("a"), Variable("b")) // a + b

This could be done for example by writing a recursive function that finds the operator that will be applied as the last one and split the string into two sub-expressions. If you want to use more sophisticated techinque, you can use parser combinators (including FParsec). A good introduction is the following article: [link:www.cs.nott.ac.uk]

Once you'll have the expression represented as a discriminated union, you can write a recursive function that takes Expression as an input and generates the postfix form (for example, for BinaryOperator, you'll first recursively process both expressions and then print the "+" sign).

Hope this helps!
Tomas

By on 9/18/2009 6:30 AM ()

Hi Tomáลก,

I don't think parser combinators in general have to be difficult to learn. After all, many parser combinator libraries (including FParsec) are nothing more than a bunch of basic parser functions and higher-order helper functions with which you can implement a recursive descent parser. So, in principle understanding the concepts behind a parser combinator library shouldn't be much more difficult than, say, learning how to use List.fold.

What is indeed somewhat more difficult to understand is the general concept of a monad. However, IMHO there isn't really anything intrinsically monadic about parser combinator libraries in general, and you certainly don't need to know anything about monads to make productive use of a library like (the current version of) FParsec.* It is true that parser combinator libraries are popular applications of monads, but that doesn't mean that you have to study advanced papers on monadic parsing just to use a library like FParsec. (Though I definitely can emphasize with anyone whose first reaction upon hearing about monadic parser combinators is the urge to read more about monads and to implement a parser combinator library oneself ;-)

*) Unfortunately the current online documentation of FParsec lacks behind the implementation. The current (and soon-to-be-replaced) tutorial on the website still puts an emphasis on the monadic "parse {...}" notation even though the current version of FParsec (view src/ download) doesn't use it anymore internally. The future tutorial will mention the monadic syntax only in connection with porting Parsec grammars. Until the new tutorial is online, the best way to learn about FParsec probably is experimenting with the samples and reading the new reference docs.

Best regards,
Stephan

By on 9/18/2009 9:48 AM ()

Hi Mario,

FParsec (quanttec.com/fparsec) includes a configurable operator precedence parser, which seems ideal for this purpose.

Regards,
Stephan

By on 9/18/2009 12:44 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper