C++ code for a RPN (Reverse Polish Notation) Calculator

calc.cpp

/* calc.cpp
 *
 * The RPN calculator program
 * EECS 280 Project 5
 *
 * By: Ryan Su
 * uniqname: rysu
 */


#include "Stack.h"
#include "Rational.h"
#include <iostream>
#include <sstream>
#include <cmath>
#include <string>
#include <cassert>

using namespace std;

//Function Protypes==========================================

//Adition operator, +
void add(Stack<Rational> &s);
//Subtract operaror, -
void sub(Stack<Rational> &s);
//Mutliplication operator, *
void mult(Stack<Rational> &s);
//Division operator, /
void div(Stack<Rational> &s);
//duplicate operator, d
void dup(Stack<Rational> &s);
//reverse operator, r
void rev(Stack<Rational> &s);
//print operator, p
void print(Stack<Rational> &s);
//clear operator, c
void clear(Stack<Rational> &s);
//print all operator, a
void print_all(Stack<Rational> &s);
//negate operator, n
void neg(Stack<Rational> &s);
//match operator, m
void match(Stack<Rational> &s);


//Helper Function prototypes==================================

//functor for match
//Modifies: Stack
//Effects: Returns true if constructed r is = to passed in num1
class equalTo
{
	Rational r;
	public:
	//equalTo constructor
	equalTo(Rational r_in) : r(r_in) {}

	bool operator() (Rational num1)
	{
		if(num1 == r)
		{
			return true;
		}
		return false;
	}
};

//determines which operation to use
void determine_op(string op, Stack<Rational> &s, bool &end);


//Function Main================================================

int main()
{
	//create the stack of rational numbers
	Stack<Rational> s;

	string read_char;
	bool end = false;
	while(cin >> read_char)
	{
		determine_op(read_char, s, end);
		if(end == true)
		{
			break;
		}
	}

	return 0;
}

//Function Prototypes=========================================

//Requires: This requires a stack with at least two operands.
//Modifies: Stack
//Effects: Pop the top two numbers off the stack, add them together, and push 
//the result onto the top of the stack. 
void add(Stack<Rational> &s)
{
	//Check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational sum = num1 + num2;
	s.push(sum);
}

//Requries: This requires a stack with at least two operands.
//Modfies: Stack
//Effects: Pop the top two numbers off the stack, subtract the first number popped from the
//second, and push the result onto the top of the stack. 
void sub(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational diff = num2 - num1;
	s.push(diff);
}

//Requires: This requires a stack with at least two operands.
//Modifies: Stack
//Effects: Pop the top two numbers off the stack, multiply them together, and push the result onto
//the top of the stack. 
void mult(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational prod = num1 * num2;
	s.push(prod);
}

//Requires: This requires a stack with at least two operands. 
//Modifies: Stack
//Effects: Pop the top two numbers off the stack, divide the second value popped number by the
//first, and push the result onto the top of the stack. 
void div(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational quot = num2 / num1;
	s.push(quot);
}	

//Requires: This requires a stack with at least one operand.
//Modifes: Stack
//Effects: Pop the top item off the stack and push two copies of the number onto the top
//of the stack. 
void dup(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//effect
	Rational num = s.pop();
	s.push(num);
	s.push(num);
}

//Requires: This requires a stack with at least two operands
//Modifies: Stack
//Effects: Pop the top two items off the stack, push the first popped item onto the top of
//the stack and then the push the second item onto the top of the stack (this just reverses
//the order of the top two items on the stack). 
void rev(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effects
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	s.push(num1);
	s.push(num2);
}

//Requires: A stack with at least one operand
//Modifies: stdout
//Effects: Print the top item on the stack to the standard output, followed by a newline.
void print(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//Effect
	cout << s.top() << endl;
}

//Requires: This input is always valid.
//Modifies: Stack
//Effects: Pop all items from the stack. 
void clear(Stack<Rational> &s)
{
	Rational holder;
	while(!s.empty())
	{
		holder = s.pop();
	}
}

//Requires: n/a
//Modifies: stdout
//Effects: Print all items on the stack in one line, from top-most to bottom-most, each
//value followed by a single space. The end of the output must be followed by exactly one
//newline. This input is always valid and leaves the stack unchanged. For an empty stack,
//for example, only the newline will be printed.
void print_all(Stack<Rational> &s)
{
	cout << s;
	cout << endl;
}

//Requires: Stack not empty
//Modifies: Stack
//Effects: Negate the top item on the stack
void neg(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//Effect
	Rational num = s.pop();
	num = num * Rational(-1, 1);
	s.push(num);

}
//Requires: This requires at least one operand.
//Modifies: Stack
//Effects: Pop the top element off the stack. Then, push onto the stack a value equal to the
//number of times this element occurs in the remaining stack.  
void match(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//Effect

	//Generate functor
	equalTo func(s.pop());
	int counter = s.count_if(func);
	s.push(Rational(counter));

}



//Helper function implementation=============================

void determine_op(string op, Stack<Rational> &s, bool &end)
{
	if(op == "+")
	{
		add(s);
	}
	else if(op == "-")
	{
		sub(s);
	}
	else if(op == "*")
	{
		mult(s);
	}
	else if(op == "/")
	{
		div(s);
	}
	else if(op == "d")
	{
		dup(s);
	}
	else if(op == "r")
	{
		rev(s);
	}
	else if(op == "p")
	{
		print(s);
	}
	else if(op == "c")
	{
		clear(s);
	}
	else if(op == "a")
	{
		print_all(s);
	}
	else if(op == "n")
	{
		neg(s);
	}
	else if(op == "m")
	{
		match(s);
	}
	else if(op == "q")
	{
		end = true;
	}
	else //its a num!
	{
		int val = atoi(op.c_str());
		s.push(Rational(val));
	}
}

list.h

/* calc.cpp
 *
 * The RPN calculator program
 * EECS 280 Project 5
 *
 * By: Ryan Su
 * uniqname: rysu
 */


#include "Stack.h"
#include "Rational.h"
#include <iostream>
#include <sstream>
#include <cmath>
#include <string>
#include <cassert>

using namespace std;

//Function Protypes==========================================

//Adition operator, +
void add(Stack<Rational> &s);
//Subtract operaror, -
void sub(Stack<Rational> &s);
//Mutliplication operator, *
void mult(Stack<Rational> &s);
//Division operator, /
void div(Stack<Rational> &s);
//duplicate operator, d
void dup(Stack<Rational> &s);
//reverse operator, r
void rev(Stack<Rational> &s);
//print operator, p
void print(Stack<Rational> &s);
//clear operator, c
void clear(Stack<Rational> &s);
//print all operator, a
void print_all(Stack<Rational> &s);
//negate operator, n
void neg(Stack<Rational> &s);
//match operator, m
void match(Stack<Rational> &s);


//Helper Function prototypes==================================

//functor for match
//Modifies: Stack
//Effects: Returns true if constructed r is = to passed in num1
class equalTo
{
	Rational r;
	public:
	//equalTo constructor
	equalTo(Rational r_in) : r(r_in) {}

	bool operator() (Rational num1)
	{
		if(num1 == r)
		{
			return true;
		}
		return false;
	}
};

//determines which operation to use
void determine_op(string op, Stack<Rational> &s, bool &end);


//Function Main================================================

int main()
{
	//create the stack of rational numbers
	Stack<Rational> s;

	string read_char;
	bool end = false;
	while(cin >> read_char)
	{
		determine_op(read_char, s, end);
		if(end == true)
		{
			break;
		}
	}

	return 0;
}

//Function Prototypes=========================================

//Requires: This requires a stack with at least two operands.
//Modifies: Stack
//Effects: Pop the top two numbers off the stack, add them together, and push 
//the result onto the top of the stack. 
void add(Stack<Rational> &s)
{
	//Check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational sum = num1 + num2;
	s.push(sum);
}

//Requries: This requires a stack with at least two operands.
//Modfies: Stack
//Effects: Pop the top two numbers off the stack, subtract the first number popped from the
//second, and push the result onto the top of the stack. 
void sub(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational diff = num2 - num1;
	s.push(diff);
}

//Requires: This requires a stack with at least two operands.
//Modifies: Stack
//Effects: Pop the top two numbers off the stack, multiply them together, and push the result onto
//the top of the stack. 
void mult(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational prod = num1 * num2;
	s.push(prod);
}

//Requires: This requires a stack with at least two operands. 
//Modifies: Stack
//Effects: Pop the top two numbers off the stack, divide the second value popped number by the
//first, and push the result onto the top of the stack. 
void div(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effect
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	Rational quot = num2 / num1;
	s.push(quot);
}	

//Requires: This requires a stack with at least one operand.
//Modifes: Stack
//Effects: Pop the top item off the stack and push two copies of the number onto the top
//of the stack. 
void dup(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//effect
	Rational num = s.pop();
	s.push(num);
	s.push(num);
}

//Requires: This requires a stack with at least two operands
//Modifies: Stack
//Effects: Pop the top two items off the stack, push the first popped item onto the top of
//the stack and then the push the second item onto the top of the stack (this just reverses
//the order of the top two items on the stack). 
void rev(Stack<Rational> &s)
{
	//check requires
	int size = s.size();
	assert(size >= 2);

	//Effects
	Rational num1 = s.pop();
	Rational num2 = s.pop();
	s.push(num1);
	s.push(num2);
}

//Requires: A stack with at least one operand
//Modifies: stdout
//Effects: Print the top item on the stack to the standard output, followed by a newline.
void print(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//Effect
	cout << s.top() << endl;
}

//Requires: This input is always valid.
//Modifies: Stack
//Effects: Pop all items from the stack. 
void clear(Stack<Rational> &s)
{
	Rational holder;
	while(!s.empty())
	{
		holder = s.pop();
	}
}

//Requires: n/a
//Modifies: stdout
//Effects: Print all items on the stack in one line, from top-most to bottom-most, each
//value followed by a single space. The end of the output must be followed by exactly one
//newline. This input is always valid and leaves the stack unchanged. For an empty stack,
//for example, only the newline will be printed.
void print_all(Stack<Rational> &s)
{
	cout << s;
	cout << endl;
}

//Requires: Stack not empty
//Modifies: Stack
//Effects: Negate the top item on the stack
void neg(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//Effect
	Rational num = s.pop();
	num = num * Rational(-1, 1);
	s.push(num);

}
//Requires: This requires at least one operand.
//Modifies: Stack
//Effects: Pop the top element off the stack. Then, push onto the stack a value equal to the
//number of times this element occurs in the remaining stack.  
void match(Stack<Rational> &s)
{
	//check requires
	assert(!s.empty());

	//Effect

	//Generate functor
	equalTo func(s.pop());
	int counter = s.count_if(func);
	s.push(Rational(counter));

}



//Helper function implementation=============================

void determine_op(string op, Stack<Rational> &s, bool &end)
{
	if(op == "+")
	{
		add(s);
	}
	else if(op == "-")
	{
		sub(s);
	}
	else if(op == "*")
	{
		mult(s);
	}
	else if(op == "/")
	{
		div(s);
	}
	else if(op == "d")
	{
		dup(s);
	}
	else if(op == "r")
	{
		rev(s);
	}
	else if(op == "p")
	{
		print(s);
	}
	else if(op == "c")
	{
		clear(s);
	}
	else if(op == "a")
	{
		print_all(s);
	}
	else if(op == "n")
	{
		neg(s);
	}
	else if(op == "m")
	{
		match(s);
	}
	else if(op == "q")
	{
		end = true;
	}
	else //its a num!
	{
		int val = atoi(op.c_str());
		s.push(Rational(val));
	}
}

Rational.cpp

/* Rational.cpp
 *
 * Representation of a rational number
 * EECS 280 Project 5
 *
 * By: Ryan Su
 * uniqname: rysu
 */

#include "Rational.h"
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cmath>

using namespace std;

//Rational Class Implementation========================================

Rational::Rational() :
numerator(0), denominator(1) {}

Rational::Rational(int val) :
numerator(val), denominator(1) {}

Rational::Rational(int numerator_in, int denominator_in) :
numerator(numerator_in), denominator(denominator_in) 
{
	
	//check if denominator is negative
	if(denominator_in < 0)
	{
		denominator_in = denominator_in * -1;
		numerator_in = numerator_in * -1;
	}

	//simplify the numerator and denominator
	if(numerator != 0 && denominator != 0)
	{
		for(int i = abs(numerator_in) * abs(denominator_in); i > 1; --i)
		{
			if(numerator_in % i == 0 && denominator_in % i ==0)
			{
				numerator_in = numerator_in / i;
				denominator_in = denominator_in / i;
			}
		}		
	}
	else if(numerator_in == 0 && denominator_in > 0)
	{
		denominator_in = 1;
	}
	else if(denominator == 0 && numerator_in > 0)
	{
		numerator_in = 1;
	}
	else if(denominator_in == 0 && numerator_in < 0)
	{
		numerator_in = -1;
	}


	numerator = numerator_in;
	denominator = denominator_in;

}

int Rational::get_numerator() const
{
	return numerator;
}

int Rational::get_denominator() const
{
	return denominator;
}

//Function Implementations==============================================

ostream& operator<<(ostream &os, const Rational& obj)
{
	int numer = obj.get_numerator();
	int denom = obj.get_denominator();
	if(numer == 0 && denom != 0)
	{
		os << "0";
	}
	else if(denom == 0 && numer > 0)
	{
		os << "infinity";
	}
	else if(denom == 0 && numer < 0)
	{
		os << "-infinity";
	}
	else if(denom == 0 && numer == 0)
	{
		os << "undefined";
	}
	else if(denom == 1)
	{
		os << numer;
	}
	else
	{
		os << numer << "/" << denom;
	}
	return os;
}

Rational operator+(const Rational &lhs, const Rational &rhs)
{
	int left_numer = lhs.get_numerator();
	int left_denom = lhs.get_denominator();
	int right_numer = rhs.get_numerator();
	int right_denom = rhs.get_denominator();

	// (a/b + c/d)'s (ad+bc)
	int new_numer = ((left_numer * right_denom) + 
		(right_numer * left_denom));
	// (a/b + c/d)'s (bd)
	int new_denom = left_denom * right_denom;

	return Rational(new_numer, new_denom);
}

Rational operator-(const Rational &lhs, const Rational &rhs)
{
	int left_numer = lhs.get_numerator();
	int left_denom = lhs.get_denominator();
	int right_numer = rhs.get_numerator();
	int right_denom = rhs.get_denominator();

	// (a/b - c/d)'s (ad-bc)
	int new_numer = ((left_numer * right_denom) -
		(right_numer * left_denom));
	// (a/b - c/d)'s (bd)
	int new_denom = left_denom * right_denom;

	return Rational(new_numer, new_denom);

}

Rational operator*(const Rational &lhs, const Rational &rhs)
{
	int left_numer = lhs.get_numerator();
	int left_denom = lhs.get_denominator();
	int right_numer = rhs.get_numerator();
	int right_denom = rhs.get_denominator();

	// (a/b * c/d)'s (ac)
	int new_numer = left_numer * right_numer;
	//(a/b * c/d)'s (bd)
	int new_denom = left_denom * right_denom;

	return Rational(new_numer, new_denom);
}

Rational operator/(const Rational &lhs, const Rational &rhs)
{
	int left_numer = lhs.get_numerator();
	int left_denom = lhs.get_denominator();
	int right_numer = rhs.get_numerator();
	int right_denom = rhs.get_denominator();

	// (a/b / c/d)'s (ad)
	int new_numer = left_numer * right_denom;
	// (a/b / c/d)'s (bc)
	int new_denom = right_numer * left_denom;

	return Rational(new_numer, new_denom);
}

bool operator==(const Rational &lhs, const Rational &rhs)
{
	int left_numer = lhs.get_numerator();
	int left_denom = lhs.get_denominator();
	int right_numer = rhs.get_numerator();
	int right_denom = rhs.get_denominator();

	if((left_numer == right_numer) && (left_denom == right_denom))
	{
		return true;
	}

	return false;
}

Rational.h

#ifndef RATIONAL_H
#define RATIONAL_H
/* Rational.h
 *
 * Representation of a rational number
 * EECS 280 Project 5
 *
 * DO NOT MODIFY THIS FILE!  Write your function implementations in
 * Rational.cpp
 */

#include <iostream>
#include <cstdlib>
#include <cassert>


class Rational {
  /*OVERVIEW
    Represent a rational number as a ratio of two integers, numerator and
    denominator.
    Think of the rational number as equivalent to numerator/denominator.
    You want to avoid
    running into unnecessary overflow problems since C++ limits
    the range of integers. Observe the following rules to keep
    your rational numbers in "reduced form" to
    avoid unnecessary integer overflows and wrong results:

    Invariant #1: Keep denominator as always >= 0. numerator can be negative,
    0, or positive.

    Invariant #2: numerator and denominator should not have a common factor
    other than 1.
    Eliminate any common factors.

    Invariant#3: When the rational number is equivalent to an integer,
    including 0, denominator must be 1.

    Invariant#4: When denominator is 0, numerator must be -1, 0, or 1.

    Note: You can assume that for all caculations that we will give
    you, both numerator and denominator for all rational numbers will
    be small enough to not cause integer overflows. But, your code
    should be able to handle situations like 2/3 being repeatedly multiplied
    by 100/100 without overflowing. You will be fine as long as you always
    keep your rational numbers in reduced form.
  */

 private:
  int numerator;
  int denominator;

 public:
  // EFFECTS: Constructor for rational number that is equivalent to integer 0.
  Rational();

  // EFFECTS: Constructor for rational number that is equivalent
  // to integer val.
  Rational(int val);

  // EFFECTS: Constructor for a rational number that is equivalent to
  // numerator_in/denominator_in.
  // Remember to ensure the Invariants.
  Rational(int numerator_in, int denominator_in);

  // EFFECTS: Returns numerator that is consistent with the invariants.
  int get_numerator() const;

  // EFFECTS: Returns denominator that is consistent with the invariants.
  // after eliminating any common factors. See invariants.
  int get_denominator() const;
};

// Overloaded operators on Rational numbers. Note that these are defined
// outside the class. It is possible to make these member functions, but
// this may be more intuititve.

// MODIFIES: output stream os
// EFFECTS: Prints out a rational number in reduced form
// without any spaces or newlines.
// Printing is done as
// follows. If the rational number is equivalent to an integer, just
// print the the integer value.
// Otherwise, print out numerator/denominator.
// For example, if numerator is 3 and denominator is 1, then print out 3.
// If numerator is 3 and denominator
// is 2, print out 3/2. If numerator is -4 and denominator is 3, print out -4/3.
// The function should also return the output stream os as its result
// so that << operations can be chained on a single line.
std::ostream& operator<<(std::ostream& os, const Rational& obj);

// EFFECTS: Returns a rational number equivalent to lhs + rhs.
// Note that (a/b + c/d) is algebraically equivalent to (ad+bc)/bd.
Rational operator+(const Rational &lhs, const Rational &rhs);

// EFFECTS: Returns a rational number equivalent to lhs - rhs.
//   Note that (a/b + c/d) is algebraically
// equivalent to (ad-bc)/bd.
Rational operator-(const Rational &lhs, const Rational &rhs);

// EFFECTS: Returns a rational number equivalent to lhs * rhs.
//   Note that (a/b * c/d) is algebraically
// equivalent to ac/bd.
Rational operator*(const Rational &lhs, const Rational &rhs);

// EFFECTS: Returns a rational number equivalent to lhs / rhs.
//   Note that (a/b / c/d) is algebraically
// equivalent to ad/bc.
Rational operator/(const Rational &lhs, const Rational &rhs);

// EFFECTS: Returns true if the two rational numbers are equal.  Otherwise,
//   returns false.
bool operator==(const Rational &lhs, const Rational &rhs);

#endif //RATIONAL_H

Stack.h

#ifndef STACK_H
#define STACK_H
/* Stack.h
 *
 * a templated stack based on a linked list
 * EECS 280 Project 5
 * By: Ryan Su
 * uniqname: rysu
 */

#include "List.h"
#include <cstddef>
#include <cassert>
#include <string>
#include <iostream>

////////////////////////////////////////////////////////////////////////////////
// DO NOT MODIFY THE CLASS'S PUBLIC INTERFACE OR PRIVATE VARIABLES.
template <typename T>
class Stack 
{
  //OVERVIEW: a templated, linked-list-based stack
  // The T is type of value stored, and it must implement operator<<

 public:
  // You should add in a default constructor, destructor, copy constructor,
  // and overloaded assignment operator, if appropriate. If these operations
  // will work correctly without defining these, you can omit them. A user
  // of the class must be able to create, copy, assign, and destroy stacks.

  //EFFECTS:  returns true if the stack is empty
  bool empty() const;

  //EFFECTS: returns the number of elements in this Stack
  int size() const;

  //REQUIRES: stack is non-empty. Assert false if it is empty.
  //MODIFIES: this
  //EFFECTS:  removes the item at the top and returns it.
  // Example:
  //    my_stack.push(42);
  //    int value = my_stack.pop();
  //    // At this point in the example, value == 42 and my_stack contains
  //    // exactly the same elements as it did before we
  //    // called my_stack.push(42)
  //    // (i.e., the 42 that we pushed is not on the stack anymore)
  T pop();

  //REQUIRES: stack be non-empty. Assert false if it is empty.
  //EFFECTS:  returns a reference the top element from the stack without
  // popping it.
  // Note: Since a reference is returned, potentially, the caller
  // can use the call to change the top without doing a pop/push. You should
  // test for that in your tests.
  // Example:
  //    my_stack.push(42);
  //    int value = my_stack.top();
  //    // At this point in the example, value == 42 but my_stack
  //    // *still has the 42 we pushed as it's top element.*
  T & top();

  //MODIFIES: this
  //EFFECTS: pushes an item onto the top of the stack
  void push(const T &item);

  //EFFECTS: returns the number of elements in the stack for which
  //  prep(datum) is true, where datum is the value stored in the stack's
  //  elements.  We use a template for Comparer type so that pred can
  //  either be a functor or a function pointer.
  // E.g., count_if(pred) is 0 for an empty stack. For a non-empty stack,
  // say S.push(item), where item is pushed on a stack S, count_if(pred) will be
  // the sum of S.count_if(pred) and either 1 or 0 depending on
  // whether item satisfies pred, respectively.
  template <typename Predicate>
  int count_if(Predicate pred) const
  {
    int count = 0;
    for(typename List<T>::Iterator i = list.begin(); i != list.end(); ++i)
    {
      if(pred(*i))
      {
        ++count;
      }
    }
    return count;
  }

  template <typename U>
  friend std::ostream &operator<<(std::ostream &os, const Stack<U> &obj);

private:
  /* You must make use of List's interface to implement the stack.
   * You must not make changes to the private section.
   */

  List<T> list;
};


////////////////////////////////////////////////////////////////////////////////
// Add your member function implementations below or in the class above
// (your choice). Do not change the public interface, although you
// may add the Big Three if needed.

//EFFECTS:  returns true if the stack is empty
template <typename T>
bool Stack<T>::empty() const
{
  return list.empty();
}

//EFFECTS: returns the number of elements in this Stack
template <typename T>
int Stack<T>::size() const
{
  return list.size();
}

//REQUIRES: stack is non-empty. Assert false if it is empty.
//MODIFIES: this
//EFFECTS:  removes the item at the top and returns it.
// Example:
//    my_stack.push(42);
//    int value = my_stack.pop();
//    // At this point in the example, value == 42 and my_stack contains
//    // exactly the same elements as it did before we
//    // called my_stack.push(42)
//    // (i.e., the 42 that we pushed is not on the stack anymore)
template <typename T>
T Stack<T>::pop()
{
  assert(!list.empty());
  T front_elt = list.front();
  list.pop_front();
  return front_elt;
}

//REQUIRES: stack be non-empty. Assert false if it is empty.
//EFFECTS:  returns a reference the top element from the stack without
// popping it.
// Note: Since a reference is returned, potentially, the caller
// can use the call to change the top without doing a pop/push. You should
// test for that in your tests.
// Example:
//    my_stack.push(42);
//    int value = my_stack.top();
//    // At this point in the example, value == 42 but my_stack
//    // *still has the 42 we pushed as it's top element.*
template <typename T>
T& Stack<T>::top()
{
  assert(!list.empty());
  return list.front();
}

//MODIFIES: this
//EFFECTS: pushes an item onto the top of the stack
template <typename T>
void Stack<T>::push(const T &item)
{
  list.push_front(item);
}

//EFFECTS: print all the elements of the stack, starting from the
// top element. Each element printed is followed by a space,
// including the last element. Do not print a newline.
// If the stack is empty, print nothing. You can modify Stack class
// if necessary to make this function a friend so that this function can
// access internal data within Stack.
//
// Hint: for this function to access the private "list" variable, you will
// need to declare it as a "friend" function in the class declaration above.
template <typename U>
std::ostream &operator<<(std::ostream &os, const Stack<U> &obj) 
{
  for(typename List<U>::Iterator i = obj.list.begin(); i != obj.list.end(); ++i)
  {
    os << *i << " ";
  }
  return os;
}

#endif /* STACK_H */