C++ Postfix Expressions Using Stacks

Question

I'm developing a program that calculates the result of a postfix expression for one of my computer science classes. The program uses a stack ADT to accomplish this.

I have written the program, but believe there may be an error because the result of some expressions are not correct. I'm not sure where my mistake is.

Also, when the input file is empty, the program produces a value of 32767. Where is that coming from?

Expression: 3 4 + 3 * Value = 21.

Expression: 5 4 3 2 1 - + / * Value = 0. (should be 5)

Expression: 9 5 2 4 + - 2 * * Value = 18. (should be -18)

Header File:

#ifndef STACK_H
#define STACK_H

#include <cstdlib>
#include <iostream>

class Stack
{
    public:
        typedef int Item;
        static const int CAPACITY = 50;

        // Constructor
        Stack() { used = 0; }

        // Modification Member Functions
        void push(Item entry) {
            data[used] = entry;
            ++used;
        }
        Item pop() {
            if(!empty())
            {
                --used;
                return data[used];
            }
        }

        // Constant Member Functions
        bool empty() const { return used == 0; }
        int size() const { return used; }

    private:
        // Data Members
        Item data[CAPACITY];
        int used;
};
#endif

Main Program:

#include <cstdlib>
#include <iostream>
#include <fstream>
#include "stack.h"
using namespace std;

int main()
{
    Stack s;
    string input;
    ifstream infile;
    int final, operand1, operand2, result;
    char infile_name[80];

    cout << "Enter input file name: ";
    cin >> infile_name;
    cout << endl;

    infile.open(infile_name);
    while(!infile)
    {
        cout << "Could not open file." << endl;
        return 0;
    }

    while (!infile.eof())
    {
        getline(infile, input);
        cout << "Expression: ";
        for (int i = 0; i < input.length(); i++)
        {
            cout << input[i];
            if(input[i] == '1' || input[i] == '2' || input[i] == '3' || input[i] == '4' || input[i] == '5' || input[i] == '6' || input[i] == '7' || input[i] == '8' || input[i] == '9')
                s.push(input[i] - '0');
            if(input[i] == '+')
                s.push(s.pop() + s.pop());
            if(input[i] == '-')
                s.push(s.pop() - s.pop());
            if(input[i] == '*')
                s.push(s.pop() * s.pop());
            if(input[i] == '/')
                s.push(s.pop() / s.pop());
        }
        final = s.pop();
        cout << endl << "Value = " << final << "." << endl << endl;
    }
}

Answer 1

One issue is that in the statement s.pop() - s.pop() (and similarly in division), there is no guarantee which s.pop() is called first. As such, the order that things are removed from the stack isn't consistent. You should do it as two separate calls.

auto oper1 = s.pop();
auto oper2 = s.pop();
s.push(oper1-oper2);

Your erroneous results are due to those two operations being performed in the wrong order, in your case.

Answer 2

Code like while (!infile.eof()) is virtually always an error. It will typically appear to read the last item of input twice (though even that isn't dependable).

Start by changing:

while (!infile.eof())
{
    getline(infile, input);

to:

while (getline(infile, input))

and see if it doesn't work better.

Also note that your stack.pop() doesn't return a value if the stack is empty:

Item pop() {
    if (!empty())
    {
        --used;
        return data[used];
    }
}

If (for example) you have extra operator, you'll try to use a value when it hasn't actually returned one, leading to undefined behavior.