CSCI 112: Programming and Algorithms II
Fall 2005
Program 4: Post-fix Calculator
Code due: 8am Friday October 21 (copied to your ecst turn-in directory, see below)
Grading Weight: 3 (programs will have a weight between 1 - 5)

Overview:

The standard form of equations, 2 + 4, is called infix because the operator (+ in this example) is "in" the middle of the operands (2 and 4 in this example).  This form has the drawback of not being able to control the order in which the operators are applied without using parentheses.  For example, if you want 2 + 4 multiplied by 5, you have to write (2+4)*5.  While this is easy to do in a programming language, it is difficult to do on a standard calculator.

Postfix notation (also called Reverse Polish Notation or RPN) is much better suited for calculators.  In postfix notation, the operator goes after the operand.  For example, the equation 2 4 + means 2 plus 4, and the expression 2 4 + 5 * means to first apply + to 2 and 4 and then apply * to the result of 2 + 4 and 5.  The result is (2 + 4) * 5 and you didn't have to type in the "(" and ")".

Postfix calculators are easily implemented using a stack data structure.  When the user enters an operand, it is inserted on to the stack (in stacks, inserting on top of the stack is called push).  When the user enters a binary operator, the 2 operands on top of the stack are removed (popped), the operator is applied to them, and the result is pushed on to the stack.

If at the end of the input, there is one and only one operand on the stack, then the input was a valid expression and the value on the stack is the result of evaluating that expression.

This assignment is to implement an RPN calculator that can evaluate any legal expression and catch all illegal input (except numbers with so many digits that they won't fit into a double).  As soon as illegal input is encountered, print the error message (see below) and call exit(1).

Program Requirements:

Implementation:

Implement your stack from scratch using dynamic allocation.  In other words, your stack must look like a linked-list.  You may not use a stack from a library.  Create a class Node to hold the elements of the stack.  This class must be nested inside of class Dstack.

Implement your program using the following class:

class Dstack

Stack of doubles that provides at least the following functions:

push - push a new element on top of the stack
pop  -  remove and return the top element from the stack (must be able to deal with an empty stack)
~Dstack - a correct destructor

You may use whatever return types and arguments you see fit.  You may add additional functions if you need them.

Put main() in the file calc.cpp

Input:

Your program must read a single equation from standard input.   The operators are + - * / ^ (^ is power, 2 4 ^ is 2 raised to the power of 4).  Numbers can be any double number, for example 4, 4.2, .2, 0.2, 0000.233.  You can assume that the number is small enough to fit into a double variable (I won't give you a number with 200 digits).

Your program should ignore all white space (spaces, tabs, newlines).

If two numbers are in a row, there must be a space between them.  For example, 42 is the number forty-two, and 4  2 are the numbers four and two.

There do not have to be spaces between numbers and operators.  For example, 10 10+ is a legal equation.

There do not have to be spaces between two operators.  For example, 10 10 10++ is a legal equation.

Files:

Each class should have a .h file and a .cpp file (note that the filenames are all lower case):

dstack.h
dstack.cpp

In addition to the above files, you will need to turn in a file containing your main() function:

calc.cpp

Program Output:

If the input is a correct post-fix expression, your program should print the result.

For example, if the input is 10 10+, your program should output 20 followed by a newline, and nothing else (don't print any prompts or "aswer =").

Errors and Error Messages:

If the input is not a valid post-fix expression, your program should print the following to standard error:

 Error: Invalid expression.

followed by a newline (not a blank line, but a newline) and then call exit(1).

Your program must check for all types of errors (except numbers that are too large).

Hints:

The algorithm is:

while (not the end of the input)

If the next input is a number, read it and push it on the stack
If the next input is an operator, read it, pop 2 operands off of the stack, apply the operator, push the result onto the stack
if there is one number on the stack, print it
else error

I suggest you implement and test the stack before you tackle the calculator aspects of the program.  You will have to write a few lines of code in main() to do this testing, but it will save you time in the long run.

You can't just use getline() or cin >> string_variable for this program because you usually don't know if an operator or an operand (a number) will be the next thing in the input stream.  You will need to use cin.peek() to look at the next character in the input.  cin.peek() returns the next character without actually reading it.  In other words, the next character you read will be the one returned by cin.peek().  If it is whitespace (space, tab, newline) you can skip it using cin.ignore().  If it is a legal operator, you can read the single character using cin >> char_variable.  If the next character is a digit, you can use cin >> double_variable to read the entire number.  cin.peek() returns EOF (which is defined as -1) if end-of-file is true.

General Requirements:

I will deduct 10 percent if your program does not compile using my Makefile on the lab machines.  Thus you must make sure to use the filenames listed below (do not capitalize your filenames), and if you are working on windows, you should compile and test your program on one of the department's suns before turning it in.

We will grade your program using another program, so if your program does not work exactly as specified below you will lose points.

The first lines of all your files (.h and .cpp) must contain:

/****
last name, first name
ecst_username@ecst.csuchico.edu
112 Program 4: RPN Calculator
****/

How to turn in code:

$ make submit

calc.cpp
dstack.h
dstack.cpp

/user/projects/csci112/p4/USERNAME

Late assignments:

If you do not finish by the deadline (see top for the deadline), you may turn your assignment in up to 24 hours late.  You will lose 15% for turning your assignment in 1-24 hours late.

If you turn your assignment in late, copy your assignment into the following directory:

/user/projects/csci112/p4_late/USERNAME

Assignments will not be accepted if more than 24 hours late.

If you are working on the department machines and you have a copy of my makefile, you can submit your files using
"make submit_late"

Extra credit:

You will get 10 points extra credit if your program passes all the extra credit tests, and a fraction of 10 points if it passes some of the extra credit tests.  Since these are multi-character operators, you will have to modify how you read the input. 

Implement the following operators:

sqrt   calculate the square root of the previous number,  15 sqrt means the square root of 15.

cos   calculate the cosine of the previous number, 30 cos means the cosine of 30

sin    calculate the sine of the previous number, 45 sin means the sine of 45

Note: Assume the user is entering degrees.  Since the math.h functions cos() and sin() expect the angle in radians you will ahve to convert the number to radians.  Use the constant M_PI from math.h to perform the conversion.