Data Structures - Chapter 7 - Programming Assignment
A Calculator Program

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages

The Assignment:
You will write a program that acts as a simple calculator, reading a file that contains an arithmetic expression on each line. The program evaluates these expressions and prints the values to cout. In the ordinary version of this assignment, the expressions are postfix expressions (as described on page 331 of the text). In a more advanced "honors" version of this assignment, the expressions are ordinary arithmetic expressions using infix notation.
Ensure that you can use the Stack template class that we provide for you.
Teach you how a program can use its command line parameters.
Teach you to read input from a file (rather than from cin).
Ensure that you understand and can implement the stack-based algorithms for evaluating an arithmetic expression.
Before Starting:
Read all of Chapter 7, with particular attention to Section 7.4.
Due Date:
Files that you must write:
  1. calc.cxx: This is a file that contains your main program for this assignment, along with various other functions that you write for your main program to use. As described above, the purpose of the main program is to read a file in which each line contains an arithmetic expression. The program evaluates these expressions and prints their values to cout.

    The details of this main program are given in the sequence of exercises listed below.

Other files that you may find helpful:
  1. stack2.h and stack2.template: These are the header file and implementation file for one of the Stack template classes from Chapter 7. Reminder: Since this is a template class, it is not separately compiled. Instead, your main program simply includes "stack2.h". With this include statement in place, the main program can declare and use any kind of stack.

A Calculator Program
Discussion of the Assignment

This discussion will lead you through a series of exercises that discuss some of the input issues that you will face in writing a program to read a file of expressions and print the values of these expressions to cout. The end of the discussion describes the difference between an ordinary version of this program (which evaluates postfix expressions) and an honors version (which evaluates expressions in the usual infix notation).

Command Line Arguments
When you execute a program in most operating systems, you type the name of the program followed by a list of values called the "command line arguments." For example, in the Unix or DOS operating system, you might type the following to execute the mkdir program:

mkdir hw06

The name of the program is "mkdir", and there is one command line argument, "hw06". Other operating systems allow you to type commands along with command line arguments in other manners (such as the "Run" dialog box in various Windows operating systems).

When you write and compile a C++ program, the resulting program can also be executed by typing its name along with command line arguments. Your instructor may have to show you how to do this on your particular operating system. For example, you can write a program called calc, compile the program, and execute it with the statement:

calc minimize your therbligs

The running calc program has access to the three strings "minimize", "your", and "therbligs". In order to obtain this access, you need to make a small change to the parameter list of the main function in the calc program. This parameter list should be changed to:

int main(int argc, char *argv[ ])

As you can see, the main program has two parameters that it can access just like any other parameters. The meaning of these parameters is determined by the command line arguments in a manner that is described in the next few exercises.

Exercise 1: Using the Argc Parameter to the Main Function

The first parameter, argc, is the count of the number of command line arguments. For example, if we execute the command:

calc minimize your therbligs

then calc's main program will have argc set to 4 (it counts the name of the program as one of the four "arguments").

For this exercise, write a complete main program called calc.cxx. The main program should have the two parameters, as shown above. The body of the main program should simply print the number of arguments in a message such as "There are 4 calc arguments!". Compile the main program into an executable file called calc. Run the resulting calc program with several different choices of command line parameters.

Exercise 2: Using the Argv Array

The main program's second argument, argv, has the declaration: char* argv[ ]. What does this mean? It means that argv is an array of pointers to characters. In other words, argv[0], argv[1], argv[2], ... are each a pointer to a character. In fact, each of these is a pointer to a dynamic array of characters. For example, suppose we execute our favorite command:

calc minimize your therbligs

In this example, argv[1] will be a pointer to a dynamic array of characters that contains the first command line parameter "minimize". As you might guess, argv[2] will be a pointer to a dynamic array that contains a pointer to a dynamic array of characters that contains "your". And argv[3] will be a pointer to a dynamic array of characters that contains "therbligs".

And what about argv[0]? That contains a pointer to a dynamic array of characters that contains the actual command that was typed. In our example, argv[0] points to a dynamic array containing "calc".

Each of the dynamic arrays argv[0], argv[1], ... can be treated just like any other string. For example, the first command line parameter can be printed to the screen by: cout << argv[1];

For your next exercise, modify your calc program from Exercise 1 so that it also prints a copy of the command that was typed along with the command line parameters. For example, if you execute the command that we have been using in our examples, then the output of the calc program will now be:

There are 4 calc arguments!
calc minimize your therbligs

Exercise 3: Checking That There is the Right Number of Arguments

Most programs require a certain number of command line parameters. If you provide the wrong number of command line parameters, then the program provides a "usage message" trying to tell you the correct way to use the program. Let's suppose that your calc program is supposed to read input from an input file, and that calc is always used with two command line arguments (the name calc is the first argument, and the name of the input file is the second argument). If calc is executed with more or less arguments, then you want a succinct error message to be printed such as "Usage: calc input_file." This is a succinct message describing how calc is supposed to be used.

For this exercise, add a new function to your calc program, with this prototype

void validate_argc(int argc, int right, const char usage[ ]);

The function has three arguments. The first argument, argc, is the value of argc from the main program. The second argument, right, is the correct number of arguments that this program is supposed to have. The third argument, usage, is a string which is a suscinct usage message for the program. Here's what the function does: If argc is equal to right, then the function does nothing. But if argc differs from right, then the function prints the message and halts the program. Two points:

  1. Print the message to cerr, rather than to cout. (since cerr is the "standard error output").
  2. You can halt the program by calling a function exit(0).

Once the validate_argc function is added to your program, include a call to the function in your main program. The call should indicate that the right number of arguments is 2, and provide the usage message: "Usage: calc input_file."

Reading From a File

By the way, you are headed toward a program that reads a file of arithmetic expressions as input. Eventually the program will evaluate all the expressions, and write the resulting answers to cout. Input from a file is easy in C++. Here are the steps:

  1. The program must #include <fstream.h>.

  2. The program needs to declare an ifstream variable that will "attach" to the input file. The data type of this variable is ifstream. For example, you could make the declaration of an ifstream variable called input, as shown here:

    ifstream input; // Will be attached to the input file

  3. The ifstream must be attached to the input file by activating the open function. The argument to the open function is an ordinary C string constant or string variable. For example, if input is an ifstream, then we can attach input to a file named foo with the function call:"foo");

    The argument to the open function can also be a string variable-- i.e., an array of characters with the last character followed by the null character '\0'.

  4. You must check that the file was successfully opened. This check can be made by activating the fail function. This function returns a true/false value to indicate whether the ifstream has failed to properly attach to the input file (true indicates failure). I'd suggest something like this:

            if ( ))
                cerr << "Could not open input file." << endl;

  5. Once the ifstream input has been successfully opened, you may use the name input in the same way that you use other input devices (such as cin). For example, suppose that the next item in the input file is an integer, and i is an integer variable. Then you may execute the statement:

    input >> i; // Read an integer from the input file

    All the other familiar input functions (such as peek and ignore) can be used with the ifstream, in the same way that you have previously used these function with cin.

  6. Eventually you will read the end of the input file. At the end of the file there is usually a special character called EOF (which is not actually part of the data of the file). You can also use the name of the ifstream (such as input in our example) as a boolean expression which is true so long as the file has not contained any bad input (such as an alphabetic character when a digit is expected). Thus, the complete boolean expression to test whether there is more input reads like this:

    (input && input.peek( ) != EOF)

  7. When you are done reading from the input file, then you should activate the close function, as shown here for our example:

    input.close( );

Exercise 4: Three More Functions for the Calc Program

Write the following three functions, and add them to your calc.cxx:

  1. A function that opens a file for input and checks that the opening process did not fail. The specification for this function is:

    void open_for_read(ifstream& f, const char filename[ ]);
    // Postcondition: The ifstream f has been opened for
    // reading using the given filename. If any errors
    // occurred then an error message has been printed
    // and the program has been halted.

  2. A boolean function that determines whether a specified file still has valid input. The specification is:

    bool is_more(istream& f);
    // Postcondition: The return value is true if f still has
    // more valid input to read; otherwise the return
    // valid is false.

    Notice that the data type of the argument is an "istream" rather than an "ifstream". An istream is usually an ifstream, although later you will learn of other kinds of istreams (such as cin). Istream arguments must always be reference parameters.

  3. A function named process_line with this prototype:

    void process_line(istream& f, bool& okay, double& answer);

    For now, you can implement a simple version of process_line. The simple version reads one input line, sets okay to true, and sets answer to 42.0. Later you will implement a more complex version of the function that actually evaluates an arithmetic expression from the input line. Anyway, put the simple version in your calc.cxx program and change the body of the main function so that it does this:

    • Declares an ifstream variable called input and uses open_for_read to open input for reading. Use argv[1] as the name of the input file.
    • Have a loop that continues while there is more input. In the body of the loop, call process_line. If process_line sets okay to true then print the value of answer on the next output line; otherwise print the word INVALID on the next output line.
    • Close the input file and print a message saying that the program is done.
The Rest of This Programming Assignment

For the rest of this programming assignment, modify the process_line function so that it reads the next line of input (including the newline character at the end of the line). It treats this input line as an arithmetic expression. If the expression has an error (such as division by zero), then the function sets okay to false and leaves answer unchanged. Otherwise, the function sets okay to true and sets answer to the value of the expression. Here are a few considerations:

  • For the ordinary assignment, the input expressions are postfix expressions. Use the evaluation algorithm from Figure 7.10 on page 334. The possible errors that will cause okay to be set to false: (a) division by zero, (b) an operation symbol is read but the stack does not have at least two numbers, (c) the entire expression has been read and evaluated but the numbers stack does not have exactly one number on it.
  • For the extra credit assignment, the input expressions are usual arithmetic expressions using infix notation. There are two approaches you can use: (1) Try the algorithm from Figure 7.12 on page 339 to convert the expression to a postfix expression (stored in a string). Then evaluate the postfix expression. Or (2) Try the better approach that I'll describe in class (which evaluates the infix expression without first converting it to postfix).
  • If an error is detected, be sure to continue to read the rest of the input line (up to and including the newline character).
  • Use input techniques similar to those in Figure 7.5 on pages 319-321.

Michael Main (