4

I have a string like string 

     s="(=> P (OR (AND A (NOT B)) (AND B (NOT A))))";

and convert it output the CNF of this string,like

( OR ( NOT P ) ( OR A B ) ) ( OR ( NOT P ) ( OR ( NOT B ) ( NOT A ) ) )

do I need to make a struct TreeNode to keep the value?

     struct TreeNode {
            string val;         // The data in this node.
            TreeNode *left;   // Pointer to the left subtree.
            TreeNode *right;  // Pointer to the right subtree.
            //TreeNode *farther;//should I use farther or not in convert to CNF?
      };

how to make it to CNF, which is conjunctive normal form? please give some algorithm detail. from my point of view, maybe use recursive function is better for solving this problem, but I still can not think out how to use recursion. Or you have other suggestion for solving this problem?

Rebecca
  • 111
  • 2
  • 12
  • Please do you own work. When you get stuck, ask a specific question. But here's a hint: "recursive descent parser". Another hint: What's the first thing that the program needs to do? – Jim Balter Apr 18 '13 at 19:30
  • I just want to know some algorithm and learn something from it, so that I can do my own work, I do not want someone to post source code for me. I do do really hard find useful information and still can not figure out, that's why I ask question here, am I wrong? – Rebecca Apr 18 '13 at 19:37
  • In the time you wrote that, you could have googled "recursive descent parser" and been long on your way. – Jim Balter Apr 18 '13 at 19:39
  • Rebecca, I've already posted an answer that should easily lead you to a complete program. – Jim Balter Apr 18 '13 at 19:54
  • @AdrianPanasiuk Hmmm .. actually the OP has asked two quite different questions ... we have each answered one of them. I'm voting to close as the headline only matches the second question. – Jim Balter Apr 18 '13 at 20:04
  • I think she asked the other question. Maybe her english is not perfect, but the post seems to be: "I have a string input that looks like s, now I have converted it to a tree like this and my implementation includes the following structure type definition. What is the general idea behind normalizing propositions I will later on apply to my representation?" – Adrian Panasiuk Apr 18 '13 at 20:14
  • @Rebecca, care to clarify your question? – Adrian Panasiuk Apr 18 '13 at 20:15
  • @AdrianPanasiuk Ah, I see. I took "I have convert it" as "I have to convert it" whereas apparently she meant "I have converted it". I do wish that people who come here for help and wouldn't be so sloppy and lazy with their questions ... it's not helpful. And when I wrote about recursive descent parsers, why didn't she say she had already done that? And she didn't say what `farther` is supposed to be or why she thinks it might be needed. – Jim Balter Apr 18 '13 at 20:23
  • @AdrianPanasiuk Actually, I wasn't wrong ... see the OP's comment on my question. – Jim Balter Apr 18 '13 at 21:23
  • @JimBalter Heh yeah, and I also found this http://stackoverflow.com/questions/16088344/how-to-convert-a-logic-expression-in-to-a-prefix-tree and http://stackoverflow.com/questions/16073637/temporary-pointer-point-to-a-using-vector-address , so she divided the problem into small questions, but I agree there's some carelessness to how she formulates questions and reacts to answers. – Adrian Panasiuk Apr 18 '13 at 21:29
  • @AdrianPanasiuk ,sorry for the confusion, actually My english is not very good, and as well as my algorithm, thanks for your answer very much! – Rebecca Apr 18 '13 at 21:31
  • "sorry for the confusion" -- how about eliminating it by providing the requested clarification. – Jim Balter Apr 18 '13 at 21:33
  • @JimBalter sorry for the confusion, I just want to get some help, as my english is not very good, sometimes, I can not get the idea of others answer – Rebecca Apr 18 '13 at 21:34
  • Rebecca, you have asked the same question many times, can't formulate it properly, and can't comprehend the answers. You are abusing SO ... please stop. If you need that much help, get a tutor. – Jim Balter Apr 18 '13 at 21:35
  • @Rebecca No prob. Like Jim Balter said, remember to use proper spelling and punctuation and edit the question if it seems vague for the community. That makes the interaction with the other users much more efficient. Also remember to use the accept answer feature in the correct manner - use it when an answer solves your question; until it does, don't accept an aswer and don't ask the same question in a new post. Instead, ask for clarification under the answer. Netiquette aside, what I think would best help you right now would be to leave your problem at hand aside and instead try to find some – Adrian Panasiuk Apr 18 '13 at 21:38
  • (@Rebecca cont'd:) introduction texts about grammars and grammar parsing. Preferably those, that provide exercises, which ask the reader to code a simple parser. You can ask for help with those exercises on StackOverflow if you get stuck. Completing the exercises should help you understand how you can code the convertion of your proposition string into a tree, what fields do you need to define in the tree node's struct etc. – Adrian Panasiuk Apr 18 '13 at 21:40

2 Answers2

4

Let's say you name your function CNF, taking a tree and returning the tree in CNF.

  1. First, replace equivalency p<=>q with AND(p=>q,q=>p) then replace implications p=>q with OR(q,NOT(p)).

  2. Convert to negation normal form: move all NOT operations down the tree, so that the NOT operations bind only to atoms (A, B).

  3. Then, the result of CNF(AND(x,y)) is simple: AND(CNF(x),CNF(y)), as it is CNF-like to have ANDs high in the tree.

  4. The result of CNF(OR(AND(x,y),z)) is a little bit more complicated. Here we will use the rule of distribution of disjunction over conjunction, which is OR(AND(x,y),z) is equivalent to AND(OR(x,z),OR(y,z)). In effect, CNF(OR(AND(x,y),z)) will be AND(OR(CNF(x),CNF(z)),OR(CNF(y),CNF(z)).

And you're done.

Adrian Panasiuk
  • 7,249
  • 5
  • 33
  • 54
  • so you algorithm is recursion or not? what about the imply (=>) in the bottom, X=>Y CNF:not x and Y, if the string is very long, things will be very complicated and a huge work – Rebecca Apr 18 '13 at 20:08
  • @Rebecca Adrian addressed implications. Yes, it's recursive ... any tree traversal is. Do you see "AND(CNF(x),CNF(y))", for instance? That's a recursive call of CNF. It's not all that much work for an experienced programmer. If you're not one, maybe you should start with a simpler problem. – Jim Balter Apr 18 '13 at 20:16
  • @Rebecca The algorithm's output will be exponential in terms of the size of the input in some cases, for example for `OR(AND(x_1,y_1),AND(x_2,y_2),...AND(x_n,y_n))` the result will be the conjunction of all clauses of the form `OR(z_1, z_2, ..., z_n)` with each `Z_i` being `X_i` or `Y_i`. – Adrian Panasiuk Apr 18 '13 at 20:21
  • @AdrianPanasiuk Im using the same approach you mentioned. But is possible to apply all the distributive laws in one traversal over the tree?. Mi problem is that something like a&b&c|d converts to ((a|d)&((b&c)|d)), so i have to do two traversals to have the desired: ((a|d)&((b|d)&(c|d))). Is that im doing something wrong or this is expected? – Wyvern666 Feb 22 '14 at 19:33
  • 1
    @Wyvern666 Try treating `AND` and `OR` as n-ary instead of binary -- so `a&b&c|d` becomes `OR(AND(a,b,c),d)` instead of `OR(AND(a,AND(b,c)),d)`. – Adrian Panasiuk Feb 23 '14 at 11:01
2

Simple recursive descent parser solution:

TreeNode* ParseExpression(const char*& p): If the string pointed to by p does not start with '(' then return ParseAtom(p), else move p past the '(', call ParseOperation(p), then move p past the ')' and return the value returned by ParseOperation.

TreeNode* ParseAtom(const char*& p): skip p past the atom (contiguous series of non-spaces). Return a TreeNode with the atom as value and NULL left and right.

TreeNode* ParseOperation(const char*& p): The string pointed to by p should start with an operator. Move p past the operator, then determine how many operands the operator takes. If one, Call ParseExpression(p) once; if two, call ParseExpression(p) twice. Then return a TreeNode with the operator as value and the results of the one or two ParseExpression calls as left and right (right should be NULL for an operator with only one operand).

Set a pointer pointing to the original string; call ParseExpression on that pointer; the return value is your tree and the pointer will point past the first expression in your string.

This addresses one of your questions: how to turn a string into a tree. Adrian Panasiuk addressed the other question, how to convert a tree to normal form. Since you're going to be doing additional tree transformations, "value" in your nodes should be called "op" or something like that to stand for "operator" (which is a reserved word in C++), and it should be an enum, not a string.

Jim Balter
  • 16,163
  • 3
  • 43
  • 66
  • so actually, there is no need to convert the string in a tree, which will make things complicated, right? would it be possible that I can use something like substr() and find() and strcpy() to make it into CNF? – Rebecca Apr 18 '13 at 20:39
  • 1
    @Rebecca Of course there's a need to convert the string to a tree, and I just told you how. – Jim Balter Apr 18 '13 at 21:22
  • Why would someone downvote this without explanation 8 years after it was posted? – Jim Balter Jun 30 '21 at 23:16