c++visual-studiogccexpressionundefined-behavior

Different output on GCC and on Visual Studio


I tried to write a program in CPP which gets an infix expression, turns it into a postfix expression and then calculates the expression, using a stack-class executed by me. I thought what I wrote works because I ran several tests on it on Visual Studio. But I don't know why, the tests have result X on Visual Studio and result Y on GCC. For an example, when I run the program and enter (5+3)*((20/10)+(8-6)) on Visual Studio, it prints 32. On GCC, on the other hand, it prints 0.

So, my question is whether someone knows what might cause this difference? Maybe something different in the compilers?

I think that it might be caused by Undefined Behaviour. But even if it does, I have no about idea about where it is invoked...

(Btw, in GCC Instead of separating the Stack.h to a different file, I just wrote it above main - the output is still different on Visual Studio)

main.cpp :

#include "Stack.h"
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool operatorsPrecedenceCheck(string& str, Stack<char>& stk, const char& ch)
{
    if (ch == '+' || ch == '-')
    {
        Stack<char> help(stk.getSize());
        char stkTop = '\0';
        if (!stk.isEmpty())
            stkTop = stk.top();
        while (!stk.isEmpty() && stkTop != '(')
        {
            stkTop = stk.top();
            if (stk.top() == '*' || stk.top() == '/')
            {
                str += stk.pop();
                str += ' ';
            }
            else
                help.push(stk.pop());
        }
        while (!help.isEmpty())
            stk.push(help.pop());

        stk.push(ch);

        return 1;
    }
    else if (ch == '*' || ch == '/')
    {
        stk.push(ch);

        return 1;
    }


    return 0;

}
bool parenthesisCheck(string& str, Stack<char>& stk, const char& ch)
{
    if (ch == '(')
    {
        stk.push(ch);

        return 1;
    }
    else if (ch == ')')
    {
        while (stk.top() != '(')
        {
            str += stk.pop();
            str += ' ';
        }
        stk.pop();

        return 1;
    }

    return 0;

}

string infixToPostfix(const string& exp)
{
    string str = "";
    Stack<char> stk(exp.length());
    bool actionExecuted = 0;
    for (int i = 0; i < exp.length(); ++i)
    {
        actionExecuted = parenthesisCheck(str, stk, exp[i]);
        if (!actionExecuted)
            actionExecuted = operatorsPrecedenceCheck(str, stk, exp[i]);
        if (!actionExecuted)
        {
            if (exp[i] >= '0' && exp[i] <= '9')
            {
                for (; exp[i] >= '0' && exp[i] <= '9'; ++i)
                    str += exp[i];

                str += ' ';
                --i;
            }
            else
                throw"An illegal value in the expression\n";
        }
    }
    while (!stk.isEmpty())
    {
        str += stk.pop();
        str += ' ';
    }

    str = str.substr(0, str.length() - 1); //Cause of space

    return str;

}

int getValueFromString(const string& str, int& i)
{
    int result = 0;
    int amountOfDigits = 0;
    while (str[i + amountOfDigits] >= '0' && str[i + amountOfDigits] <= '9')
        ++amountOfDigits;

    for (int j = pow(10, amountOfDigits - 1); j >= 1; j /= 10)
        result += (str[i++] - '0') * j;
    --i;

    return result;
}

float calcPostfix(const string& str)
{
    Stack<int>stk(str.length() / 2);
    for (int i = 0; i < str.length(); i += 2)
    {
        if (str[i] >= '0' && str[i] <= '9')
            stk.push(getValueFromString(str, i));
        else if (str[i] == '/')
            stk.push((float)1 / stk.pop() * stk.pop());
        else if (str[i] == '*')
            stk.push(stk.pop() * stk.pop());
        else if (str[i] == '+')
            stk.push(stk.pop() + stk.pop());
        else if (str[i] == '-')
            stk.push(-1 * (stk.pop() - stk.pop()));
        else
            throw"Unknown Operator in Calculating Postfix\\n";
    }

    return stk.top();

}

int main()
{
    try
    {
        string exp;
        cout << "enter an infix expression as a string" << endl;
        cin >> exp;
        string postfix = infixToPostfix(exp);
        cout << postfix << endl;
        cout << calcPostfix(postfix) << endl;
    }
    catch (const char* exc)
    {
        cout << exc;
        exit(-1);
    }
    catch (...)
    {
        cout << "Unknown Error has occured\\n";
        exit(-1);
    }

    return 0;

}

Stack.h :

#ifndef MYSTACK_H
#define MYSTACK_H

template <class T>
class Stack
{
    //Inner class help
    void swap(Stack<T> &a, Stack<T>& b);

    T* data;
    int capacity;
    int size;
public:
    //Constructors & Destructor
    Stack();
    Stack(int capacity_);
    Stack(const Stack<T>& toCopy);
    Stack(Stack<T>&& toMove);
    ~Stack();

    //Methods
    int getCapacity() const;
    int getSize() const;
    void clear();
    bool isEmpty() const;
    bool isFull() const;
    T pop();
    void push(const T& toInsert);
    T top() const;

    //Operators
    Stack<T>& operator= (const Stack<T>& toAssign);
    Stack<T>& operator=(Stack<T>&& toMove);
};

//Inner class help
template<class T>
void Stack<T>::swap(Stack<T>& a, Stack<T>& b)
{
    T* temp_1 = a.data;
    a.data = b.data;
    b.data = temp_1;

    int temp_2 = a.size;
    a.size = b.size;
    b.size = temp_2;

    temp_2 = a.capacity;
    a.capacity = b.capacity;
    b.capacity = temp_2;
}

//Constructors & Destructor
template<class T>
Stack<T>::Stack() : data(nullptr), capacity(0), size(0) {}
template<class T>
Stack<T>::Stack(int capacity_) : capacity(capacity_), size(0) 
{
    data = new T[capacity];
    if (!data)
        throw "ERROR - couldn't allocate memory\n";
}
template<class T>
Stack<T>::Stack(const Stack<T>& toCopy)
{
    size = 0;
    capacity = toCopy.capacity;
    data = new T[capacity];
    if (!data)
        throw "ERROR - couldn't allocate memory\n";

    for (int i = 0; i < toCopy.size; ++i, ++size)
        data[i] = toCopy.data[i];
}
template<class T>
Stack<T>::Stack(Stack<T>&& toMove)
{
    data = nullptr;
    size = capacity = 0;

    swap(*this, toMove);
}
template<class T>
Stack<T>::~Stack()
{
    clear();
}

//Methods
template<class T>
int Stack<T>::getSize() const
{
    return size;
}
template<class T>
int Stack<T>::getCapacity() const
{
    return capacity;
}
template<class T>
void Stack<T>::clear()
{
    if (data)
    {
        delete[] data;
        data = nullptr;
    }
    size = capacity = 0;
}
template <class T>
bool Stack<T>::isEmpty() const
{
    return size == 0;
}
template <class T>
bool Stack<T>::isFull() const
{
    return size == capacity;
}
template <class T>
T Stack<T>::pop()
{
    if (isEmpty())
        throw"Couldn't pop - Stack is empty\n";

    T toReturn = data[--size];
    T* temp = new T[capacity];
    if (!temp)
        throw "ERROR - couldn't allocate memory\n";
    for (int i = 0; i < size; i++)
        temp[i] = data[i];

    delete[]data;
    data = temp;
    
    return toReturn;
}
template <class T>
void Stack<T>::push(const T& toInsert)
{
    if (isFull())
        throw "Couldn't push - stack is full\n";

    T* temp = new T[capacity];
    if (!temp)
        throw "ERROR - couldn't allocate memory\n";
    for (int i = 0; i < size; i++)
        temp[i] = data[i];

    temp[size++] = toInsert;
    delete[]data;
    data = temp;
}
template<class T>
T Stack<T>::top() const
{
    if (isEmpty())
        throw"Couln't return top - Stack is empty\n";

    return data[size - 1];
}

//Operators
template<class T>
Stack<T>& Stack<T>::operator=(const Stack<T>& toAssign)
{
    if (data)
        delete[]data;

    Stack<T>help = toAssign;
    swap(*this,help);
    return *this;
}
template<class T>
Stack<T>& Stack<T>::operator=(Stack<T>&& toMove)
{
    if (data)
        delete[]data;

    data = nullptr;
    size = capacity = 0;
    
    swap(*this, toMove);
    return *this;
}

#endif

Code on GCC

template <class T>
class Stack
{
    //Inner class help
    void swap(Stack<T> &a, Stack<T>& b);

    T* data;
    int capacity;
    int size;
public:
    //Constructors & Destructor
    Stack();
    Stack(int capacity_);
    Stack(const Stack<T>& toCopy);
    Stack(Stack<T>&& toMove);
    ~Stack();

    //Methods
    int getCapacity() const;
    int getSize() const;
    void clear();
    bool isEmpty() const;
    bool isFull() const;
    T pop();
    void push(const T& toInsert);
    T top() const;

    //Operators
    Stack<T>& operator= (const Stack<T>& toAssign);
    Stack<T>& operator=(Stack<T>&& toMove);
};

//Inner class help
template<class T>
void Stack<T>::swap(Stack<T>& a, Stack<T>& b)
{
    T* temp_1 = a.data;
    a.data = b.data;
    b.data = temp_1;

    int temp_2 = a.size;
    a.size = b.size;
    b.size = temp_2;

    temp_2 = a.capacity;
    a.capacity = b.capacity;
    b.capacity = temp_2;
}

//Constructors & Destructor
template<class T>
Stack<T>::Stack() : data(nullptr), capacity(0), size(0) {}
template<class T>
Stack<T>::Stack(int capacity_) : capacity(capacity_), size(0) 
{
    data = new T[capacity];
    if (!data)
        throw "ERROR - couldn't allocate memory\n";
}
template<class T>
Stack<T>::Stack(const Stack<T>& toCopy)
{
    size = 0;
    capacity = toCopy.capacity;
    data = new T[capacity];
    if (!data)
        throw "ERROR - couldn't allocate memory\n";

    for (int i = 0; i < toCopy.size; ++i, ++size)
        data[i] = toCopy.data[i];
}
template<class T>
Stack<T>::Stack(Stack<T>&& toMove)
{
    data = nullptr;
    size = capacity = 0;

    swap(*this, toMove);
}
template<class T>
Stack<T>::~Stack()
{
    clear();
}

//Methods
template<class T>
int Stack<T>::getSize() const
{
    return size;
}
template<class T>
int Stack<T>::getCapacity() const
{
    return capacity;
}
template<class T>
void Stack<T>::clear()
{
    if (data)
    {
        delete[] data;
        data = nullptr;
    }
    size = capacity = 0;
}
template <class T>
bool Stack<T>::isEmpty() const
{
    return size == 0;
}
template <class T>
bool Stack<T>::isFull() const
{
    return size == capacity;
}
template <class T>
T Stack<T>::pop()
{
    if (isEmpty())
        throw"Couldn't pop - Stack is empty\n";

    T toReturn = data[--size];
    T* temp = new T[size];
    if (!temp)
        throw "ERROR - couldn't allocate memory\n";
    for (int i = 0; i < size; i++)
        temp[i] = data[i];

    delete[]data;
    data = temp;
    
    return toReturn;
}
template <class T>
void Stack<T>::push(const T& toInsert)
{
    if (isFull())
        throw "Couldn't push - stack is full\n";

    T* temp = new T[size + 1];
    if (!temp)
        throw "ERROR - couldn't allocate memory\n";
    for (int i = 0; i < size; i++)
        temp[i] = data[i];

    temp[size++] = toInsert;
    delete[]data;
    data = temp;
}
template<class T>
T Stack<T>::top() const
{
    if (isEmpty())
        throw"Couln't return top - Stack is empty\n";

    return data[size - 1];
}

//Operators
template<class T>
Stack<T>& Stack<T>::operator=(const Stack<T>& toAssign)
{
    if (data)
        delete[]data;

    Stack<T>help = toAssign;
    swap(*this,help);
    return *this;
}
template<class T>
Stack<T>& Stack<T>::operator=(Stack<T>&& toMove)
{
    if (data)
        delete[]data;

    data = nullptr;
    size = capacity = 0;
    
    swap(*this, toMove);
    return *this;
}

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool operatorsPrecedenceCheck(string& str, Stack<char>& stk, const char& ch)
{
if (ch == '+' || ch == '-')
    {
        Stack<char> help(stk.getSize());
        char stkTop = '\0';
        if (!stk.isEmpty())
            stkTop = stk.top();
        while (!stk.isEmpty() && stkTop!='(') //Not mentioned but required
        {
            stkTop = stk.top();
            if (stk.top() == '*' || stk.top() == '/')
            {
                str += stk.pop();
                str += ' ';
            }
            else
                help.push(stk.pop());
        }
        while (!help.isEmpty())
            stk.push(help.pop());

        stk.push(ch);
        
        return 1;
    }
    else if (ch == '*' || ch == '/')
    {
        stk.push(ch);

        return 1;
    }
    

    return 0;
}
bool parenthesisCheck(string& str, Stack<char>& stk, const char& ch)
{
    if (ch == '(')
    {
        stk.push(ch);

        return 1;
    }
    else if (ch == ')')
    {
        while (stk.top() != '(')
        {
            str += stk.pop();
            str += ' ';
        }
        stk.pop();

        return 1;
    }

    return 0;
}

string infixToPostfix(const string &exp)
{
    string str = "";
    Stack<char> stk(exp.length());
    bool actionExecuted = 0;
    for (int i = 0; i < exp.length(); ++i)
    {
        actionExecuted = parenthesisCheck(str, stk, exp[i]);
        if (!actionExecuted)
            actionExecuted = operatorsPrecedenceCheck(str, stk, exp[i]);
        if (!actionExecuted)
        {
            if (exp[i] >= '0' && exp[i] <= '9')
            {
                for (; exp[i] >= '0' && exp[i] <= '9'; ++i)
                    str += exp[i];

                str += ' ';
                --i;
            }
            else
                throw"An illegal value in the expression\n";
        }
    }
    while (!stk.isEmpty())
    {
        str += stk.pop();
        str += ' ';
    }

    str = str.substr(0,str.length() - 1); //Cause of space

    return str;
}

int getValueFromString(const string& str, int &i)
{
    int result = 0;
    int amountOfDigits = 0;
    while (str[i+amountOfDigits] >= '0' && str[i+amountOfDigits] <= '9')
        ++amountOfDigits;

        for (int j = pow(10,amountOfDigits-1); j>=1; j /= 10)
            result += (str[i++] - '0') * j;
        --i;

    return result;
}

float calcPostfix(const string& str)
{
    Stack<int>stk(str.length()/2);
    for (int i = 0; i < str.length(); i += 2)
    {
        if (str[i] >= '0' && str[i] <= '9')
            stk.push(getValueFromString(str, i));
        else if (str[i] == '/')
            stk.push((float)1 / stk.pop() * stk.pop());
        else if (str[i] == '*')
            stk.push(stk.pop() * stk.pop());
        else if (str[i] == '+')
            stk.push(stk.pop() + stk.pop());
        else if (str[i] == '-')
            stk.push(-1 * (stk.pop() - stk.pop()));
        else
            throw"Unknown Operator in Calculating Postfix\n";
    }

    return stk.top();
}

int main()
{
    try
    {
        string exp;
        cout << "enter an infix expression as a string" << endl;
        cin >> exp;
        string postfix = infixToPostfix(exp);
        cout << postfix << endl;
        cout << calcPostfix(postfix) << endl;
    }
    catch (const char* exc)
    {
        cout << exc;
        exit(-1);
    }
    catch (...)
    {
        cout << "Unknown Error has occured\n";
        exit(-1);
    }

    return 0;
}

Solution

  • In stk.pop() - stk.pop() there is no guarantee that the left hand pop() happens first, if you change to:

    auto a = stk.pop();
    auto b = stk.pop();
    stk.push(-1 * (a - b));
    

    You'll get the same behaviour across different compilers.

    You have the same problem in (float)1 / stk.pop() * stk.pop().

    Your original code with some added debugging: https://godbolt.org/z/xEKzeTzvn

    The fixed version: https://godbolt.org/z/oczef5hrj