 |
Date: 2000 Mar 30
Due Thursday, 2000 Apr 06, at the beginning of class.
2000Apr05: In the section describing how to evaluate a reverse Polish expression, we used $. This is for expositional purposes only. In your code, the $ need not be placed on the stack and a $ will not be at the end of the expression.
2000Apr01: Specified that the user interface for the tautology checker may not be changed.
The textbook's chapter 6 covers defining templatized classes. Chapter 7 discusses stacks. Be sure to read Section 7.4, concentrating on reverse Polish notation expressions.
The gdb debugger permits running programs in ``slow motion,'' permitting examination of how a program runs. For information how to use gdb, see my short gdb notes or the notes at Stanford.
Here is a quick and dirty introduction to gdb.
You and possibly a CS1321 classmate are to implement a stack data structure capable of holding any element type. Then you are to write code using the stack to evaluate a Boolean expression written in reverse Polish notation. Combining this with distributed source code yields a program that checks Boolean expressions for tautologies.
A stack is a last-in/first-out data structure with objects arranged in linear order. That is, it permits easy access only from one end. Entries can be added or removed only at the rightmost end. For example, the STL stack class implements a stack.
Your implementation should support all the operations listed in Table 1. These operations are similar but not identical to those provided by the STL stack class.
You can choose any implementation strategy you like for your stack class except that you may not use the STL stack class or any implementation similar to the source code in the textbook. It should be possible to use your templatized class to create and manipulate stacks of ints, doubles, strings, bools, etc., with any number of elements.
Your implementation should correctly use dynamic memory (but why implement it using dynamic memory yourself?).
The typename keyword is also useful whenever the compiler cannot determine that an expression is a type. For example, it is sometimes necessary to write
A Boolean expression consists of variables, true, and false connected together by Boolean operators &&, ||, =>, !, and == and possibly parentheses. For example,
Intuitively, a well-formed expression has the correct number of operands and operators arranged in the correct order. It is defined recursively:
A well-formed expression is either true, false, a variable, or an expression p q &&, p q ||, p q =>, p q ==, or p !, where p and q are well-formed expressions.
To evaluate Boolean expressions, we need to be able to evaluate the simplest Boolean expressions.
Evaluating a reverse Polish notation is easy using a stack. See Figure 2. Initially, the stack is empty; for expositional purposes, we use $ to denote the bottom of the stack so we can tell it is empty. Initially, we start with the entire expression; we mark its end using a $ for expositional purposes only. The rules are:
In addition to Boolean expressions involving only true, false, and the operators described earlier, we can write Boolean expressions involving variables. Such an expression has a value for any assignment of Boolean values to its variables. For example, consider the expression p q ||. There are 22 ways of assigning values to its two variables since each variable can be either true or false. For each way of assigning values to p and q, we can then evaluate the resulting expression. The result is false if both p and q are false and true for the other three choices.
A tautology is a Boolean expression that evaluates to true for all possible ways of assigning values to its variables. For example,
Given a Boolean expression with N variables, one way of determining whether it is a tautology is to evaluate the 2N possible expressions resulting from assigning different combinations of Boolean values to the N variables. If all of them evaluate to true, the original expression is a tautology; otherwise it is not.
Write a function evaluate evaluating a Boolean expression without any variables. Given an expression in reverse Polish notation represented as vector of strings, it should return a pair of Booleans, the first indicating whether the expression was well-formed and, if well-formed, the second indicating the expression's value.
The provided code reads a Boolean expression with variables from the standard input and cycles through all possible variable assignments, invoking evaluate to determine the expression's value. If the expression is true for all assignments, the program indicates is a tautology. Otherwise, the program indicates it is not a tautology or is not well-formed.
The user-provided expression must be in reverse Polish notation with all variables, operators, and keywords separated by whitespace. Any whitespace-delimited set of characters that is not an operator, true, or false is a variable.
Write a templatized stack class. We have provided a minimal stack.h and test file. Add an evaluate function and any helper functions to the tautology checker. A prototype for evaluate is already included.
As for previous homeworks, working with other people during your planning phase is encouraged. For this homework, you are permitted to write the code, i.e., program, with one other person in CS1321. To learn the material, both of you should be actively involved in the programming. Failure to do so will almost certainly hurt your comprehension of the material in the rest of the course.
Each one- or two-person team of programmers should submit only its completed implementation, consisting of the files stack.h and tautology-checker.cc. You do not need to send any other files. Please send only text documents, do not send Microsoft Word documents, PDF documents, HTML documents, etc. Please include both your names and email addresses at the top of your program.
We will test your stack implementation using our own programs and our own choice of stack elements; we will also test your completed tautology-checker program. Please be sure your code compiles without warning when using g++ -Wall -pedantic. It should not be necessary to change the given tautology checker code, but, if you do, changing the user-interface will be considered incorrect.
See the submission details for information how to email the programs. Note that the CS computer configuration was recently changed. If you want to receive an automated reply acknowledging your submission, please read the submission WWW page. If a team of two are in different sections, submit exactly once to one of the two permissible email addresses.
Given a Boolean expression with v variables and n operators, our tautology checker requires O(2vn) time. While exponential running times are acceptable for small values of v, they quickly become infeasible. (This Perl program generates a tautology with the number of variables specified as its command-line argument. (After downloading it, make the file executable using chmod +x generate-tautology.pl.) Try using it to generate input for your tautology checker. To time the tautology checker program, use timer.h.)
Can we find a faster algorithm? No one has yet been successful. There is a family of NP-complete problems all of which are currently thought difficult to solve. We can prove that, if any of these problems could be solved in polynomial time, i.e., O(nk), for some fixed k, then all these problems can be solved in polynomial time. If we could prove one problem required more than polynomial time, all of them would. Satisfiability, i.e., ``Is there an assignment making the Boolean expression true?,'' is the most famous NP-complete problem. The tautology problem is at least as hard or harder than satisfiability so do not be frustrated by not finding a faster algorithm. For more information, read Foundations of Computer Science, by Alfred V. Aho and Jeffrey D. Ullman, ISBN 0-7176-8233-2, p. 649.
