// FILE: stkQue.cpp
// PURPOSE: Stack and queue applications
//------------------------------------------------------------------
// FILES: must have Stackt.h, Stackt.cpp, Queue.h, Queue.cpp
// COMPILATION INSTRUCTIONS: g++ and gxx 
// COMMAND LINE: g++ (or gxx) stkQues.cpp
//------------------------------------------------------------------
#include <iomanip.h>
#include <stdlib.h>
#include <string>
#include "Stackt.cpp"
#include "Queuet.cpp"


template <class T>
void revStack(Stack<T> &s) {
  //postcond: WITHOUT using a vector or another 
  //   stack, the elements in s are reversed

}


template <class T>
void revQueue1(Queue<T> &q) {
  //postcond: WITHOUT using a vector or another 
  //  queue, the elements in q are reversed iteratively

}


template <class T>
void revQueue2(Queue<T> &q) {
  //postcond: WITHOUT using a vector or another 
  // queue, the elements in q are reversed recursively


}


bool isBalanced(const string &st) {
  //postcond: returns true when parens in st are 
  //   properly balanced: (() (() ()) ): but  
  //   false when not balanced correctly: (() ()))  : false

  return false;
}


bool isPalindrome(const string &st) {
  //postcond: returns true when expression in st is a 
  //   plaindrome: ABCCBA, madamimadam; 
  //   othrewise returns false 

  return false;
}


void testRevStack(void); 
void testRevQueue(bool);
void testRevQueue2(void);
void testBalanced(void);
void testIsPalindrome(void);
void menu(char &);
void cls(void);

int main() {
  char ch;
  do {
    cls();
    menu(ch);
    switch( ch ) {
    case '1': testRevStack(); break;
    case '2': testRevQueue(true); break;
    case '3': testRevQueue(false); break;
    case '4': testBalanced(); break;
    case '5': testIsPalindrome(); break;
    case '0': return 0;
    default: break;
    } // switch
    cout << "\nPress <ENTER>: "; cin.ignore(10, '\n');
  } while (ch != '0');
  return 0;
}

void menu(char &choice) {
  const int left = 21;
  const string PAD('\n' + string(left, ' '));
  cout << PAD << "     STACK/QUEUE APPLICATIONS";
  cout << PAD << "----------------------------------";
  cout << PAD << "Reverse a stack                  1";
  cout << PAD << "Reverse a queue (iteratively)    2";
  cout << PAD << "Reverse a queue (recursively)    3";
  cout << PAD << "Test for balanced parentheses    4";
  cout << PAD << "Test for palindrome              5";
  cout << PAD << "Quit program                     0";
  cout << PAD << "----------------------------------";
  cout << PAD << "       SELECTION==> ";
  cin.get(choice);
  cin.ignore(10, '\n');
  while ( choice < '0' || choice > '5' ) {
    cout << PAD << "*** Invalid choice. Try again: ";
    cin.get(choice);
    cin.ignore(10, '\n');
  }// while
} //*** menu


void loadStack(Stack<char> &s, int n) {
  string st("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
  if ( n > st.length() ) n = st.length() - 1;
  else n--;
  for (int k = n; k >= 0; k--) {
    s.push(st[k]);
  }
}


void loadQueue(Queue<char> &q, int n) {
  string st("ABCDEFGHIJKLMNOPQRSTUVWXYZ");
  if ( n > st.length() ) n = st.length();
  for (int k = 0; k < n; k++)
    q.enqueue(st[k]);
}


void testRevStack(void) {
  Stack<char> S;
  cls();
  loadStack(S, 6);
  cout << "S before revStack(S):";
  S.print();
  cout << "S after revStack(S): ";
  revStack(S);
  S.print();
  cout << endl << endl << endl;
  S.makeEmpty(); loadStack(S, 3);
  cout << "S before revStack(S):";
  S.print();
  cout << "S after revStack(S): ";
  revStack(S);
  S.print();
  cout << endl << endl << endl;
  S.makeEmpty();
  cout << "S before revStack(S): ";
  S.print();
  cout << "S after revStack(S):  ";
  revStack(S);
  S.print();
}


void testRevQueue(bool iterative) {
  Queue<char> Q;
  cls();
  loadQueue(Q, 5);
  cout << "Q before revQueue(Q) "
       << (iterative? "iterative: " : "recursive: ");
  Q.print();
  if ( iterative ) revQueue1(Q);
  else revQueue2(Q);
  cout << "Q after revQueue(Q) "
       << (iterative? "iterative:  " : "recursive:  ");
  Q.print(); cout << endl << endl;
  Q.makeEmpty(); loadQueue(Q, 4);
  cout << "Q before revQueue(Q) "
       << (iterative? "iterative: " : "recursive: ");
  Q.print();
  if ( iterative ) revQueue1(Q);
  else revQueue2(Q);
  cout << "Q after revQueue(Q) "
       << (iterative? "iterative:  " : "recursive:  ");
  Q.print(); cout << endl << endl;
  Q.makeEmpty();
  cout << "Q before revQueue(Q) "
       << (iterative? "iterative: " : "recursive: ");
  Q.print();
  if ( iterative ) revQueue1(Q);
  else revQueue2(Q);
  cout << "Q after revQueue(Q) "
       << (iterative? "iterative:  " : "recursive:  ");
  Q.print();
}


void testBalanced(void) {
  cls();
  string exp1("((25^3) - (4 - (7 - 17) + 1) + 1)");
  string exp2("((25^3) - (4 - (7 - 17) + 1) + 1");
  string exp3("((25^3) - 4 - (7 - 17) + 1) + 1)");
  cout << exp1 << ( isBalanced(exp1) ? " is" : " is not") 
       << " balanced\n\n";
  cout << exp2 << ( isBalanced(exp2) ? " is" : " is not") 
       << " balanced\n\n";
  cout << exp3 << ( isBalanced(exp3) ? " is" : " is not") 
       << " balanced\n\n";
}



void testIsPalindrome(void) {
  cls();
  string exp1("ABCDDCBA");
  string exp2("ABCDDQBA");
  string exp3("amanaplanacanalpanama");
  cout << "isPalindrome(" << exp1 << ") = "
       << ( isPalindrome(exp1) ? "true" : "false") << endl << endl;
  cout << "isPalindrome(" << exp2 << ") = "
       << ( isPalindrome(exp2) ? "true" : "false") << endl << endl;
  cout << "isPalindrome(" << exp3 << ") = "
       << ( isPalindrome(exp3) ? "true" : "false") << endl << endl;
}


void cls(void) {
  for (int k = 0; k < 55; k++)
    cout << endl;
}