Homework 9: rpncalc

Reverse Polish Notation

We'll discuss "reverse Polish notation" (RPN), so-named in honor of its creator: Polish mathematician Jan Lukasiewicz, in class. Basically, it's a way to write mathematical formulae that does not require parentheses. RPN calculators (including rpncalc) don't need (or have) parentheses or an = key. In general, RPN calculators require fewer keys to do the same calculation as conventional calculators. (Note that experienced abacus operators usually beat both!)

The rpncalc Program

Input to rpncalc consists of operands (numbers) and operators delimited by whitespace (tabs and spaces). Operands may be integers or floating point numbers, although integers are converted to floating point numbers automatically (hence the use of double_stack). Entering an operand pushes it on the stack.

Here are the operators rpncalc understands:

+

pops the top two numbers off the stack and pushes their sum back on it.

-

pops the top two numbers off the stack and pushes their difference back on it. (So 8 2 - results in 6, not -6.)

*

pops the top two numbers off the stack and pushes their product back on it.

/

pops the top two numbers off the stack and pushes their quotient back on it. (So 8 2 / results in 4, not 0.25.)

**

pops the top two numbers off the stack and pushes the second-from-top number raised to the top number back on it. (So 8 2 ** results in 64, not 256.)

clr

clears the stack.

drop

pops the top number off the stack and ignores it.

dup

pushes a duplicate of the top number on the stack.

quit

exits the program

sqrt

pops the top number off the stack and pushes its square root back on it.

rpncalc works in two modes: interactive and command line.

The first rpncalc mode is interactive. It enters this mode when you don't provide any command line arguments. In interactive mode, it will continually prompt you to enter lines of operands and operators, separated by whitespace (spaces and/or tabs). Before each line, it will print out the contents of the stack and prompt you with "rpn:". You can then enter successive lines to modify the stack:

$ rpncalc
rpn: 2 1 +
                        3
rpn: 2 **
                        9
rpn: 4 2 **
                       16
                        9
rpn: +
                       25
rpn: sqrt
                        5
                        6

You can put as many operands and operators on the line as you like:

rpn: 2 1 + 2 ** 4 2 ** + sqrt
                        5

In interactive mode, the first error gives an error message indicating the problem operator and preserves the stack up until where the error was detected, so if you want to divide 3 by 2 but enter 0 by mistake, you can fix the problem:

$ rpncalc
rpn: 3 0 /
         ^--error
                        3
                        0
rpn: drop 2 /
                      1.5

The second rpncalc mode is command line. In this mode, you can enter an RPN formula directly on the command line. rpncalc evaluates the formula, prints the resulting stack, and exits:

$ rpncalc 1 1 +
                        2
$ rpncalc 2 3.1 / 4.7 5 / +
          1.5851612903226
$ rpncalc 103993 33102 /
          3.1415926530119

Caution: "*" has special meaning to the shell, so in command line mode it is generally necessary to either escape (with "\") the * operator or put it in quotes:

$ rpncalc 2 3 *
evaluation failed at "{some file name}" -- exiting
$ rpncalc 2 3 \*
                        6
$ rpncalc 2 3 '*'
                        6
$ rpncalc 2 3 "*"
                        6

(There's a way to fix this, but it involves shell reconfiguration, which is outside the scope of this class. If you find rpncalc useful outside of class, contact the instructor for how to do this.)

In command line mode, any error causes the program to exit with an error message:

$ rpncalc 1 + +
evaluation failed at "+" -- exiting
$ rpncalc 3 0 /
evaluation failed at "/" -- exiting

The homework directory includes working binary copies of rpncalc (for Linux systems) and rpncalc.exe (for Windows systems) so you can try it out and test it against your solution.

The rpncalc.c Source File

To build your implementation of rpncalc, here are the steps:

1. Copy double_stack.c and double_stack.h from your Lab 12 directory to your working directory for this homework.

2. Compile double_stack.c into double_stack.o as you did in the lab:

   $ gcc -Wall -c double_stack.c
   

3. Download the template rpncalc_tplt.c from the homework directory.

4. Rename it to rpncalc.c:

   $ mv rpncalc_tplt.c rpncalc.c
   

   Here are its contents:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#include "double_stack.h"


/*
 * These two `pop*Operand*()` functions incorporate things we will do
 * frequently: pop one or two double operands off the stack.
 */


static int popUnaryOperand(double *x_p)
/* pop a single double operand off the stack, return status */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * return the result of calling `doubleStack_pop()` to pop the
     *  double `x_p` points to off the stack. (You can do this in
     *  a single `return` statement.)
     */
}


static int popBinaryOperands(double *x_p, double *y_p)
/* pop two double operands off the stack, return status */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * user `doubleStack_pop()` to pop the double `y_p` points at off
     *  the stack
     * if there wasn't anything on the stack,
     *     return a 0
     * use `doubleStack_pop()` to pop the double `x_p` points at off
     *  the stack
     * if there wasn't anything on the stack,
     *     push the double `y_p` points at back on the stack
     *     return a 0
     * return a 1
     */
}


static int opAdd(void)
/* replace the top two doubles on the stack with their sum, return status */
{
    /*
     * Nothing to do in this function: Use it as an example for the
     * other `op*()` functions.
     *
     * Here's the pseudocode it implements:
     *
     * call `popBinaryOperands()` to get the operands `x` and `y`
     * if that call fails,
     *      return a 0
     * call `doubleStack_push()` to push `x + y` on the stack
     * return a 1
     */
    double x, y;

    if (!popBinaryOperands(&x, &y)) {
        return 0;
    }
    doubleStack_push(x + y);
    return 1;
}


static int opClr(void)
/* clear the stack, return status (always successful) */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * loop:
     *     pop a value (which will be ignored) off the stack
     *     if the stack is empty (i.e. the pop fails),
     *         break out of the loop
     * return a 1
     */
}


static int opDiv(void)
/* replace the top two doubles on the stack with their quotient, return status */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popBinaryOperands()` to get two operands `x` and `y`
     * if there are errors:
     *     return a 0
     * if `y` is 0, (avoid divide-by-zero)
     *     push `x` back on the stack
     *     push `y` back on the stack
     *     return a 0
     * push the quotient of `x` and `y` on the stack
     * return a 1
     */
}


static int opDrop(void)
/* discard the top double on the stack, return status */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popUnaryOperand()` to get a double `x` (which will be
     *  ignored)
     * if that call fails,
     *      return a 0
     * return a 1
     */
}


static int opDup(void)
/* duplicate the top double on the stack, return status */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popUnaryOperand()` to get a double `x`
     * if that call fails,
     *      return a 0
     * call `doubleStack_push()` to push `x` back on the stack
     * call `doubleStack_push()` to push `x` back on the stack
     * return a 1
     */
}


static int opMul(void)
/* replace the top two doubles on the stack with their product, return status */
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popBinaryOperands()` to get the operands `x` and `y`
     * if that call fails,
     *      return a 0
     * call `doubleStack_push()` to push the product of `x` and `y` on
     *  the stack
     * return a 1
     */
}


static int opPow(void)
// replace the top two doubles on the stack with their exponentiation,
// return status
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popBinaryOperands()` to get the operands `x` and `y`
     * if that call fails,
     *      return a 0
     * call `doubleStack_push()` to push the `x` to the `y`th power on
     *  the stack using the `pow()` function to do the computation
     * return a 1
     */
}


static int opSqrt(void)
// replace the top double on the stack with its square root, return
// status
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popUnaryOperand()` to get the operand `x`
     * if that call fails,
     *      return a 0
     * if `x` is negative,
     *      return a 0
     * call `doubleStack_push()` to push the square root of `x` on
     *  the stack using the `sqrt()` function to do the computation
     * return a 1
     */
}


static int opSub(void)
// replace the top two doubles on the stack with their difference,
// return status
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `popBinaryOperands()` to get the operands `x` and `y`
     * if that call fails,
     *      return a 0
     * call `doubleStack_push()` to push `x` - `y` on the stack
     * return a 1
     */
}


static int parseDouble(char *token_p, double *d)
/* parse a string token into a double, return status */
{
    char *end_p;

    /*
     * Unlike `atof()`, which we used for ``monsterdb``, `strtod()`
     * lets us detect an error when used like this:
     */
    (*d) = strtod(token_p, &end_p);
    if (end_p != token_p || *end_p == '\0')
    {
        return 1;
    }
    return 0;
}


static int parseToken(char *token_p)
// parse a single token_p, return status
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * call `parseDouble()` on the token to try to see if it looks
     *  like a double (set via a pointer to a double variable `d`).
     * if that call succeeds,
     *     call `doubleStack_push()` to push `d` on the stack
     *     return a 1
     * else if the token is "+" (use `strcmp()`, et seq.),
     *     return the result of a call to `opAdd()`
     * else if the token is "-",
     *     return the result of a call to `opSub()`
     * else if the token is "*",
     *     return the result of a call to `opMul()`
     * else if the token is "/",
     *     return the result of a call to `opDiv()`
     * else if the token is "**",
     *     return the result of a call to `opPow()`
     * else if the token is "clr",
     *     return the result of a call to `opClr()`
     * else if the token is "drop",
     *     return the result of a call to `opDrop()`
     * else if the token is "dup",
     *     return the result of a call to `opDup()`
     * else if the token is "quit",
     *     call `exit()` with a success (0) status
     * else if the token is "sqrt",
     *     return the result of a call to `opSqrt()`
     * else
     *     return 0 (unknown operator)
     */
}


static void evaluateLine(char *line_p)
// break `line_p` into operands and operators and apply them to the
// stack
{
    /*
     * This code is a little tricky, so here's the solution. You should
     * note a couple of things:
     *
     * 1. The standard library function `strtok()` works to "pull
     *    apart" a string into (NUL(the char)-terminated) "token"
     *    strings. The first time it's called, it's passed a string to
     *    act on and another string of characters, any of which can
     *    delimit a token. All subsequent calls pass a NULL (the
     *    pointer) for the first argument, which tell it to continue
     *    to use the same string as on the first call, and (in this
     *    case) the same second argument. This makes it very
     *    convenient to put in a for-loop in the way we've done it
     *    here. This is another handy C pattern to remember.
     *
     * 2. If `parseToken()` fails, it uses `token_p - line_p`, which
     *    is the index of the token's starting character, to space an
     *    error indicator on a line it prints right below the original
     *    entry. This lets the user know exactly where the problem was
     *    encountered.
     */
    char *token_p;

    for (token_p = strtok(line_p, " \n\t");
         token_p != NULL;
         token_p = strtok(NULL, " \n\t")) {
        if (!parseToken(token_p)) {
            printf("     %*s^--error\n", (int) (token_p - line_p), "");
            return; /* stop processing this line at the first error */
        }
    }
}


int main(int argc, char *argv[])
{
    /*
     * ASSIGNMENT
     *
     * Implement the following pseudocode:
     *
     * if `argc` is greater than 1 (i.e., the program name doesn't count),
     *     (this is command line mode)
     *     for every argument, starting with `argv[1]`,
     *         call `parseToken()` on that argument
     *         if an error occurs,
     *             print an error message on standard error
     *             call `exit()` with a failure (1) status
     *     call `doubleStack_print()` to print out the final stack
     * otherwise:
     *     (this is interactive mode)
     *     using a 1024-char array `line`...
     *     loop:
     *         call `doubleStack_print()` to print out the current stack
     *         call `printf()` to print out the prompt "rpn: " (no newline)
     *         call `fgets()` to read `line` from standard input
     *         if that call returns a NULL (indicating an end-of-file or error)
     *             break out of the loop
     *         call `evaluateLine()` to evaluate `line`
     */
    return 0;
}

5. Follow the instructions in the comments. The "ASSIGNMENT" comments mark places where you need to make changes.

6. Compile your code to produce rpncalc.o:

   $ gcc -Wall -c rpncalc.c
   

7. Link rpncalc.o together with double_stack.o to build the rpncalc.exe program (aka "binary"):

   $ gcc rpncalc.o double_stack.o -o rpncalc.exe -lm
   

   Remember that the -lm is to link with the math library, which you need for pow() (and any other math functions) to work.

8. Run rpncalc and make sure it's giving the expected output. Be sure to test both modes and all commands.

Extra Credit

You may earn a maximum of 10 points extra credit by adding two or more operators to rpncalc. Here are some suggestions:

sin

pops the top number off the stack and pushes its sine back on. The sin() function is in the math library, but you're already #includeing math.h (to get pow()). You may also add similar operators for math functions like cos(), tan(), exp(), etc.

pi

pushes the value of π on the stack. (Get it from the math library.) You may also add e (Euler's constant.)

To get ideas for other useful operators, try making some typical calculations or look at a scientific calculator.

If you attempt extra credit, add a comment to the start of your rpncalc.c that will tell the grader about it. Be specific.

Submitting Results

As there's only one file in this homework (rpncalc.c), submit it as an email attachment to the instructor. No tarball is necessary.