Help! Evaluating Many Logical Expressions (Dinesh Somkani)
10 Oct 1996 11:04:22 -0400

          From comp.compilers

Related articles
Help! Evaluating Many Logical Expressions (1996-10-10)
Re: Help! Evaluating Many Logical Expressions (1996-10-13)
| List of all articles for this month |

From: (Dinesh Somkani)
Newsgroups: comp.compilers,comp.programming
Date: 10 Oct 1996 11:04:22 -0400
Organization: NETCOM On-line Communication Services (408 261-4700 guest)
Keywords: optimize, question

Hi All

I have a requirement to evaluate, real-time, a logical expression made up
of many relational expressions.

The given expression looks something like this:
A && B && C
or, somewhat more complex, with lots of parentheses and all.
The A, B, C are the relational expressions. The data arrives in
transactions; one transaction can affect only one relational expression.
I may be able to place some reasonable limit on the number of components
to a logical expression (say, 20).

The problem is:
(a) how to verify that the given logical expression is meaningful -
detecting truisms like (A && ... && ~A), etc.
(b) how to structure the logical expression for evaluation. I have maybe
10000 of these at a time, built using say 100000 components.
(c) structuring - are there ways to simplify a logical expression so
that one keeps doing incremental evaluations (say left to right, or
perhaps in a tree) until there is a conclusive result.
(d) Any methods to reduce/normalize the expression, since (once
implemented) speed would become an issue sooner or later.

Would appreciate some help - a good reference or a cook book, pointer to
some standard algorithms, or whatever. I need to do this in C/++.

Please e-mail me directly at

Dinesh K Somani

Post a followup to this message

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