CS210 An RPN Calculator

Stacks are a critical part of the operating system's structure. Although we typically don't manipulate the call stack directly from our C programs, once our C code has been compiled to assembly language, it will use the stack heavily. From a systems perspective it's important to understand how stacks operate.

In this assignment you'll write a five-function calculator that takes input in Reverse Polish Notation, which is a post-fix way of writing arithmetic expressions. RPN is described at a high level at the end of this document, focusing on how a stack can be used to evaluate expressions. Just like your linked-list assignment, you'll be using dynamically allocated nodes, but this time arranged as a stack rather than a list.

Error handling in your calculator

Unlike other languages that you've used to date, C doesn't have any built-in error handling -- you won't find any try/catch sort of facility in the language specification. This means that it is up to the programmer to ensure that there are no unhandled errors.

A large part of this assignment is figuring out all of the places that something could go wrong and making sure that when it does go wrong, the problem is gracefully handled. Some advice on error handling is given at the end of this document. Typically you'll want to respond to errors by printing a statement about the error and terminating the program.

One bit of general advice on error-handling: C includes a goto statement, and it is commonly used to jump across code to a place where errors are handled. Use it judiciously and do a bit of reading to understand its limitations.

Overview

For this project you'll build out a stack-based calculator that uses RPN notation.

Organization

You should end up with at least eight source files in your project, plus one file of captured output.

• main.c driver file for the problem set
• node.h, node.c declaration and implementation of a single node
• stack.h, stack.c declaration and implementation of stack operations
• rpn.h, rpn.c declaration and implementation of the RPN evaluator
• errors.h definitions of strings for error codes
• ps4results.txt

Your code in main.c should be doing very little work on its own -- it basically will just be making calls into the evaluate( ) function in rpn.c:

result = evaluate(expression, &status);

Note that node.h and node.c will be very similar to the node that you used in PS3, but it needs to carry information about its contents:

typedef struct node {
double value;
int type;
node *next;
} node;

Use an enumeration to define type as either OPERATOR or NUMBER, and adjust createNode( ) from PS3 as necessary to accommodate the new fields.

Stack operations

Stacks have three primary operations, and you'll need to implement all three:

• push(node*) Push a node onto the stack
• node* pop( ) Pop the top of the stack
• node* peek( ) Return a reference to the node on top of the stack

In addition, implement a clearStack( ) function that resets the stack to empty, freeing any nodes that were there previously. This should be called prior to each evaluation.

Stacks work from the top, so a push( ) will result in HEAD pointing to the pushed node, and the pushed node pointing to the former HEAD. Similarly, a pop( ) will return the top node on the stack and set HEAD to point to the former second node.

You are of course welcome to write additional helper functions. For example, it might be useful to write a bool stackEmpty( ) function, or a function to return the type of a node, or maybe one to print the stack that you could use for debugging.

Because these functions are working with node pointers, they will need to handle errors related to the pointers (for example, null pointers and the return status from malloc( ).

Building the stack

Write a function in rpn.c called evaluate( ) that takes two parameters: the expression to evaluate, and a reference to a status variable.

double evaluate (char* expression, int* status)

In evaluate( ), use the function strtok( ) (from < string.h>) to parse the input string. The input string will comprise numbers and operators separated by a single space. For example:

char expression[ ] = {"40 2 +"};

Keep in mind that strtok( ) involves two different calls, one to 'prime' the algorithm, and a second in a loop to parse the remainder of the tokens. Each call to strtok( ) will result in a new node being malloc'd and pushed. Once the calls to strtok( ) are complete, the stack will be built and you can start evaluating the expression.

The string function strstr( ) is a good one to use to determine whether a token is a number or an operator. You'll also need to convert the string returned from strtok into a number.

Evaluating expressions

Your calculator should evaluate the following five mathematical operators:

+ - / * ^ (exponentiation using recursion)

Use a switch statement to perform these calculations.

The problems

PS4.0: Evaluate expressions

Once you've done all the setup work writing node, stack, and evaluate functions, evaluate these expressions, capturing the result in ps4results.txt. If an error occurred, capture the error message in the ps4results.txt file.

1. "24.2 12 / 3 / 17 + +"
2. "+"
3. "17 22 / 4 * 16 -"
4. "2 8 ^ 3 /"
5. "17 22 33 / 4 + 2"
6. ""
7. "8 7 + 6 - 5 / 4 * 3 ^"

Calculations using a stack and RPN

Reverse Polish Notation is a way of writing and evaluating mathematical expressions that is commonly used in industries such as engineering and finance. One of its biggest advantages is that there are no parentheses to alter precedence, and so calculation flows from left to right without jumping around. It is often the case that software offering infix notation (where the operator is between the operands) will first convert the infix expression to postfix (where operators follow their operands, as in RPN) prior to performing a calculation.

For example, to write the expression 24 + 18 in RPN: 24 18 +.

RPN typically uses a stack to evaluate expressions. Each value in the expression (either a number or an operator) is called a token. The algorithm looks like this:

• Start with an empty stack
• Read a token and create a node from it, marking it as either NUMBER or OPERATOR; use malloc( ) to allocate space for the node
• If the node contains a number, push it onto the stack
• If the node contains an operator
  • Pop two values
  • Apply the operator
  • Push the result (in a new node) to the stack

When you've reached the end of the expression, there should be just one node on the stack, holding the evaluation of the expression.

Note that we are only working with operators that take two values for this assignment.

Don't forget to call free( ) on any node that is being discarded.

Responding to errors

Because we are working primarily with pointers, it is important to always check a pointer for NULL prior to dereferencing it.

We're also doing math, and at least one error condition must be checked for prior to execution: Dividing by zero, which yields an undefined result (and, usually, a program crash).

Your evaluate( ) function should include a reference to a status variable:

double evaluate (char* expression, int* status)

In this function, status should be set to zero for success, or a negative value for an error. Use #define to define strings for errors that your code handles in the file errors.h, so that if, for example, you encounter a null pointer where you shouldn't, you can respond like this:

*status = ERRNULLPTR;
return 0.0; //the return value will be discarded

Some common errors to get you started (and you might run into more):

• Incorrectly formatted expression (too many operators, too few values, etc.)
• Divide by zero
• Null pointer where it shouldn't be

Formatting errors can typically be captured by examining the stack at the end of an evaluation pass, since at the end there should be only one node on the stack, holding the result. More than one node, or a null HEAD, would indicate a problem.