Boolean algebra expressions

Hey all,

I'm trying to find components or a technique that allows manipulation of Boolean expressions that is not so complex that its unmanageable. Specifically I am looking for a way I could input a string such as A*(B+C) and it would simplify it down to AB+AC using the laws of boolean algebra.

I have been trying to work on this for a week or so and I cannot seem to get anywhere on this. I would appreciate any links, references, and/or oppinions on how I may achieve this.

Thanks!!!

You have several problems to overcome. First you need to be able to read in the data from your input source, then you need to parse it to individual tokens, validating that you only have acceptable tokens. Next you have to run through the tokens and note which ones are 'data' and which ones act on those data (which, I suppose, could be done as you parse the data), then you need to write logic to associate the 'active' tokens (appropriate names escape me) with blocks of data tokens. Once all that is done, then you can start running your algebra logic on the various token sets so you can simplify, reduce, whatever (I am a biochemist, I don't need math much higher than add/subtract/mult/divide). It sounds like a really challenging project, one I would expect to take a really experienced programmer much more than a week to code and test fully. You might want to look up some references on compiling, because after all, you are doing many of the same functions. The compiler books I have looked at have lots of math you might find familiar (just greek to me). If you want to continue trying to solve this yourself instead of googling for packages that surely exist to do these sorts of things, I recommend that you break it down into the elements I have listed and tackel them one at a time, testing and checking with each change to be sure nothing has introduced any bugs. Be sure to keep backups of your working code! C, and to a bit lesser extent C++, allows you almost total freedom to shoot yourself in the foot (or worse), so unless you are an experienced C programmer, you may want to consider a more forgiving language like Java (if you want to stick with C like syntax) so you can avoid some of the worst of the mistakes newbies tend to make.

Good luck!

A valid expression can only contain operands (variables), operators and parantheses.

For my particular project the only operators are logic gates (NOT, AND, NAND, OR, NOR, XOR, XNOR). I am only allowing 8 operands and to make it easier only A-H will be used. To validate my string I will check each character of the expression against a string "ABCDEFGH()!*&+|%#" that is made up of only the allowed characters.

The steps I feel are needed for my project are as follows:
1) Take a string expression
2) validate the string (check for allowed variables, operators, parantheses matching
3) parse the string into tokens (as you've said) and store tokens into some sort of data structure (leaning more toward binary trees at the moment)
4) use boolean algebra rules to minimize original expression....at this point i have 2 expressions (original and reduced)
5) draw both expressions using actual bitmaps of digital logic gates
6) misc operations (printing, saving, etc)

I feel confident in 1, 2, 5, and 6. Parsing and minimizing the original expression is what I am totally confused on how to tackle. Drawing might be difficult to but it's something I can definitely play with and solve.

I should explain that the main goal of this project is to visually compare the original expression with its minimized form. It is not to create digital circuits or anything (I will leave that to electrical engineers hehe )

I would guess that would be a full-time project for at least several months. I hope you are getting paid for this! What OS are you writing for? For me the challenge would be to do the bitmap design and printing, the parsing is not that different from other projects I have done. Are you planning on using C or C++? Since I don't expect this is a performance demanding process, I recommend C++ so you can take advantage of vectors, lists, maps, etc. as well as lots of other tools to avoid the need to manually deal with memory.