Fwd: assignment

[Prashant Sharma]

The Assignment: Stack based RPN Calculator

Part 1:

In this assignment you will write a C program that will emulate the action of a classic stack based calculator. For those of you that are not familiar with stack based calculators or Reverse Polish Notation I would suggest the following Wikipedia site:

http://en.wikipedia.org/wiki/Reverse_Polish_notation

In such a calculator all operations are organized around a stack. Entering a number like 3.14159 would push that value on the stack, entering an operation like + or tan would consume numbers from the top of the stack and push the result on the top of the stack. Your C code must read the entries that the user types on the standard input, manage the stack and print the correct outputs when needed.

This assignment will allow you to exercise a few aspects of the C language including getting input from stdin, using the sscanf function to parse string content, performing operations on strings, handling dynamic memory with malloc and free and using printf to produce output.

The program that you implement should run a loop which continually reads the commands that the user types on stdin and performs the requisite operation as follows:

Input	Action
A decimal number	Add the number to the top of the stack. Here are some examples of valid numbers 4.13, -0.675, 25
+	Pop the two top entries off of the stack and place the sum at the top of the stack.
-	Pop the two top entries off the stack subtract the first/top entry from the second and add the result to the top of the stack.
*	Pop the two top entries off the stack multiply them and add the result to the top of the stack.
/	Pop the two top entries off the stack divide the first/top entry by the second and add the result to the top of the stack.
sin	Pop the top entry off the stack compute its sine (interpreted as a value in radians) and add that result to the top of the stack
cos	Pop the top entry off the stack compute its cosine (interpreted as a value in radians) and add that result to the top of the stack
tan	Pop the top entry off the stack compute its tangent (interpreted as a value in radians) and add that result to the top of the stack
sqrt	Pop the first entry off the stack, perform the square root of this entry, and add the result to the top of the stack.
pow	Pop the top two entries off the stack and perform ba, where a is the top/first entry popped off stack and b is the second. Add the result to the top of the stack.

dup	Duplicate the value at the top of the stack so after this command the two values at the top of the stack should be the same
swap	Swap the order of the two top entries in the stack.
pop	Pop the top entry off the stack
print	Print the current contents of the stack
quit	Exit the program freeing all entries on the stack

Part 2:

In this part of the assignment, you will extend the functionality from part 1 to allow a limited capability for users to define their own functions. The user should be able to define one function at a time, and then call it according to the following:

Input	Action
def arg1 arg2 ... argN	Define a single function that is a list of any of the input options from part 1. Arguments are whitespace separated. If a previous function already exists, this will overwrite it. You may assume that the total length of this input will not exceed 100 characters (not 100 arguments).
call_func	Call each item in the list in the user defined function, applying its effects to the stack in the order in which it appears in the list.
print_func	Print the list the comprises the current user defined function.
append_func arg1 arg2 ... argN	Append additional inputs from part 1 to the end of the current user defined function. Again, you may assume that the total length of this input will not exceed 100 characters (not 100 arguments).
remove_arg	Deletes the first input in the user defined function, deleting the entire function if the current function is of length 1.

When the user defines this function, list of inputs which comprise it must be parsed and stored in a queue data structure. You will NOT receive full credit for storing the entire string and parsing it each time the user inputs call_func.

You do not have to worry about order of operations; perform each action in the list from left to right, as if the user were to type each command separately. If any of the arguments to def are invalid, no function will be defined, a previously defined function will not be overwritten, and “INVALID ARGS” will be printed. “INVALID ARGS” should also be printed if any of the arguments to append_func are invalid. If the user inputs call_func, print_func, append_func, or remove_arg but a function is not defined via def, print “NO FUNCTION DEFINED.”

Usage example:

Input: “def 2 pow swap 2 pow + sqrt” (Pythagorean Theorem) Input: “call_func” current stack: 3, 4
--> yields 5 at the top of the stack

Handling command strings:

For the commands that are typed it should not matter whether the characters are upper case or lower case or a mixture of both, your program should perform the required operation so if the user types tan, TAN or tAn the same thing should happen. Furthermore, extra whitespace characters can appear on the command line before or after the command but if you detect extra non-whitespace characters your program should print “INVALID COMMAND” and ignore that input, it should not exit, it should just go back to waiting for the next command. Extra whitespace (as in more than the minimum of 1 space) between arguments to def is also legal. Look at the C examples on Canvas to find examples of reading input from stdin using the fgets and sscanf functions.

If there are not a sufficient number of entries on the stack to perform the requested entry your program should print out “STACK ERROR” and then proceed to wait for the next command.

At the end of every numeric entry or command that does not produce an error your code must print the value currently at the top of the stack followed by a newline (ie ‘\n’).

Handling the heap:

A big part of your grade for this assignment revolves around your use of malloc and free. Your code must correctly create and maintain the required stack data structure which is similar to the linked list data structure that will be covered in class. You MUST correctly free memory when items are removed from the stack. Failure to do so correctly will result in a memory leak and a major loss of points.

Standard C Libraries

In order to program effectively in C you will want to begin to familiarize yourself with the Standard C Libraries. You can find a useful reference to them here: http://www.acm.uiuc.edu/webmonkeys/book/c_guide/

These utilities are packaged into collections of functions that you can call from your code. In order to avail yourself of these routines you should #include the relevant header files at the beginning of your program like so:

#include <stdio.h>
#include <ctype.h>

These include directives include the declarations contained in these files into your program so the compiler learns about their existence and calling signature.

Here are some standard C library routines that you may want to look at:

<stdio.h> printf, sscanf, fgets
<math.h> sin, cos, tan, pow, sqrt <ctype.h> tolower, toupper, iswhitespace <string.h> strstr, strcmp

<stdlib.h> malloc, free, exit

The list is only suggestive not comprehensive, you don’t have to use any of them if you don’t want, feel free to use other functions that you find in the standard libraries if you prefer them. 

--

Prashant Sharma