Review C++ RPN Evaluator

Question

So for Homework I had to write an RPN Evaluator and write the results to a text file. I've done all that - fine and dandy but it feels weird. Like the writing to my results text file. It doesn't feel efficient. There are some constraints like no Vector or String Libraries and no other external classes besides my stack. Any tips on how I can improve this?

Here are pastebin files: Main.cpp, Stack.h, RPN Expressions, and my Results Output File

Main.cpp

#include <iostream>
#include <iomanip>
#include <fstream>
#include <ctype.h>
using namespace std;
#include "stack.h"
//**************************************************************************
bool writeOperate(Stack<int>&, ofstream&, char);
void writePush(Stack<int>&, ofstream&, char[]);
void getResult(Stack<int>&, ofstream&, bool);
//**************************************************************************
int main()
{
    char token[3];
    bool valid = true;
    Stack<int> stack(10);
    ifstream expressions;
    ofstream results;

    expressions.open("expressions.txt");
    results.open("results.txt");

    while(expressions >> token)
    {
        if(token[0] == ';')
            getResult(stack, results, valid);
        else if(isdigit(token[0]))
            writePush(stack, results, token);
        else if(ispunct(token[0]))
            valid = writeOperate(stack, results, token[0]);
    }

    return 0;
}
//**************************************************************************
void writePush(Stack<int>& stack, ofstream& file, char* numStr)
{
    int num = atoi(numStr);

    cout << numStr << " ";
    stack.push(num);
    file << "(Token: " << numStr << left << setfill(' ') << setw(15) << ")" ;
    file << "Push " << numStr << endl;
}
//**************************************************************************
bool writeOperate(Stack<int>& stack, ofstream& file, char op)
{
    int num1,
        num2;
    int total = 0;
    bool success = false;

    cout << op << " ";
    stack.pop(num2);

    if(stack.pop(num1))
    {
        switch (op)
        {
            case '+':
                total = num1 + num2;
                break;
            case '-':
                total = num1 - num2;
                break;
            case '*':
                total = num1 * num2;
                break;
            case '/':
                total = num1 / num2;
                break;
            case '%':
                total = num1 % num2;
                break;
        }
        stack.push(total);
        success = true;
    }

    file << "(Token: " << op << left << setfill(' ') << setw(15) << ")";
    file << "Pop " << left << setfill(' ') << setw(15) << num1;
    file << "Pop " << left << setfill(' ') << setw(15) << num2;
    file << "Push " << total << endl;
    return success;
}
//**************************************************************************
void getResult(Stack<int>& stack, ofstream& file, bool success)
{
    int total;
    int size = stack.getSize();

    if(size == 1 && success)
    {
        stack.pop(total);
        cout << "= " << total << endl;
        file << "\t\t\t\t";
        file << left << setfill(' ') << setw(15) << "Valid: ";
        file << "result = " << total;
        size--;
    }
    else
    {
        cout << "= Invalid" << endl;
        file << "\t\t\t\t";
        file << "RPN Expressions is Invalid";
    }

    file << "\n\n\n";

    for(int i = 0; i < size; i++)
    {
        stack.pop(total);
    }
}

Stack.h

#ifndef STACK_H
#define STACK_H
//**************************************************************************
template<typename TYPE>
class Stack
{
    private:
        TYPE* stack;
        int top,
            capacity;

    public:
        Stack(int c = 100);
        ~Stack();
        bool push(const TYPE&);
        bool pop(TYPE&);
        bool peek (TYPE&) const;
        bool isEmpty() const;
        bool isFull() const;
        int getSize() const;
};
//**************************************************************************
template<typename TYPE>
Stack<TYPE>::Stack(int c)
{
    capacity = c;
    stack = new(nothrow) TYPE[capacity];
    top = -1;
};
//**************************************************************************
template<typename TYPE>
Stack<TYPE>::~Stack()
{
    delete[] stack;
    capacity = 0;
    top = -1;
};
//**************************************************************************
template<typename TYPE>
bool Stack<TYPE>::push(const TYPE& dataIn)
{
    bool success = false;

    if(top + 1 < capacity)
    {
        top++;
        stack[top] = dataIn;
        success = true;
    }

    return success;
};
//**************************************************************************
template<typename TYPE>
bool Stack<TYPE>::pop(TYPE& dataOut)
{
    bool success = false;

    if(top > -1)
    {
        dataOut = stack[top];
        top--;
        success = true;
    }

    return success;
};
//**************************************************************************
template<typename TYPE>
bool Stack<TYPE>::peek(TYPE& dataOut) const
{
    bool success = false;

    if(top > -1)
    {
        dataOut = stack[top];
        success = true;
    }

    return success;
};
//**************************************************************************
template<typename TYPE>
int Stack<TYPE>::getSize() const
{
    return (top + 1);
};
//**************************************************************************
template<typename TYPE>
bool Stack<TYPE>::isEmpty() const
{
    return (top == -1);
};
//**************************************************************************
template<typename TYPE>
bool Stack<TYPE>::isFull() const
{
    return (top + 1 == capacity);
};

#endif

Expressions.txt

2   4   *   5   +   ;
13  5   %   5   +   ;
15  1   +   2   /   1   -   ;
15  +   1   +   2   /   1   -   ;
3   4   +   15  10  -   *   ;
3   4   +   6   15  10  -   *   ;
4   5   -   7   *   2   3   +   +   ;
2   13  +   14  6   -   -   5   *   4   +   ;
35  6   4   2   2   /   +   *   -   ;
3   4   +   1   2   -   *   4   2   /   3   -   +   ;
3   14  1   2   4   2   3   +   %   *   +   -   +   ;
9   2   1   +   /   11  *   ;

Results.txt

(Token: 2)              Push 2
(Token: 4)              Push 4
(Token: *)              Pop 2              Pop 4              Push 8
(Token: 5)              Push 5
(Token: +)              Pop 8              Pop 5              Push 13
                Valid:         result = 13


(Token: 13)              Push 13
(Token: 5)              Push 5
(Token: %)              Pop 13             Pop 5              Push 3
(Token: 5)              Push 5
(Token: +)              Pop 3              Pop 5              Push 8
                Valid:         result = 8


(Token: 15)              Push 15
(Token: 1)              Push 1
(Token: +)              Pop 15             Pop 1              Push 16
(Token: 2)              Push 2
(Token: /)              Pop 16             Pop 2              Push 8
(Token: 1)              Push 1
(Token: -)              Pop 8              Pop 1              Push 7
                Valid:         result = 7


(Token: 15)              Push 15
(Token: +)              Pop -858993460     Pop 15             Push 0
(Token: 1)              Push 1
(Token: +)              Pop -858993460     Pop 1              Push 0
(Token: 2)              Push 2
(Token: /)              Pop -858993460     Pop 2              Push 0
(Token: 1)              Push 1
(Token: -)              Pop -858993460     Pop 1              Push 0
                RPN Expressions is Invalid


(Token: 3)              Push 3
(Token: 4)              Push 4
(Token: +)              Pop 3              Pop 4              Push 7
(Token: 15)              Push 15
(Token: 10)              Push 10
(Token: -)              Pop 15             Pop 10             Push 5
(Token: *)              Pop 7              Pop 5              Push 35
                Valid:         result = 35


(Token: 3)              Push 3
(Token: 4)              Push 4
(Token: +)              Pop 3              Pop 4              Push 7
(Token: 6)              Push 6
(Token: 15)              Push 15
(Token: 10)              Push 10
(Token: -)              Pop 15             Pop 10             Push 5
(Token: *)              Pop 6              Pop 5              Push 30
                RPN Expressions is Invalid


(Token: 4)              Push 4
(Token: 5)              Push 5
(Token: -)              Pop 4              Pop 5              Push -1
(Token: 7)              Push 7
(Token: *)              Pop -1             Pop 7              Push -7
(Token: 2)              Push 2
(Token: 3)              Push 3
(Token: +)              Pop 2              Pop 3              Push 5
(Token: +)              Pop -7             Pop 5              Push -2
                Valid:         result = -2


(Token: 2)              Push 2
(Token: 13)              Push 13
(Token: +)              Pop 2              Pop 13             Push 15
(Token: 14)              Push 14
(Token: 6)              Push 6
(Token: -)              Pop 14             Pop 6              Push 8
(Token: -)              Pop 15             Pop 8              Push 7
(Token: 5)              Push 5
(Token: *)              Pop 7              Pop 5              Push 35
(Token: 4)              Push 4
(Token: +)              Pop 35             Pop 4              Push 39
                Valid:         result = 39


(Token: 35)              Push 35
(Token: 6)              Push 6
(Token: 4)              Push 4
(Token: 2)              Push 2
(Token: 2)              Push 2
(Token: /)              Pop 2              Pop 2              Push 1
(Token: +)              Pop 4              Pop 1              Push 5
(Token: *)              Pop 6              Pop 5              Push 30
(Token: -)              Pop 35             Pop 30             Push 5
                Valid:         result = 5


(Token: 3)              Push 3
(Token: 4)              Push 4
(Token: +)              Pop 3              Pop 4              Push 7
(Token: 1)              Push 1
(Token: 2)              Push 2
(Token: -)              Pop 1              Pop 2              Push -1
(Token: *)              Pop 7              Pop -1             Push -7
(Token: 4)              Push 4
(Token: 2)              Push 2
(Token: /)              Pop 4              Pop 2              Push 2
(Token: 3)              Push 3
(Token: -)              Pop 2              Pop 3              Push -1
(Token: +)              Pop -7             Pop -1             Push -8
                Valid:         result = -8


(Token: 3)              Push 3
(Token: 14)              Push 14
(Token: 1)              Push 1
(Token: 2)              Push 2
(Token: 4)              Push 4
(Token: 2)              Push 2
(Token: 3)              Push 3
(Token: +)              Pop 2              Pop 3              Push 5
(Token: %)              Pop 4              Pop 5              Push 4
(Token: *)              Pop 2              Pop 4              Push 8
(Token: +)              Pop 1              Pop 8              Push 9
(Token: -)              Pop 14             Pop 9              Push 5
(Token: +)              Pop 3              Pop 5              Push 8
                Valid:         result = 8


(Token: 9)              Push 9
(Token: 2)              Push 2
(Token: 1)              Push 1
(Token: +)              Pop 2              Pop 1              Push 3
(Token: /)              Pop 9              Pop 3              Push 3
(Token: 11)              Push 11
(Token: *)              Pop 3              Pop 11             Push 33
                Valid:         result = 33

Answer 1

Review of plain code:

Stack:

You have made the choice to use top to represent the current top (a valid choice). Personally I would have used top to represent the insertion point of the next item. This way it will never become negative and most of the utility functions at the end become much nicer to read. Note if the top can never be negative you can use unsigned variants of int, such as std::size_t, to represent your data.

        int top,
            capacity;

Stop being lazy, and make each member's type explicit.
In every workplace I have come across, they ban this. There are a couple of corner cases where it can go wrong, so they just plain disallow it.

You should not be using no throw variants of new (in 99.999% of the time). If you really do need it (you don't) then you need to take the appropriate action to validate that new worked correctly.

    stack = new(nothrow) TYPE[capacity];

The destructor is for tidying up resources.

    capacity = 0;
    top = -1;

There is no point in doing meaningless work (like the above) when the members are not going to exist as soon as the destructor empties.

Also you basically implemented your own (simplified) vector internally to your Stack class. It would have been a lot simpler if you had used std::vector<TYPE> rather than TYPE*. The problem is that when your class contains a RAW owned pointer, you need to do extra work to make sure that the compiler generated methods don't mess up.

The following methods are generated for you by the compiler:

• Default Constructor (not in this case since you have a constructor)
• Copy Constructor
• Assignment Operator
• Destructor

The basic rule is that if you need to define any of the last three (doing real work), then you need to define all three of them (it's known as the rule of three (rule of five in C++11)). In this case you need to define the copy constructor and assignment operator (or disable them).

Since you don't seem to be using them you should disable them:

 class Stack
 {
     private:
         Stack(Stack const& copy);            // Deliberately not defined.
         Stack& operator=(Stack const& copy); // Deliberately not defined.
 };

headers

In C++, all the C header files are available in two versions. <X>.h and c<X>. The first version is the C version and puts all the identifiers in the global namespace. The second version is the C++ version and puts all the identifiers in the std:: namespace (it is implementation defined if the identifiers are placed in both by the headers).

Thus it is generally good practice to always use the C++ versions of these headers when writing C++ code.

#include <ctype.h>
// Replace with
#include <cctype>

This is only OK for small demo programs. Get out of the habit of using it (it is a very bad habit and is hard to break later).

using namespace std;

Using it pollutes the current namespace (in this case global) and can cause clashes with other code that will be a pain in any real program.

main()

Why not declare an open in one go:

ifstream expressions;
ofstream results;


expressions.open("expressions.txt");
results.open("results.txt");

Much easier to write and read as:

std::ifstream    expressions("expressions.txt");
std::ofstream    results("results.txt");

You had better hope that token is no longer than 2 characters long

while(expressions >> token)

Remember you declared this: char token[3];. The third place is going to be a \0'. It is always better to use std::string for this type of thing; if it is not large enough, it will dynamically expand to prevent a crash.

The following conditions are fine as long as you know that your input has already been sanitized.

    if(token[0] == ';')
        getResult(stack, results, valid);
    else if(isdigit(token[0]))
        writePush(stack, results, token);
    else if(ispunct(token[0]))
        valid = writeOperate(stack, results, token[0]);

Any funky input is going to cause your program to go haywire. I would assume that your input is not sanitized and take the appropriate steps to validate that the input is exactly what you expect.

std::string token;
while(expressions >> token)
{
    // Note the use of ""; this does an exact string comparison to make sure
    // that we are not swallowing any other characters.
    if(token == ";")
        getResult(stack, results, valid);

    // Make sure that puctuation tokens are exactly 1 character long.
    else if (ispunct(token[0]) && token.size() == 1)
        valid = writeOperate(stack, results, token[0]);

    // Otherwise assume is a number
    // Let the function writePush() validate it varactiy and throw an exception
    // if there is something wrong.
    else
        writePush(stack, results, token);
}

return 0;

}

writePush(Stack& stack, ofstream& file, char* numStr)

The function atoi() does not check what the trailing characters are. So if your input contained "25+", you will silently ignore the '+', which may change the meaning of your expression. Or "1Loki" will be parsed with a result even though it has no meaning.

int num = atoi(numStr);

I would use the stringstream operator:

std::stringstream numstream(numStr);
int num;
char errorCheck;
if ((numstream >> num) && !(numstream >> errorCheck))
{
    // We reached here then we have a valid number.

    // It means that `numstream >> num` succeeded and we read a valid number
    // and `numstream >> errorCheck` (note the !) failed, and thus there was
    // no more input to read.
}

bool writeOperate(Stack& stack, ofstream& file, char op)

Since all your operators currently require two numbers, you should make sure that when popping them you get both:

stack.pop(num2);

if(stack.pop(num1))

Should be:

if(stack.pop(num2) && stack.pop(num1))

Answer 2

Once you've underflowed the stack, an expression is invalid. Every operation from that point til the next ; could be considered broken. Even if the expression later "recovers" and contains enough extra operands to look valid at the end, at some point along the way an invalid operation was performed and you can't trust the result.

I might suggest that you clear the stack as soon as you notice an error, and stop even doing operations (just eat tokens) til you see another ;.

Aside from that,

• In Stack<TYPE>::Stack(), you should probably let new throw. The object is in an unusable state if new (nothrow) returns null, and the first attempt to use it will trigger UB. What's worse is that you have no way of telling the caller that.