Parsing Parentheses in Propositional Logic Program

Question

I'm working on translating a propositional logic statement to conjunctive normal form. The issue I'm having is parsing through the possibly complicated parentheses levels. The question I need to solve is the right order and I think recursion should be used to solve the inner parentheses first before moving outward but I can't figure out how to implement my ideas. The program is written in Java. Can anyone help?

Answer 1

Can you give an example of the statement you're converting to CNF? I'm thinking you mean there are parentheses in the starting logic statement, but it would help to see.

In the meantime, I'll say you don't need recursion... but a stack would be very helpful : ) Push items and their mathematical operations onto the stack, then pop them off and act on them when appropriate. Since it's homework I won't go into too much detail, but you'll find that you'll push-push-push-pop-multiply-push-push-pop-add-pop-divide... use the stack as a way of focusing on the current operation.

An investigation into Postfix Notation is also relevant and may help... even the wikipedia article on it will give you some ideas (though there are absolutely more computer-science-oriented articles out there).

Disclaimer: I put no thought into the number or order of those pushes and pops in my example : )

Update

You don't need more than one pass through the data, and you can convert to CNF on the fly.

You're heading in the right direction, so some help/hints:

• Use two stacks, one for the operands and one for the operators.
• When you have two operands and an operator, you pop the operands, apply the operator, and push the result back as a new (consolidated) operand
• The advantage of postfix is that you can do your conversion on the fly... for example, when you encounter a →, apply a ¬ to the operand stack and push a ⋁ onto the operator stack

Taking a reduction of your example:

F→(E⋀(A→B))

The first steps of the conversion looks like this (I'm assuming you've got the underlying logic-conversion rules down pat, and that it's just the code you're working out):

F→(E⋀(A→B))
¬F⋁(E⋀(A→B))
¬F⋁(E⋀(¬A⋁B))

In CNF postfix, it will look like this:

F¬EA¬B⋁⋀⋁     // (Parentheses are obviated in postfix notation)

To get there, read through your initial logic statement in one pass from left to right... Push operands onto the Operands stack, and operators onto the Operators stack.

As you apply the Operators, pop the required operands from the Operands stack, apply the operator, and push the resulting string back to the stack as a new operand.

Closing parentheses or lower-precedence operations trigger the pop-apply-push. The whole thing looks like this:

                                      Operand        Operator
                                       Stack          Stack
                                     ----------     ----------
Read F:  Push onto Operand stack     F ........      ..........

Read →:  On-the-fly conversion (𝑥→𝑦 becomes ¬𝑥⋁𝑦)
  Unary Operator ¬ pops F from Operands; applies it; pushes back to Operands
                                     ¬F .......      ..........   
  Push ⋁ onto the op-stack           ¬F .......      ⋁ .......    

Read (:  Discard    

Read E:  Push onto Operands stack    ¬F E ....       ⋁ ...... 
Read ⋀:  Push onto Operators stack   ¬F E ....       ⋁⋀ .....

Read (:  Discard                    
Read A:  Push onto Operands stack    ¬F E A ..       ⋁⋀ .....

Read →:  On-the-fly conversion (𝑥→𝑦 becomes ¬𝑥⋁𝑦)
  Unary Operator ¬ pops A from Operands; applies; pushes back to Operands
                                     ¬F E ¬A .       ⋁⋀ .....
  Push ⋁ onto Operators stack        ¬F E ¬A .       ⋁⋀⋁ ....

Read B:  Push onto Operands stack    ¬F E ¬A B       ⋁⋀⋁ ....

Read ):  Triggers Operators/Operands pop; applies; pushes back to Operands 
        (After, there are three operands on the Operands stack)
                                     ¬F E (¬A⋁B)    ⋁⋀ ....

Read ):  Triggers Operators/Operands pop; applies; pushes back to Operands
        (After, there are two operands on the Operands stack)
                                     ¬F (E⋀(¬A⋁B))  ⋁ ....

No more reads:  Final Operators/Operands pop/apply/push (result is output)
                                    ¬F⋁(E⋀(¬A⋁B))  

Caveats and notes:

This is just a start in the right direction... you'll have to deal with issues like operator precedence (i.e. do you push and act later, or pop and act now). You'll find your decision is based on the next character you read (and not on the closing parenthesis, as I've implied above).

It sounds more complicated than it is... pseudo-code for the above wouldn't be more than 12-15 lines. However, there are complexities I haven't addressed... the <--> function will have to be modeled in a way similar to → is above... you'll have to take this line of thinking and implement all of the conversion rules.

Implied parentheses can trip you up, e.g.

6 * (8 * 6) + 4

is really

(6 * (8 * 6)) + 4

If you don't handle operator precedence correctly, you might end up with something like

686*4+*

Which gives you 312, instead of the correct answer (292).

If you have trouble reading the unicode logic symbols in this post, let me know; I can redo it with standard characters, but it reads so much nicer in uni : )

HTH,
James

PS: A nifty little applet illustrating postfix is here:
http://fac-web.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/

Answer 2

Pseudocode:

parseRestOfString (int openParens, String rest) { 
    c = rest (0);
    if (c == ')' && openParens == 0) ...

Does that give you a hint?

Answer 3

Take a look at this:

Recursive descent parser

JavaCC