// FILE: 00ab2.cpp
// PURPOSE: 2000 AB Exam: Question 2
//-----------------------------------------------------------------------
// COMPILATION INSTRUCTIONS: g++ and gxx 
// 1. FILES: apvector.h, apvector.cpp, apstring.h, apstring.cpp,
//    apqueue.h, apqueue.cpp, apstack.h, apstack.cpp
// 2. COMMAND LINE: g++ (or gxx) 00ab2.cpp apstring.cpp 
//-----------------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// Print out 2000 AB Exam Question 2 and implement your solutions
// to part a and part b as specified
//-----------------------------------------------------------------------
#include <iomanip.h>
#include "apstring.h"  
#include "apqueue.h"
#include "apstack.h"

enum TokenType {PLUS, TIMES, NUMBER};

struct Token {
  TokenType op;
  int value;
  Token(TokenType op2 = NUMBER, int value2 = 0);
};

Token::Token(TokenType op2, int value2) :
  op(op2), value(value2) {}


//=================================================
//  Part a. Complete operator<(), as started below.
//=================================================
bool operator < (const Token &lhs, const Token &rhs) {
  return false;
}

//======================================================
//  Part b. Complete InfixToPostfix(), as started below.
//======================================================
void InfixToPostfix(const apqueue<Token> &infixQ,
		    apqueue<Token> &postQ) {

}

void testLessThan(void);
void testInToPost(void);

int main() {
  apstring title("2000 AB Question 2");
  cout << "\n\n\n\n\n\n\n\n\n" 
       << setw(39 + title.length()/2) <<  title.c_str() << endl << endl;
  testLessThan();
  testInToPost();

  return 0;
}

void testLessThan(void) {
  cout << "Testing operator<(). "
       << "Expected output: true  false  true  false  true  false\n";
  Token plus(PLUS), times(TIMES), number(NUMBER, 75);
  cout << "Testing nodes with op fields (PLUS < TIMES): " 
       << ( (plus < times)? "true" : "false" ) << endl;
  cout << "Testing nodes with op fields (TIMES < PLUS): " 
       << ( (times < plus)? "true" : "false" ) << endl;
  cout << "Testing nodes with op fields (TIMES < NUMBER): " 
       << ( (times < number)? "true" : "false" ) << endl;
  cout << "Testing nodes with op fields (NUMBER < TIMES): " 
       << ( (number < times)? "true" : "false" ) << endl;
  cout << "Testing nodes with op fields (PLUS < NUMBER): " 
       << ( (plus < number)? "true" : "false" ) << endl;
  cout << "Testing nodes with op fields (NUMBER < PLUS): " 
       << ( (number < plus)? "true" : "false" ) << endl;
  cout << endl;
}

void testInToPost(void) {
  cout << "Testing InfixToPostfix()\n";
  apqueue<Token> inQ, postfixQ, tmp;
  Token t;
  // Building infix expression: 3 * 4 + 5 * 2 + 8
  //---------------------------------------------
  inQ.enqueue(Token(NUMBER, 3)); inQ.enqueue(Token(TIMES));
  inQ.enqueue(Token(NUMBER, 4)); inQ.enqueue(Token(PLUS));
  inQ.enqueue(Token(NUMBER, 5)); inQ.enqueue(Token(TIMES));
  inQ.enqueue(Token(NUMBER, 2)); inQ.enqueue(Token(PLUS));
  inQ.enqueue(Token(NUMBER, 8)); 
  tmp = inQ;
  cout << "Converting this infix expression to postfix:  ";
  while ( !tmp.isEmpty() ) { 
    tmp.dequeue(t);
    if ( t.op == PLUS ) cout << "+ ";
    else if ( t.op == TIMES ) cout << "* ";
    else // t.op == NUMBER
      cout << t.value << " ";
  }
  cout << "\nNumber of tokens: " << inQ.length() << endl;
  cout << "Expecting this postfix expression: "
       << "3 4 * 5 2 * + 8 + " << endl;
  InfixToPostfix(inQ, postfixQ);
  int len = postfixQ.length();
  tmp = postfixQ;

  cout << "Resulting postfix expression is:   ";
  while ( !tmp.isEmpty() ) { 
    tmp.dequeue(t);
    if ( t.op == PLUS ) cout << "+ ";
    else if ( t.op == TIMES ) cout << "* ";
    else // t.op == NUMBER
      cout << t.value << " ";
  }
  cout << "\nNumber of tokens: " << len << endl;
  //----------------------------------------------------
  // Building infix expression: 3 + 4 * 5 
  //---------------------------------------------
  inQ.makeEmpty();  tmp.makeEmpty();  postfixQ.makeEmpty();
  inQ.enqueue(Token(NUMBER, 3)); inQ.enqueue(Token(PLUS));
  inQ.enqueue(Token(NUMBER, 4)); inQ.enqueue(Token(TIMES));
  inQ.enqueue(Token(NUMBER, 5));
  tmp = inQ;
  cout << "Converting this infix expression to postfix:  ";
  while ( !tmp.isEmpty() ) { 
    tmp.dequeue(t);
    if ( t.op == PLUS ) cout << "+ ";
    else if ( t.op == TIMES ) cout << "* ";
    else // t.op == NUMBER
      cout << t.value << " ";
  }
  cout << "\nNumber of tokens: " << inQ.length() << endl;
  cout << "Expecting this postfix expression: "
       << "3 4 5 * + " << endl;
  InfixToPostfix(inQ, postfixQ);
  len = postfixQ.length();
  tmp = postfixQ;
  cout << "Resulting postfix expression is:   ";
  while ( !tmp.isEmpty() ) { 
    tmp.dequeue(t);
    if ( t.op == PLUS ) cout << "+ ";
    else if ( t.op == TIMES ) cout << "* ";
    else // t.op == NUMBER
      cout << t.value << " ";
  }
  cout << "\nNumber of tokens: " << len << endl << endl;
}