Hello programmers!
I am working on a program that checks if a user's input is a palindrome (in this case, the input is a string).
I am using a custom class template "stack", that is a constrained version of my custom class "List", which is a linked list class template. Each item in the LinkedList is of a class template ListNode, and it has a pointer to the next item.
How my program works to check if a string it a palindrome:
It gets input from a user, removes spaces, removes punctionation marks, makes all letters lowercase, and then creates two stacks, which have the letters being pushed on it in reverse order for one, and in forward order for the other.
Then, I start popping the stacks and comparing for the equality between the two.
The main() program works just fine.
However, when the destructor for the stacks are called, which then calls the base class destructor, I get the following:
Palindrome testing with stacks(36206,0x7fff7d151310) malloc: *** error for object 0x100200090: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Could anyone suggest for me what to do regarding this message?
I never worked with malloc, so I do not know what to do. I was doing some debuggin in my xCode (for mac) debugger, and the destructor for List is called three times, even though I created two stacks (and therefore means that it has to be called two times).
The reason why I am catching this problem now is that I modified the stack and list class to behave as my demands of them required, so this is going on.
I would like for your attention to be directed to the Stack class and to the List class's destructor.
Here's my code:
// main.cpp
// A program that tests a string to see if it's a palindrome
#include <iostream>
#include <algorithm>
#include <string>
#include <ctype.h>
#include "Stack.h"
using namespace std;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
string getString(const string& msg)
{
//gets a desired string input from user
string input;
cout << msg << flush;
cin >> input;
return input;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool hasNum(const string& toTest)
{
//tests to see if toTest contains at least one character that is a num
for (auto iter=toTest.cbegin();iter != toTest.cend();++iter)
{
if (isnumber(*iter))
{
return true;
}
}
return false;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<typename T>
bool areEqual(Stack<T> stackOne,Stack<T> stackTwo)
{
T tempStackOne;
T tempStackTwo;
while (!(stackOne.isStackEmpty()))
{
stackOne.pop(tempStackOne);
stackTwo.pop(tempStackTwo);
if (tempStackOne != tempStackTwo)
return false;
}
return true;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
string input="";
//get a string from user
cout << "This is a program that tests if an inputted string is a palindrome\n" << endl;
do
{
input=getString("Enter a phrase (without any numbers in it) in to be tested: ");
if (hasNum(input))
{
cerr << "Input can not have any numeric characters." << endl;
cout << "Please try again." << endl;
}
}
while(hasNum(input));
//process string by removing all punctuation marks and spaces
input.erase(remove_if(input.begin(),input.end(),::ispunct),input.end());
//process by which all spaces are removed
input.erase(remove_if(input.begin(),input.end(),::isspace),input.end());
//convert all letters to lowercase
transform(input.begin(), input.end(), input.begin(), ::tolower);
//after this is done, create two stacks, in order, and reverse
Stack<char> forwardStack;
Stack<char> backwardStack;
//iterate backwards, and add the chars in order to forwardStack
for (auto iter=input.crbegin(); iter!=input.crend();++iter)
{
forwardStack.push(*iter);
}
for (auto iter=input.cbegin();iter!=input.cend();++iter)
{
backwardStack.push(*iter);
}
//check to see if the stacks are equal
cout << "\n\nThe input " << (areEqual(forwardStack, backwardStack)? "is":"is not") << " a palindrome.\n\n" << endl;
}
My Stack class:
// Stack.h
// Stack class-template definition using private inheritance of class List
#ifndef Stack_h
#define Stack_h
#include "List.h"
template<typename STACKTYPE>
class Stack : private List<STACKTYPE>
{
public:
//push calls the List function insertAtFront
void push(const STACKTYPE &data)
{
this->insertAtFront(data);
}
//pop calls the List function removeFromFront
bool pop(STACKTYPE &data)
{
return this->removeFromFront(data);
}
//isStackEmpty calls List function isEmpty
bool isStackEmpty() const
{
return (this->isEmpty());
}
//printStack calls the List function print
void printStack() const
{
this->print();
}
};
#endif
My List class (PAY ATTENTION TO DESTRUCTOR):
// List.h
// List class-template definition
#ifndef List_h
#define List_h
#include <iostream>
#include "ListNode.h"
template <typename NODETYPE>
class List
{
public:
//default constructor
List(): firstPtr(nullptr),lastPtr(nullptr)
{}
//destructor
~List()
{
emptyList();
std::cout << "All nodes destroyed\n\n";
}
//insert node at front of List
void insertAtFront(const NODETYPE& value)
{
ListNode<NODETYPE> *newPtr=getNewNode(value); //new node
if (isEmpty()) //List is empty
firstPtr=lastPtr=newPtr; //new List has only one node
else
{
//List is not empty
newPtr->nextPtr=firstPtr;
firstPtr=newPtr;
}
}
//insert node at back of List
void insertAtBack(const NODETYPE& value)
{
ListNode<NODETYPE> *newPtr=getNewNode(value); //new node
if (isEmpty())
firstPtr=lastPtr=newPtr; //new List has only one node
else
{
//list is not empty
lastPtr->nextPtr = newPtr; //update previous last node
lastPtr = newPtr;
}
}
//delete node from front of list [return boolean to signify if operation is successful]
bool removeFromFront(NODETYPE& value)
{
if (isEmpty()) //List is empty
return false; //delete unucessful
else
{
ListNode<NODETYPE> *tempPtr=firstPtr; //hold item to delete
if (firstPtr==lastPtr) //no nodes remain after removal
firstPtr=lastPtr=nullptr; //set all ptr's to nullptr
else //some nodes remain after removal
firstPtr=firstPtr->nextPtr; //set firstPtr to nextPtr
//return data being removed via the reference variable value
value=tempPtr->data; //return the data being removed
delete tempPtr; //reclaim previous front node
return true;
}
}
//delete node from back of list [return boolean to signify if operation is successful
bool removeFromBack(NODETYPE& value)
{
if (isEmpty()) //List is empty
return false; //delete unsuccessful
else
{
ListNode<NODETYPE> *tempPtr=lastPtr; //hold item to delete
if (firstPtr == lastPtr) //no nodes remain after removal
firstPtr=lastPtr=nullptr; //set all ptr's to nullptr
else
{
ListNode<NODETYPE>* currentPtr = firstPtr;
//locate second-to-last element
while (currentPtr->nextPtr != lastPtr)
currentPtr=currentPtr->nextPtr; //move to next node
lastPtr=currentPtr; //remove last node
currentPtr->nextPtr = nullptr; //this is now the last node
}
value = tempPtr->data; //return value from old last node
delete tempPtr; //reclaim former last node
return true;
}
}
//returns true if List is empty
bool isEmpty() const
{
return firstPtr==nullptr;
}
//display contents of List
void print() const
{
if (isEmpty()) //List is empty
{
std::cout << "The list is empty.\n\n";
return;
}
//continue by printing the list's contents
ListNode<NODETYPE> *currentPtr=firstPtr;
std::cout << "The list is: ";
while (currentPtr != nullptr) //get element data
{
std::cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
}
std::cout << "\n" << std::endl;
}
List<NODETYPE> operator=(const List<NODETYPE>& toAssign)
{
//check to see if the list is the same, to avoid assigning to self
if (this != &toAssign)
{
//empty the list being assigned to, and then assign toAssign's contents to this List
emptyList();
//iterate over toAssign's contents, and assign the contents to list
List<NODETYPE> *currentPtr=toAssign.firstPtr;
while (currentPtr != nullptr)
{
this->insertAtFront(currentPtr);
currentPtr=currentPtr->nextPtr; //get toAssign's next content
}
}
return *this;
}
NODETYPE& operator[](int subscript)
{
if ( subscript < 0 || subscript >= size())
throw std::out_of_range("Subscript out of range");
//subscript is in valid range -
//return a modifiable lvalue
int count=0;
ListNode<NODETYPE> *currentPtr=firstPtr;
while (count != subscript)
{
++count;
currentPtr=currentPtr->nextPtr;
}
return (currentPtr->data);
}
NODETYPE operator[](int subscript) const//returns non-modifiable rvalue
{
if (subscript < 0 || subscript >= size())
throw std::out_of_range("Subscript out of range");
//subscript is in valid range -
//return a non-modifiable lvalue
int count=0;
ListNode<NODETYPE> *currentPtr=firstPtr;
while (count != subscript)
{
++count;
currentPtr=currentPtr->nextPtr;
}
return (currentPtr->data);
}
unsigned size() //returns list size
{
if (isEmpty()) //List is empty
return 0; //size is 0
else
{
ListNode<NODETYPE> *currentPtr=firstPtr;
int sizeCount=0;
while (currentPtr != nullptr)
{
++sizeCount;
currentPtr=currentPtr->nextPtr;
}
return sizeCount;
}
}
void emptyList() //PROBLEMATIC FUNCTION IF THE DECISION IN THE IF STATEMENT EVALUATES TO TRUE
{
if (!isEmpty()) //List is not empty
{
std::cout << "Destroying nodes ...\n";
ListNode<NODETYPE> *currentPtr=firstPtr;
ListNode<NODETYPE> *tempPtr=nullptr;
while (currentPtr != nullptr) //delete remaining nodes
{
tempPtr=currentPtr;
std::cout << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
delete tempPtr;
}
}
}
private:
ListNode<NODETYPE> *firstPtr; //pointer to first node
ListNode<NODETYPE> *lastPtr; //pointer to last node
//utility function to allocate new node
ListNode<NODETYPE> *getNewNode(const NODETYPE& value)
{
return new ListNode<NODETYPE>(value);
}
};
#endif
And then my ListNode.h:
// ListNode class-template definition
#ifndef ListNode_h
#define ListNode_h
//forward declaration of class List is required to announce that class
//List exists so it can be used in the friend declaration at line 20
template<typename NODETYPE> class List;
template<typename NODETYPE>
class ListNode
{
friend class List<NODETYPE>; //make List a friend
public:
//constructor
explicit ListNode(const NODETYPE &info): data(info), nextPtr(nullptr)
{}
//return all data in node
NODETYPE getData() const
{
return data;
}
private:
NODETYPE data; //data
ListNode<NODETYPE> *nextPtr; //pointer to next node in list
};
#endif
I do not want people wasting their precious time on my code, but I am asking for some guidance in debugging, escpecially with the malloc message.
Here's an example of how the program runs leading up to the message:
This is a program that tests if an inputted string is a palindrome
Enter a phrase (without any numbers in it) in to be tested: abcba
The input is a palindrome.
All nodes destroyed
All nodes destroyed
Destroying nodes ...
Palindrome testing with stacks(36206,0x7fff7d151310) malloc: *** error for object 0x100200090: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
(lldb)
Many thanks!
