Department of Mathematics and Computer Science

Machine Problem 3

Math 61 D. C. Smolarski, S.J. Winter 2000

Data Structure Concepts:STACKS, ARITHMETIC EXPRESSIONS, CONVERSION TO RPN

30 points (5 additional points possible!)
DUE: (MP 3) Noon, Thursday, February 3, 2000

For this Machine Problem, you are to write a C++ program that evaluates simple arithmetic expressions. For example,

           INPUT:  (2+3)*(5-2) =
	   OUTPUT:      15

You should use two stacks, one for storing operators (*,+,-, etc. via a numeric code [see below]) and one for the operands (i.e., numbers). (You should only have ONE definition of class, however.)

Part of this program involves learning how to implement the stack class in a separate "header" file (and associated code file). This involves writing the stack class in separate files (perhaps call the two files astack.h and astack.cxx [for "array-stack"]). These two files contain nothing other than information pertaining to the implementation of the class "Stack." Detailed information is given in Notes M4 from my Math 10 set of class notes. (Note that there, the files are called "stack1," so if you copy that code directly, you need to change every instance of "stack1" to "astack.")

In another file, perhaps called mp3.cxx, you put code to implement the algorithm for this assignment making use of the new datatype "stack." To access the other files, include the statement

      #include "astack.h"

I suggest you use the following makefile:

     mp3 : astack1.o mp3.o
	      g++ astack.o mp3.o -o mp3

     astack1.o : astack.cxx astack.h
	      g++ -c astack.cxx

     mp3.o : mp3.cxx 
	      g++ -c mp3.cxx

(What this makefile means is this:
The first line says that the file mp3 depends on files astack1.o and mp3.o and the next line tells how to create mp3 from these other two files.

The third line says that file astack1.o depends on files astack.cxx and astack.h. If either of these two are newer than astack.o the next line is executed.

This sort of makefile guarantees that whenever any one of the three inter-related files is modified, files which depend on them are recompiled, but only those files are recompiled that are absolutely necessary.)

The textbook, Ford and Topp, give segments of one version of a program to implement this problem on pages 299-308 of the book. You are free to use that information, or use the suggestions below, or do it in your own way. NOTE that the Ford and Topp program solves a problem that is more complicated than what I suggest for this double assignment! Thus, if you copy their code, you may be doing much more work than necessary!

You need get the program running using ONLY ONE-DIGIT operands WITHOUT any PARENTHESES, i.e., it should evaluate correctly simple expressions such as 3*4 + 5 and 5 - 4 * 2 (with arbitrary spaces between characters).

Once that is running, for 5 added points, add the ability to perform correctly when there are parentheses in the input.

YOU SHOULD WORK SUBSTANTIALLY BY YOURSELF ON THESE PROGRAMS. Of course, a friend's eyes may help you debug certain errors. But I do not want several students to work together on the entire code and turn in separate versions of it.

Your program should more or less follow these steps:

1. Initialize.
2. a) Read the input characters, one by one, skipping blanks until you reach end-of-input-line mark (i.e., =).
   b) For each character, write the character, then test it. If the character is a digit then push it on the operand stack, else push it on the operator stack, UNLESS YOU NEED TO REDUCE THE STACK FIRST.
3. When all the characters for a given input-line are read-in, reduce all stacks and print out the value of the expression.

For extra points, you need to worry about parentheses! This can be done in several ways. The book uses one scheme. The following is an alternative.

Each operator can be assigned a precedence number, e.g. + <=> 0, - <=> 1, * <=> 2, / <=> 3. You can also keep count of a "level" number, which indicates the level of parentheses you are presently within. The level number starts out at 0. When a left parentheses is encountered, the level number is increased by 4. When a right parentheses is encountered, it is decreased by 4. When doing any OPERATOR stack operations (PUSH, POP, REDUCE), one needs to use the value on the stack, modifying it if necessary by the level value. For example, if the top of stack were a 2 (i.e., a *), but one attempted to push a 4 on it (i.e, a 0 corresponding to a + after the level was changed to 4 because a left parenthesis had been encountered in the input stream), this push would be permitted because the value for + would now be interpreted (and actually stored) as 4 and not as 0.

You may want to make use of the following code:

      int nconvert(char c)
      //Converts a number read as a char var to an integer value
      {
        return (int(c) - int('0'));
      }

      /* ----------- */

      int eval(int op, int a2, int a1)
      /* Evaluates a2 op a1 where op is the numeric
         precedence corresponding to an operator */
      {int value;
        switch (op)
        {
        case  0 : return (a2 + a1);
        case  1 : return (a2 - a1);
        case  2 : return (a2 * a1);
        case  3 : return (a2 / a1);
        }
      }

      /* ----------- */

      void operatadd(char ch, stack & operatorx)
      /* Pushes the correct operator precedence number onto
      the operator stack or changes the level number */
      {
        switch(ch)
        {
        case '+' : operatorx.push(0);
                break;
        case '-' : operatorx.push(1);
                break;
        case '*' : operatorx.push(2);
                break;
        case '/' : operatorx.push(3);
                break;
        case '(' : operatorx.level = operatorx.level + 4;
                break;
        case ')' : operatorx.level = operatorx.level - 4
                break;
        }
      }

It is probably best to read in the line, one character at a time, as character variables.

To check if a character variable CH is a single digit, one can use the library function isdigit . To use this, include header file ctype.h by means of this statement:

                #include<ctype.h>

                isdigit(CH)

To read in single characters as well as skip input blanks, you can use the following:

        do 
        {
                cin.get(ch);
        }while (ch == ' ');

It may be useful to design a function PUSHOP which pushes an operator of given precedence onto the OPERATOR STACK, after, if necessary, first performing a "reduction." Thus, PUSHOP calls the "regular" stack PUSH procedure. It also modifies the operation code number based on the level number.

Create your own input file for each program and show enough cases to show what your program actually does. For each program, turn in your program code, and your input and output files.

The output should echo the input (similar to what was shown at the beginning of this assignment).