I want to apologize in advance since this is like the second question I'm asking relating to this assignment. I am trying to write a program to convert a postfix expression into infix using a stack template class created by my professor (with some modifications of my own). The main method is supposed to read in input from a file in the order, "expected solution", then "input". The code works for a different implementation of the stack template but for another implementation it does not. I get different issues like, "terminate called recursively" or the program just stops abruptly with no error message. The main method is displayed below.
#include "stack.hpp"
using namespace std;
/*
NOTE: result will probably be different from solution and output "ERROR" since result
has a bunch of extra parentheses, but they are essentially the same infix expression.
*/
int main(){
//freopen("input_postfix2infix.txt", "r", stdin);
string input;
string solution;
int line_counter = 0;
while(cin >> solution){
cout << "Top of while loop" << endl;
cin >> input;
Stack<string> stack;
string result;
//The input file is in the format "expected_solution infix_expression",
//where expected_solution is the infix_expression in postfix format
cout << input << endl;
for(int i=0; i<input.length(); ++i){
char c = input.at(i);
if(isalnum(c))
{
string s;
s.push_back(c);
cout << "Before push; s = " << s << endl;
stack.push(s);
cout << "Letter pushed;" << " Stack: "; stack.display();
}
else
{
string op1 = stack.pop();
string op2 = stack.pop();
string exp = op2 + c + op1;
exp = '(' + exp + ')';
stack.push(exp);
}
// WRITE CODE HERE to store in 'result' the postfix transformation of 'input'
}
result = stack.pop();
// You need to do some extra stuff here to store in 'result' the postfix transformation of 'input'
// Checking whether the result you got is correct
if(solution == result){
cout << "line " << line_counter << ": OK [" << solution << " " << result << "]" << endl;
}else{
cout << "line " << line_counter << ": ERROR [" << solution << " " << result << "]" << endl;
}
line_counter++;
cout << endl << endl;
}
}
I commented out the file part and used the keyboard for stdin. When I enter the expected solution then the input, the program gets to a certain point then stops. Particularly, in the second iteration of the for loop, inside "stack.push(s)", right before "arr[topIndex + 1] = c;" is when it stops abruptly with no error message. It does not execute anything past that statement so, the stack only gets to push in the first string from the first for loop iteration. At this point, I have no idea what could be the problem. I used a bunch of cout statements to narrow down where the problem could be, but I do not understand what is causing the issue. Here is the code for the stack (stack.hpp and stack.cpp).
stack.hpp:
//#include <bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
// Ideally this would not be a huge number, you could also use a vector
#define MAXSIZE 100000
using namespace std;
template<class T>
class Stack{
private:
T* arr; // the actual stack
int topIndex; // index of the top element
int SIZE;
public:
Stack(){
SIZE = 100;
arr = (T*)malloc(sizeof(T)*SIZE);
topIndex = -1; // constructor
};
~Stack(){
cout << "Destructor" << endl;
free(arr);
}; // destructor
void push(T c); // push c to the list
T pop(); // return and remove the top element in the stack
T peek(); // return the top element in the stack
int size(); // returns the size of the stack
void display(); // display the stack in stdout
};
stack.cpp
#include "stack.hpp"
using namespace std;
template<class T>
void Stack<T>::push(T c){
cout << "Inside push" << endl;
if(topIndex == MAXSIZE-1){
cout<<"Stack overflow"<<endl;
return;
}
cout << "Before arr; topIndex = " << topIndex; cout << "; SIZE = " << SIZE << endl;
arr[topIndex + 1] = c;
cout << "After arr" << endl;
topIndex++;
if(topIndex == SIZE-1)
{
SIZE += 100;
arr = (T*)realloc(arr, sizeof(T)*SIZE);
}
}
template<class T>
T Stack<T>::pop(){
if(topIndex < 0){
cout<<"Cannot delete. Stack empty."<<endl;
}
return arr[topIndex--];
}
template<class T>
T Stack<T>::peek(){
if(topIndex < 0){
cout<<"Cannot peek. Stack empty."<<endl;
}
return arr[topIndex];
}
template<class T>
int Stack<T>::size(){
return topIndex+1;
}
template<class T>
void Stack<T>::display(){
for(int i=topIndex; i>=0; --i){
cout<<arr[i]<<"\t";
}
cout<<endl;
}
template class Stack<char>;
template class Stack<int>;
template class Stack<string>;
However, when I compile and run main with the original stack.hpp and stack.cpp files (i.e. the ones my professor made), everything works perfectly. Below is my professor's original stack.cpp and stack.hpp files (the only modification is MAXSIZE = 100 instead of 100000 since 100000 is too large, also I added "template class Stack<string>;" at the end of the .cpp file so that the template can work for strings).
stack.hpp (original by professor):
//#include <bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
// Ideally this would not be a huge number, you could also use a vector
#define MAXSIZE 100 //This was originally 100000 but that was too large when using strings so I cut it down to 100
using namespace std;
template<class T>
class Stack{
private:
T arr[MAXSIZE]; // the actual stack
int topIndex; // index of the top element
public:
Stack(){
topIndex = -1; // constructor
};
~Stack(){}; // destructor
void push(T c); // push c to the list
T pop(); // return and remove the top element in the stack
T peek(); // return the top element in the stack
int size(); // returns the size of the stack
void display(); // display the stack in stdout
};
stack.cpp (original by professor):
#include "stack.hpp"
using namespace std;
template<class T>
void Stack<T>::push(T c){
if(topIndex > MAXSIZE-1){
cout<<"Stack overflow"<<endl;
return;
}
arr[topIndex + 1] = c;
topIndex++;
}
template<class T>
T Stack<T>::pop(){
if(topIndex < 0){
cout<<"Cannot delete. Stack empty."<<endl;
}
return arr[topIndex--];
}
template<class T>
T Stack<T>::peek(){
if(topIndex < 0){
cout<<"Cannot peek. Stack empty."<<endl;
}
return arr[topIndex];
}
template<class T>
int Stack<T>::size(){
return topIndex+1;
}
template<class T>
void Stack<T>::display(){
for(int i=topIndex; i>=0; --i){
cout<<arr[i]<<"\t";
}
cout<<endl;
}
template class Stack<char>;
template class Stack<int>;
template class Stack<string>;
The main modification is that I tried to implement a dynamic array instead of a static one so that the size of the array would not have to be unnecessarily large and cause problems. I spent hours trying to deduce what the issue is, but I just cannot figure it out. Previously, my code would not run because the array size was so large (as previously stated, MAXSIZE was 100000 so I changed it to 100) and thus was probably causing stack overflow when I used it with strings so, I reduced it and it worked. Now I am having this issue. Could stack overflow be the problem again? Any help understanding what's going on would be greatly be appreciated. Thank you!
