Mon, 28 Feb 1994 11:25:54 GMT

Related articles |
---|

Truth table evaluation philip@livenet.ac.uk (Philip Riebold) (1994-02-25) |

Re: Truth table evaluation norman@flaubert.bellcore.com (1994-02-26) |

Re: Truth table evaluation bcohen@cad721.intel.com (1994-02-26) |

Re: Truth table evaluation ashok@cse.iitb.ernet.in (1994-02-28) |

Newsgroups: | comp.compilers |

From: | ashok@cse.iitb.ernet.in (Ashok Sreenivas) |

Keywords: | optimize, theory |

Organization: | Computer-Sc-Dept, IIT-Bombay-76, INDIA |

References: | 94-02-189 |

Date: | Mon, 28 Feb 1994 11:25:54 GMT |

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.