CODEWITHSUNDEEP
booleanboolean-logicboolean-expression
hermann
hermann

Reputation: 6295

Converting conditions with parentheses to equivalents with no parentheses

I am developing an app where a user is able to add conditions to certain tasks.

For example he could have conditions a, b, c, d and combine them in a way where in the end it looks like :

(a AND b) OR ( c AND d )
OR
(a AND b AND c) or d
OR
(a AND !b) AND c OR !d

etc.

How can I convert these conditions to equivalents by removing parentheses?

Upvotes: 5

Views: 6960

Answers (3)

Meyer Jacobs
Meyer Jacobs

Reputation: 76

Every expression in Boolean Algebra can be converted into an equivalent expression, without parenthesis, using only AND, OR, and ! (unary NOT).

Here is a simple but inefficient algorithm:

Using the example expression (a OR !b) AND c,

  1. Build a truth table for every combination of truth values of the variables:

    | a | b | c | (a OR !b) AND c  |
| 0   0   0 | 0                |
| 0   0   1 | 1                |
| 0   1   0 | 0                |
| 0   1   1 | 0                |
| 1   0   0 | 0                |
| 1   0   1 | 1                |
| 1   1   0 | 0                |
| 1   1   1 | 1                |

  2. For every set of values where the expression is true (every row with 1 in the rightmost column), create an expression using ANDs and ! that evaluates to true only for that specific set of values.

    | a | b | c | (a OR !b) AND c  |
| 0   0   0 | 0                |
| 0   0   1 | 1                |  (!a AND !b AND c )
| 0   1   0 | 0                |
| 0   1   1 | 0                |
| 1   0   0 | 0                |
| 1   0   1 | 1                |  (a  AND !b AND c )
| 1   1   0 | 0                |
| 1   1   1 | 1                |  (a  AND b  AND c )

  3. Join the expressions with OR.

    (!a AND !b AND c ) OR (a  AND !b AND c ) OR (a  AND b  AND c )

  4. The resulting expression is rarely minimal, so you may want to apply some minimization techniques afterward.

    (!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c)
=
(!a AND !b AND c) OR (a AND c)
=
(!b AND c) OR (a AND c)

Ta-da!

It is important to note that building the truth table in step 1 is an O(2^n) operation (in number of variables), which is terrible. For cases with nontrivial numbers of variables, you'll probably want to use a different technique. The primary advantage of this algorithm is that it makes it very obvious how ANY expression can be transformed into the form you wanted.

Edit: To be clear, if you are using normal precedence rules you can remove the parenthesis in the final expression.

Upvotes: 6

Erik Eidt
Erik Eidt

Reputation: 26656

Not totally sure what the motivation is for the conversion to non-parenthetical equivalents, so I took it to mean that you're trying to establish an expressive capability (i.e. expression language) for the users to communicate their desired task conditions to your app.

You can't remove the need for parenthesis and still support arbitrarily complex expressions in a normal infix expression language having the normal operator precedence rules.

You have a few choices, I think:

  1. Support parenthesis. (They're not really that hard to parse.)

  2. Use an alternate relatively standard or well-known expression language that doesn't use parenthesis, such as Reverse Polish Notation, aka RPN. See http://en.wikipedia.org/wiki/Reverse_Polish_notation . RPN uses a postfix notation that allows users full control over operator precedence by positioning and stacking rather than using parenthesis. This comes at the expense of having to carefully (re)order the operands and operations. (There's no free lunch.)

  3. Limit the expressiveness of your language to some specific patterns that don't need parenthesis in a more normal (infix) language (having operator precedence).

And lastly, if you have a user interface to help the users compose their expressions (instead of textual language), you can do something like #2 above and use the order the users defines sub expressions to indicate operator precedence without the need for parenthesis. Basically your UI would be helping them build an expression tree.

Finally, if your question goes to how to remove parenthesis for the purposes of executing expressions, this is more like a code generation problem. Again, the stack of RPN can be useful. Or, you can translate the (potentially parenthetical) expressions into individual mini (e.g. three operand) statements explicitly connected by additional (in compiler lingo, temporary) variables. For example, (a + b) * c becomes t1 = a + b followed by final-result = t1 * c.

Upvotes: 0

joulesm
joulesm

Reputation: 642

You can use various properties of Boolean algebra to help simplify your expressions, but you might not be able to get rid of all the parentheses. The parentheses are necessary for some expressions because there is no order of operations for NOT, AND, and OR. Thus if you can't rearrange your expression to read from left to right, you will need parentheses.

Upvotes: 4

Related Questions