CSCI 495 Assignment 1
Solving Propositional Calculus

Deadline: Wednesday, 9 October 2002 (33% off for each day late).

Your program is to determine all possible combinations of truth assignments for the propositional calculus symbols in a sentence that will make the sentence true. If none do, the program should output that the sentence is unsolvable. The sentence is to be input to the program in normal infix notation, with parenthesis to indicate order of operations, e.g. (P & Q) > (R | S), where the operators are defined as follows:

The simplest way to do this is to first convert the expression into postfix notation, then evaluate it for each possible truth assignment. The algorithm for converting infix to postfix is as follows:
  1. Initialize an empty stack.
  2. Repeat the following until the end of the infix expression is reached.
    1. Get next input character in the infix expression.
    2. If character is
      1. A left parenthesis - Push it onto the stack.
      2. An operand - Display it.
      3. An operator - Push operator onto the stack.
      4. A right parenthesis - Pop and display stack elements until left parenthesis, which is not displayed.
  3. When the end of the infix expression is reached, pop and display stack items until stack is empty.

The postfix version of the example is P Q & R S | >. The algorithm to evaluate a postfix expression is as follows:

  1. Initialize an empty stack.
  2. Repeat the following until the end of the expression is encountered.
    1. Get the next character in the postfix expression.
    2. If character is
      1. An operand - Push it onto the stack.
      2. An operator -
        1. Pop the top two values from the stack.
        2. Apply the operator to the two values.
        3. Push the result back onto the stack.
  3. When the end of the expression is encountered, its value is on top of the stack.

Hand in your well-documented program and sample output showing reasonably complex expressions.