Description
In this lab, you will be introduced to ANSI C99 and make use of a stack data structure implemented
as an array. Input will be read using scanf(1) and output printed with printf(1). The program will
implement a Reverse Polish notation calculator.
1. Reverse Polish notation
Reverse Polish notation [1] (RPN) was invented by the Polish logician Jan Łukasiewicz [2] and places
all operators after their operands, which makes it much easier to parse than infix notation, and does
not need parentheses to override operator precedence. For example, the infix expression
3*4+5*6
is represented as
34*56*+
in RPN.
[1] http://en.wikipedia.org/wiki/Reverse_Polish_notation
[2] http://en.wikipedia.org/wiki/Jan_%C5%81ukasiewicz
2. Program input
Input to the program will consist of double precision IEEE-754 floating point numbers and calculator
operators. You have been provided with a reference implementation jrpn.java which you are to
translate into crpn.c, for whichaskeleton outline has been provided.
(a) Any word on input that looks like a number to the function strtod(3) is pushed onto a stack.
(b) If an input word consists of one of the operators ’+’, ’-’, ’*’, or ’/’, two numbers will be
popped off the stack, the right operand being popped first and the left operand next, then the
result is pushed back onto the stack.
(c) The operator ’;’ cause all numbers on the stack to be printed, from bottom to top using the
format “%.15g\n”.
(d) The operator ’@’ clears the stack.
(e) Any input word beginning with the character ’#’ causes the rest of the line to be ignored as a
comment.
(f) Anything else on input is an error.
3. Outline of the functions
The following functions are to be implemented. See the Java version for detailed implementation
requirements.
(a) void bad_operator (char *oper)
takes an invalid operator and prints an error message.
(b) void push (stack_t *stack, double number)
pushes the number onto the stack if there is space but prints an error message if not.
(c) void do_binop (stack_t *stack, char operator)
accepts a binary operator, pops the right operand then the left operand, computes the answer
then pushes the result on the stack. An error message is printed if there are not at least two
numbers on the stack.
(d) void do_print (stack_t *stack)
prints the stack bottom to top, one number per line, or indicates that the stack is empty.
(e) void do_clear (stack_t *stack)
causes the stack to be emptied.
CMPS-012M • Fall 2013 • Lab 3 • RPN, Stacks, and ANSI C page 2 of 2
(f) void do_operator (stack_t *stack, char *operator)
accepts any operator and dispatches the appropriate function to perform the operation.
(g) int main (int argc, char **argv)
loops reading input and calls other functions to perform appropriate operations.
4. The code/ and misc/ subdirectories
The code/ subdirectory contains two programs : jrpn.java contains the implementation of your lab
in Java. crpn.c contains a partial implementation of your lab in C. The main function is complete,
and you have to fill in the bodies of the rest of the functions to that they do exactly the same thing as
the Java version. The exact format of the numbers printed will be slighly different because of the
wa y the languages format numbers differently.
The misc/ subdirectory contains various sample programs illustration some facets of ANSI C99.
5. Compiling your code
Do not type gcc in at the terminal directly, since it is properly used with multiple options, which
would normally be put in a Makefile. This time, you will write a simple shell script called mk to perform the compilation. The script should contain the following lines :
#!/bin/sh
# $Id$
gcc -g -O0 -Wall -Wextra -std=gnu99 crpn.c -o crpn
Add your name after the RCS Id comment line in another comment. Use chmod +x to make it executable. When you have created the file, check it into an RCS subdirectory using cid. Also do this
with your program crpn.c. Note : The hash-bang line (starting with #!) may not have any spaces.
6. What to submit
Submit the script mk and the program crpn.c, and if you are doing pair programming, also the PARTNER file.