From: Matthew Smillie <M.B.Smillie@...>
Date: 2006-06-05T21:20:52+09:00
Subject: Re: parsing a boolean expression

On Jun 5, 2006, at 7:32, Daniel Baird wrote:

> Hi all,
>
> I need to take a string typed by dirty users' fingers, that should  
> contain a
> boolean expression, like this:
>  one and (two or three or (four and five) or six) and (seven or eight)
> ..and parse it into some kind of sensible data structure, like a  
> tree or
> something.   Or reject it if it's mal-formed.
>
> I figure it might take me two or three days to write and debug from  
> scratch
> (..hey, I'm fairly new to Ruby :\ ), but I'm sure there's a library
> somewhere that will do the job.

Well, there is and there isn't.  If you know how to write grammars in  
yacc, then there's racc:
http://i.loveruby.net/en/projects/racc/doc/

If your input is always going to be as simple as the above (space- 
delimited tokens and parens), and you don't know anything about yacc,  
then there's the distinct possibility that you'll lose more time  
fiddling with it than you will writing your own parser.

Ferinstance, you could pretty easily add the 'missing' parens (after  
each operator to the end of the expression) to make it explicit, then  
change it to an s-expression by switching the order of the first  
token and operator in each sub-expression.  And an s-expression is  
basically a tree.  It would depend on what you want to do with it  
when you're done.

matthew smillie.