Re: Truth table evaluation

Philip Riebold (philip@livenet.ac.uk) writes:


: I have an application that generates arbitrary postfix boolean expressions
: such as


: a b AND c b NOT AND OR END


: ... I need to evaluate the truth table for the expression.


As it happens, we did a very similar thing for one of our course projects
here. The approach we adopted was to, in some sense "minimise" the
expression that has to be evaluated. We did this by first reducing the
expression to have only two operators (in our case AND and XOR - all the
others can be expressed as combinations of these). Then we "flattened"
our expression tree so that it looked like this :


            XOR ( t1, t2, ... tn)


where each of the ti is either a leaf node or a AND node. Within each of
these subtrees (XOR or AND), we then sorted the operands and applied
trivial reduction rules (such as x XOR x = F, x AND x = x etc.). The
final form is the "minimal" form of the expression, on which you can then
try all combinations of values etc.


Hope this helps.


- Ashok.


Ashok Sreenivas,
Dept. of Computer Sc. and Engg,
IIT, Bombay - 400 076.
(ashok@cse.iitb.ernet.in)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.