|Truth table evaluation email@example.com (Philip Riebold) (1994-02-25)|
|Re: Truth table evaluation firstname.lastname@example.org (1994-02-26)|
|Re: Truth table evaluation email@example.com (1994-02-26)|
|Re: Truth table evaluation firstname.lastname@example.org (1994-02-28)|
|From:||email@example.com (Ashok Sreenivas)|
|Organization:||Computer-Sc-Dept, IIT-Bombay-76, INDIA|
|Date:||Mon, 28 Feb 1994 11:25:54 GMT|
Philip Riebold (firstname.lastname@example.org) 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.
Dept. of Computer Sc. and Engg,
IIT, Bombay - 400 076.
Return to the
Search the comp.compilers archives again.