Truth table evaluation

Philip Riebold <philip@livenet.ac.uk>
Fri, 25 Feb 1994 16:43:04 GMT

          From comp.compilers
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)
Truth table evaluation, summary and thanks philip@livenet.ac.uk (Philip Riebold) (1994-03-04)
| List of all articles for this month |
Newsgroups: comp.compilers
From: Philip Riebold <philip@livenet.ac.uk>
Keywords: logic, question
Organization: Compilers Central
Date: Fri, 25 Feb 1994 16:43:04 GMT

[apologies that this query hasn't got that much to do with compilers but I
thought some compiler techniques might be applicable]


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


a b AND c b NOT AND OR END


There are up to 16 different variables in each expression and each
variable may occur more than once.


I need to evaluate the truth table for the expression. At present I use a
straightforward method of evaluating the expression for each of the
possible combination of the variables. For 16 variables this takes ~3
seconds on a SUN IPC.


Are there any ways I can speed this up ? There are special case rules I
can apply if all the operators are the same but I am looking for methods
which work in the general case.


Any help/suggestions would be appreciated.


Philip
--

Post a followup to this message

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