CSCE 3110 Data Structures
Assigment  3
Total : 85 points
Issued: 02/19/2006
Due   : 03/05/2006
................................

1. (35) Implement a program to convert an infix expression to a postfix expression.
The operators include '(', ')', '+','-','*','\',mod. The operators follows the
usual precedence definition. The expression is entered from the standard input.
An example input infix expression: 23+7*((3+2)-2)E 
(use E to specify the end of the expression).


2. (35 points) Suppose we have four numbers 1,2,3,4 and 
an empty stack. We can only push each number
into the stack in the given order. We perform the following operations: 
push(1)-push(2)-pop()-push(3)-push(4)-pop()-pop()-pop(). These sequence of
operations will give us back the numbers in the following order:
2,4,3,1 which is a permutation of the original sequence. If there are
six numbers 1,2,3,4,5,6, can they be permutated into order 3,2,5,6,4,1 using the
method just described? Can they be permutated into order 1,5,4,6,2,3? If 
it is possible show how to do it.

Now given 10 numbers 1,2,3,4,5,6,7,8,9,10, is
a given permutation such as 10,9,2,3,5,6,7,1,4,8 obtainable using the method
just described?

Now implement an algorithm that asks for a number N which means 1,2,...N is given to you and
a permutation of the N numbers, then putouts a Yes or No as the answer to indicate
if the permutation is possible by performing the above described stack operations.
If the answer is yes, your program should also print the
operation sequence. Save the program in a file called permutationCheck.cpp. 


3. (15 points) Write a C++ class for the enqueue and dequeue 
operations in a queue implemented using two stacks.  The class should
support the common operations of a queue. You can either implement
a template or just implement a class for a queue of integers. Save
the program in files called iiqueueOf2Stacks.h and queueOf2Stacks.cpp. 
Please  write a testing program to demonstrate the operations that you implemented.



Submission instructions:  
   - write a README file including the answers to problems 1-3, and a 
     detailed note about the functionality of each of the above programs, 
     and complete instructions on how to run them.
   - make sure you include your name in each program and in the README file.
   - make sure all your programs are fully commented, and compile and run 
     correctly on the CSP machines.
   - submit your assignment by the due date using the 'project' program.
     class code is 3110s001 and the project name is stackQueue.