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 ) 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:
1. Start with an empty stack
2. Read a token and create a node from it, marking it as either NUMBER or OPERATOR; use
malloc( ) to allocate space for the node
3. If the node contains a number, push it onto the stack
4. If the node contains an operator
A. Pop two values
B. Apply the operator
C. 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.