Linked List Tautology

[woodmaj]

Write a program that tells you if the expression entered is a
tautology or not. Assume that you have no more than three
propositional symbols in your expressions -- call them P, Q, R.
You must use the linked list implementation of the data
structures needed.

The above is my homework assignment. I am wondering if anyone has any idea where to start with this. I started writing a postfix -> infix linekd list stack example, and then thought I'd edit it, but I'm at a loss as to how you would get the values for the true/value?

Would I have to include the truth tables?

[Taywin]

OK, I do not have the total idea of how to do it because I have questions about your assignment. Do you have to handle parenthesis as well? Or the user must modify the way of entering the input?

//i.e.
// notice it is not -- (not P -> Q) and R
// but it is -- not P -> (Q and R)
Enter relationship of P,Q,R: not P -> Q and R
Enter P value: false
Enter Q value: true
Enter R value: false
// notice that the first proposition will return false, but the second one returns true

Anyway from my understanding, the way to do it is similar to do a multi-way tree; however in this case, the tree height is always 3 because there are only 3 propositional symbols. Each node of the tree is the value of P, Q, or R entered from left to right. Each node points to different node depending on the operator.

class TautologyNode {
  TautologyNode nextAndNode, nextOrNode, nextIfThenNode;
  boolean isNot, prevNodeValue, currNodeValue;
}

Then you can build as many propositional conditions as you like in the table as long as a user enter it from left to right. As above example I asked, it will not do it correctly because the user must change the way all symbols are entered.

[JamesCherrill]

You can define a tautology as a logical expression whose value is true for all possible combinations of input values. Since this exercise is limited to three input symbols you can construct a complete truth table - it only has 8 rows.
So maybe the approach is to parse the expression and store it as a LL (infix/postfix/ whatever suits you). Then write an expression evaluator to evaluate the expression for any given values of P Q R. Finally call the evaluator for all 8 possible combinations of P/Q/R true/false and see if all 8 evaluate to true.

[woodmaj]

James, I think that is exactly what I have to do. I'm not supposed to use a tree like the other posted suggested. Can you give me a hint on what to actually code for this?

Many thanks for your help

[JamesCherrill]

Sorry, but I don't have any code ideas to hand, and I don't really have time now to design something from scratch. All I can suggest is to code & test it in the three stages I implied in my first post - build & test the parser, build & test the evaluator, build & test the truth table. If you keep it simple and do one step at a time it shouldn't be too hard. I'll watch out for any design ideas or code you want checked out.