Boolean formulas

[The_Kermit]

Hey guys!
I'm trying to build a program that will evaluate boolean expressions. For example:
a>(b>(a^b)) or maybe ¬a>(a^b).
It doesn't really matter if you know boolean logic or not since i'm ok doing the calculations. The only part i'm struggling with is parsing the formula. I need to read in a formula entered into the command line and then split it into it's subformals. For the first example, the subformals would be:
b>(a^b)
a^b
a
b
These values, including the original formula, will then be stored in an array but for the life of me i can't get it to work. I've played around with stringTokenizer but very quickly realized that wasn't going to be of much use and i've also had a go with stream Tokenizer and attempted recursive descent parsing but to no avail. Any help will be much appreciated.

[brianlevine]

What problems are you running into? It sounds to me like some kind of recursion is the way to go. What's not working?

[The_Kermit]

Well, when i tried using string and stream tokenizer i just hit a bit of a brick wall. I realised stringtokenizer was way too basic since all i could really get it to do was use brackets as delimiters but this obviously didn't produce all the subformals that were required. For example, on the example i used in my original post, the subformal b>(a^b) was left out of the result set. streamTokenizer didn't seem much more useful and then when i played around with recursive descent parsing i just got kinda lost to be honest. I'm not really the best of coders and i'm not too sure how to proceed with the program. I feel like I may be missing something really obvious.

[brianlevine]

Kermit, here's a bit to get you started. First there are two kinds of operators unary and binary. Unary just means it effects a single expression and binary means it works on two.

So ¬ is unary
and > and ^ are binary

Then you have expressions which are either a single item like "a" or "b" or compound like
(a > b)

Any time you come to a compound expression you need to evaluate the smaller parts (note that a compound expression can be made up of other compound expressions. So this is a compound expression:
(a > b)
and here's another that's a compound expression made up of two compound expressions:
(a > b) > (b > c)

You'll need to keep track of parenthesis to tell whether it's compound or not. I think going character by character and keeping track of open and closed parentheses (to see whether you're inside a compound expression) is the way to go.

I hope that gets you started...

[The_Kermit]

Thanks for the advice! I was actually just thinking about doing this the way you just suggested. It's just turning the idea into working code... I'll have a mess around and see what I can come up with. Thanks again

[Ezzaral]

You might find that stacks are pretty handy for keeping track of those compound expressions.

[The_Kermit]

Hey guys, i've been playing around with this for a quite a while now and i'm still stuck. I've managed to get the program to split simple compound formulas like (a^b) v (b) but i can't get more complex compounds to work such as (a(b(a^b). It's the brackets that are doing it cause i can't get it to keep track of multiple opening brackets and have it know where the correct closing bracket is. *sigh*

[brianlevine]

Are you using stacks to keep track of how deep into a compound expression your in?

Post up some code and I'll take a look...