#include <iostream>
#include <strstream>
using namespace std;

#include "apstring.h"
#include "apqueue.h"
#include "apstack.h"

enum TokenType {PLUS, TIMES, NUMBER};

struct Token
{
    TokenType op;    // op == NUMBER means token represents a value
    int value;       // the value represented if op is NUMBER;
                     // otherwise undewfined
};

bool operator < (const Token& lhs, const Token& rhs)
{
    return lhs.op < rhs.op;
}

void InfixToPostfix(const apqueue<Token>& infixQ,
		    apqueue<Token>& postQ)
// pre: the sequence of tokens in infixQ represents a
//      valid infix expression using +, *, and integers;
//      postQ is empty
// post: the sequence of tokens in postQ represents a
//       valid postfix expression equivalent to the
//       infix expression represented by infixQ    
{
    apqueue<Token> tempQ = infixQ;
    apstack<Token> stack;
    Token tok;
    
    while (! tempQ.isEmpty())
    {
	tempQ.dequeue(tok);

	if (tok.op == NUMBER)
	{
	    postQ.enqueue(tok);
	}
	else
	{
	    while (! stack.isEmpty() &&
		   ! (stack.top() < tok) )
	    {
		postQ.enqueue(stack.top());
		stack.pop();
	    }
	    stack.push(tok);
	}
    }
    while (! stack.isEmpty())
    {
	stack.pop(tok);
	postQ.enqueue(tok);
    }
}

int main()
{
    apqueue<Token> q1, q2;
    apstring
}