Stack-based Calculator
 

Stack-based calculator

Top down design, make, private member functions, if statement, do/while loop.

Our next step will be to design and implement a small but useful program using the techniques that we learned so far. It will be a simple stack based calculator. Even though it is a very small project, we will follow all the steps of the design and implementation process. We'll start with the functional specification, then proceed with the architectural design, and finally implement the program.

Functional Specification

The stack-based calculator has a simple interface. It accepts user input in the form of numbers and operators. Numbers are stored in the LIFO type memory--they are pushed on the stack. Binary operators are applied to the two top level numbers popped from the stack, and the result of the operation is pushed on top of the stack. If there's only one number in the stack, it is substituted for both operands. After every action the contents of the whole stack is displayed.

Since effectively the calculator implements reverse Polish notation, there is no need for parentheses. For simplicity we will implement only four basic arithmetic operations. A sample session may look like this (user input follows the prompt '>'): 
> 3
    3
> 2
    3
    2
> +
    5
> +
    10

Design

The obvious top-level object is the calculator itself. It stores numbers in its memory and performs operations on them. Since we would like to be able to display the contents of the calculator's stack after every action, we need access to a stack sequencer. Finally, in order to completely decouple input/output operations from the calculator, we should have an input object that obtains input from the user and does some pre-processing (tokenization) to distinguish between numbers and operators.

We'll use the standard cout object for output.

The minimum lifetimes of these three objects are the following:

  • The calculator has to be alive during the whole session since it has long term memory.
  • The scope of the input object is associated with a single input operation.
  • The scope of the sequencer is associated with every stack display operation that follows a successful calculator action.

The input object obtains a string from the standard input. It can distinguish between numbers and operators, returning different tokens depending on the input. If the token is 'number' the string is converted to an int and the input object remembers its value.

The calculator object accepts the input object, from which it can get pre-digested data, and executes the command. If the data is a number, it stores it in a stack; if it is an operator, it performs the operation. The results can be viewed by creating a stack sequencer--the calculator may simply give access to its stack for the purpose of iteration.

Notice that we have only three types of objects interacting at the top level, plus one object, the stack, that we can treat as a black box (we don't call any of its methods, we just pass access to it from one component to another). This is not just a side effect of the simplicity of our project--we should always strive to have only a small number of top level objects.

Once the top level is established, we can start our top-down descent. In our design we may go one level deeper into the calculator object. We already know that it has a stack. The stack object will thus be embedded in it. We will re-use the stack that we used in the previous paragraph.

Stubbed Implementation

The top-down design will be followed by the top-down implementation. Based on our architectural specification we start to write the main procedure.

Download!
source 
void main ()
{
    Calculator TheCalculator;
    bool status;
    do
    {
        // Prompt for input
        cout << "> ";
        Input input;
        status = TheCalculator.Execute (input);
        if (status)
        {
            for (StackSeq seq (TheCalculator.GetStack ());
                !seq.AtEnd ();
                seq.Advance () )
            {
                cout << "    " << seq.GetNum () << endl;
            }
        }
    } while (status);
}

We have introduced some new constructs here, the do/while loop and the if statement. The execution of the body of the do/while loop is repeated as long as the condition in the while clause remains true. Notice that, unlike in the case of the for loop, the body of the do/while loop is always executed at least once. As should be obvious by now, the body of the loop forms a separate local scope (even if it is a single statement and the braces are omitted).

The body of the if statement is entered only if the condition in the if clause is true (different from zero). Otherwise it is skipped altogether. And again, the body of the if statement forms a local scope even if it is only one statement, in which case the braces may be omitted.

Notice also that the variable status is defined without being initialized. We try to avoid such situations in C++. Here I took the liberty of not initializing it, since it is always initialized inside the body of the do/while loop (and we know that it is executed at least once). I couldn't define the variable status inside the scope of the loop, because it is tested in the while clause which belongs to the outer scope. The while clause is evaluated during each iteration, after the body of the loop is executed.

Next, following the top-down approach, we'll write stub implementations for all classes. The stack is passed from the calculator to the sequencer and we don't need to know anything about it (other than that it's an object of class IStack). Hence the trivial implementation: 
class IStack {};

The sequencer has all the methods stubbed out. I have added to it a dummy variable, _done, to simulate the finiteness of the stack. GetNum returns the arbitrarily chosen number 13. 
class StackSeq
{
public:
    StackSeq (IStack const & stack) : _stack (stack), _done (false)
    {
        cout << "Stack sequencer created\n";
    }
    bool AtEnd () const { return _done; }
    void Advance () { _done = true; }
    int GetNum () const { return 13; }
private:
    IStack const &  _stack;
    bool            _done;
};

At this level of detail, the class Input exposes only its constructor: 
class Input
{
public:
    Input ()
    {
        cout << "Input created\n";
    }
};

The calculator, again, has a dummy variable whose purpose is to break out of the loop in main after just one iteration. 
class Calculator
{
public:
    Calculator () : _done (false)
    {
        cout << "Calculator created\n";
    }
    bool Execute (Input& input)
    {
        cout << "Calculator::Execute\n";
        return !_done;
    }
    IStack const & GetStack () const
    {
        _done = true;
        return _stack;
    }
private:
    IStack  _stack;
    bool    _done;
};

The method GetStack returns a const reference to IStack. In other words it makes a read-only alias for the calculator's private object _stack and makes it available to the caller. The user may use this alias to access _stack, but only through its const methods, or, if it is an IStack's friend, by reading the values of _top and those stored in the array _arr. This is exactly what the sequencer needs. Notice also that the statement return _stack is interpreted by the compiler to return a reference to _stack. This is because GetStack was declared as returning a reference. If GetStack were declared as 
IStack const GetStack () const;
the compiler would return a read-only copy of the stack. Copying the stack is somehow more expensive than providing a reference to it. We'll come back to this problem later, when we talk about value classes.

With all the dummies in place, we can compile and execute the test program. Its output shows that everything works as expected. 
Calculator created
> Input created
Calculator::Execute
Stack sequencer created
    13
> Input created
Calculator::Execute

Implementation

Calculator: Implementation

Now is the time to start the top to bottom descent. The first candidate for implementation is the Calculator itself. When implementing the calculator we'll find out what we need from the Input object. Let's start with the Execute method. First, it should retrieve the token from the input. We may expect the following tokens: the number token, any of the arithmetic operator tokens, or the error token. For each type we do a different thing. For the number token we retrieve the value of the number from the input and push it on the stack. For the operator, we pop two numbers (or one if there aren't two), pass them to the Calculate method and push the result.


Download!
source 
bool Calculator::Execute (Input const & input)
{
    int token = input.Token ();
    bool status = false; // assume failure

    if (token == tokError)
    {
        cout << "Unknown token\n";
    }
    else if (token == tokNumber)
    {
        if (_stack.IsFull ())
        {
            cout << "Stack is full\n";
        }
        else
        {
            _stack.Push (input.Number ());
            status = true; // success
        }
    }
    else
    {
        assert (token == '+' || token == '-' 
              || token == '*' || token == '/');

        if (_stack.IsEmpty ())
        {
            cout << "Stack is empty\n";
        }
        else
        {        
            int num2 = _stack.Pop ();
            int num1;

            // Special case, when only one number on the stack:
            // use this number for both operands.

            if (_stack.IsEmpty ())
                num1 = num2;
            else
                num1 = _stack.Pop ();

            _stack.Push (Calculate (num1, num2, token));
            status = true;
        }
    }
    return status;
}

We have introduced the extension of the conditional--the else clause. The body of the else statement is executed only if the preceding if statement hasn't been executed (because the condition was false).

If/else statement can be staggered like this: 
if (A)
    ...
else if (B)
    ...
else if (C)
    ...
else
    ...

Calculate is the new method of Calculator. Since it is used only inside the implementation of Calculator, it is made private. It takes two numbers and a token and it returns the result of the operation. I have separated this code into a method mostly because the Execute method was getting too large. Calculate has well defined functionality, quite independent from the rest of the code. It is implemented as one large staggered if/else construct. 
int Calculator::Calculate (int num1, int num2, int token) const
{
    int result;
	
    if (token == '+')
        result = num1 + num2;
    else if (token == '-')
        result = num1 - num2;
    else if (token == '*')
        result = num1 * num2;
    else if (token == '/')
    {
        if (num2 == 0)
        {
            cout << "Division by zero\n";
            result = 0;
        }
        else
            result = num1 / num2;
    }
    return result;
}
Notice the use of character literals such as 
'+', '-', '*', '/'.
Unlike string literals, character literals are surrounded by single quotes. Instead of assigning special values to operator tokens, we just used their character literal (ASCII) values.

Let's have a look at the modified class definition of the calculator. 
class Calculator
{
public:
    bool Execute ( Input& input );
    // give access to the stack
    IStack const & GetStack () const { return _stack; }
private:
    int Calculate (int n1, int n2, int token) const;

    IStack  _stack;
};

We may now add our old implementation of IStack and StackSeq, extend the dummy Input by adding dummy implementations of the methods Token and Number, recompile and test.

Input: Implementation

Now it's the time to implement the Input class. It's also time to split our project into separate files. We should have three header files--calc.h, stack.h and input.h--as well as three implementation files--calc.cpp, stack.cpp and input.cpp. To build an executable program out of multiple source files one needs the help of a linker. Fortunately, in an integrated environment you can create a project to which you add all the implementation files and let the environment build the program for you. We don't want to get too involved in such details here.

The more header files we have, the more likely it is that we will include the same file twice. How can this happen? Suppose that we include input.h inside calc.h. Then we include both calc.h and input.h inside calc.cpp, and we're in trouble. The compiler will see two definitions of class Input (they're identical, but so what). The way to protect ourselves from such situations is to guard the header files with conditional compilation directives. Let's enclose the whole body of input.h with the pair 
#if !defined input_h
...
#endif

If the symbol input_h is not defined, the compiler will process the code between these two preprocessor directives (as they are called). In the beginning, this symbol is not defined by anybody. So the first time the compiler encounters the #include "input.h" directive, it will go ahead processing input.h. However, the first directive inside the if/endif pair defines the symbol input_h 
#define input_h

Next time the #include "input.h" directive is encountered, the compiler will skip everything between #if !defined input_h and #endif since input_h has already been defined. 
#if !defined input_h   // prevent multiple inclusions
#define input_h

const int maxBuf = 100;

// Tokens are tokNumber, tokError, +, -, *, /.

const int tokNumber = 1;
const int tokError  = 2;

// Gets input from stdin, converts to token.

class Input
{
public:
        Input ();
        int Token () const { return _token; }
        int Number () const;
private:
        int  _token;
        char _buf [maxBuf];
};

#endif // input_h

Notice that the methods Token and Number are declared const. The Calculator who has read-only access to input (through a const reference) will still be able to call these methods. The buffer _buf is where the string obtained from the user will be stored.

The implementation file input.cpp includes two new standard headers. 
#include <cctype>
#include <cstdlib>

The file cctype contains the definitions of (very efficient) macros to recognize character type. The isdigit macro, for instance, returns true if the character is one of the digits between '0' and '9' and false otherwise. The other file, cstdlib, is needed for the declaration of the function atoi that converts an ASCII string representing a decimal number to an integer. You can find out more about functions like that by studying the standard library. You can either use online help or read the compiler manuals (or some other books). 
Input::Input ()
{
    cin >> _buf;

    // first char of input is usually enough to decide
    // what token it is

    int c = _buf [0]; 

    if (isdigit (c))
        _token = tokNumber;
    else if (c == '+' || c == '*' || c == '/')
        _token = c;
    else if (c == '-') // allow entering negative numbers
    {
        if (isdigit (_buf [1])) // peek at next char
            _token = tokNumber;
        else
            _token = c;
    }
    else
        _token = tokError;
}

The constructor of Input reads a line of text from the standard input into a character buffer. This is yet another amazing trick performed by our friend cin. (By the way, for the time being we are not even thinking about what could happen if the buffer overflows. We are still at the level of weekend programming.)

Depending on the first character in the buffer, we decide what token to make out of it. Notice the special treatment of the minus sign. It could be a binary minus, or it could be a unary minus in front of a number. To find out which one it is, we peek at the next character in the buffer. Notice the use of one of the character classification macros I mentioned before. isdigit returns true when the character is a digit (that is one of '0', '1', '2'... '9'). The character classification macros are implemented using a very efficient table lookup method. It is more efficient to call isdigit than execute code like this 
if ( c >= '0' && c <= '9' )

The header cctype contains other useful macros, besides isdigit, like isspace, islower and isupper.

If the token is tokNumber, the Calculator needs to know its value. The method Number converts the string in the buffer into an int value using the library function atoi declared in cstdlib. 
int Input::Number () const
{
    assert (_token == tokNumber);
    return atoi (_buf);   // convert string to integer
}

The Makefile

One final word for those of us who, for one reason or another, don't use an integrated environment to develop their code. When the project grows beyond a single file, it is time to start using the make utility. Below is a very simplified makefile that establishes the dependencies between various files in the project and provides the recipes to generate them: 
calc.exe : calc.obj stack.obj input.obj
    cl calc.obj stack.obj input.obj

calc.obj : calc.cpp calc.h input.h stack.h
    cl -c calc.cpp

stack.obj : stack.cpp stack.h
    cl -c stack.cpp

input.obj : input.cpp input.h
    cl -c input.cpp

If the makefile is called calc.mak, you just call make calc.mak (or nmake calc.mak) and all the necessary compilation and linking steps will be executed for you to create the executable calc.exe. Again, use online help or read manuals to find out more about make (or nmake).