I tried to write a program in CPP which gets an infix expression, turns it into a postfix expression and then calculates the expression.
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 GDB. For an example, when I run the program and enter (5+3)*((20/10)+(8-6)) on Visual Studio, it prints 32. On GDB, 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 GDB 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 expressionn";
}
}
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 memoryn";
}
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 memoryn";
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 emptyn";
T toReturn = data[--size];
T* temp = new T[size];
if (!temp)
throw "ERROR - couldn't allocate memoryn";
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 fulln";
T* temp = new T[size + 1];
if (!temp)
throw "ERROR - couldn't allocate memoryn";
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 emptyn";
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 GDB
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 memoryn";
}
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 memoryn";
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 emptyn";
T toReturn = data[--size];
T* temp = new T[size];
if (!temp)
throw "ERROR - couldn't allocate memoryn";
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 fulln";
T* temp = new T[size + 1];
if (!temp)
throw "ERROR - couldn't allocate memoryn";
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 emptyn";
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 = '';
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 expressionn";
}
}
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 Postfixn";
}
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 occuredn";
exit(-1);
}
return 0;
}
New contributor
CS Student is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.