C++ HELP! How to write a program without using the STL classes?

?

2010-03-12 02:03:12 UTC

using stack to check for Palindrome ... :O)

#include

#include

using namespace std;

const int ciMaxStack = 3;

class CStack {

private:

int iCurrent;

int iMaxStack;

char *cData;

public:

CStack(char Data = 0, const int iStackSize = ciMaxStack) : iMaxStack(iStackSize), iCurrent(0)

{

cData = new char[iStackSize];

for (int i = 0; i < iMaxStack; i++) {

cData[i] = 0;

}

if (Data != 0){

cData[iCurrent] = Data;

}

else {

iCurrent = -1;

}

}

~CStack()

{

iCurrent = 0;

iMaxStack = 0;

delete [] cData;

cData = NULL;

}

void push(const char& Data)

{

if (iCurrent == iMaxStack - 1) {

int iMax = iMaxStack * 2;

char *pData = new char[iMax];

strncpy(pData, cData, iMaxStack);

for (int i = iMaxStack; i < iMax; i++) {

pData[i] = 0;

}

delete [] cData;

cData = pData;

iMaxStack = iMax;

}

cData[++iCurrent] = Data;

}

char pop()

{

char cRet = 0;

if (iCurrent > -1) {

cRet = cData[iCurrent];

}

cData[iCurrent--] = 0;

return cRet;

}

};

int main(int argc, char* argv[])

{

string a = "mottom", strTemp = "";

CStack b;

for (int i = 0; i < a.length(); i++) {

b.push(a[i]);

}

string c = "";

for (i = 0; i < a.length(); i++) {

c+= b.pop();

}

if (c.compare(a) ==0) {

cout << "Palindrome!" << endl;

}

else {

cout << "No Palindrome!" << endl;

}

system("pause");

return 0;

}

Mary

2016-04-12 04:45:17 UTC

the only thing i can think of is using goto. traverseRight: currentNode = currentNode->right; goto ifstatement; traverseLeft: currentNode = currentNode->left; ifstatement: if(...) //you like to go right goto traverseRight; else //you like to go left goto traverseLeft;

Jim

2010-03-11 23:54:54 UTC

the link I give is a good place to go for documentation about the STL, and if you dig hard enough, you will find tutorials there (not very navigable for finding the tutorials - it's under documentation).

string & vector don't have the capability to do a reverse, although that REALLY should be in the STL...

the 3rd link has more complete documentation, the first 2 have examples and looks nicer.

oops

2010-03-11 23:14:11 UTC

This problem has nothing to do with stacks, and I can't see how push and pop would help you with it. I'm assuming that you're teacher doesn't want you using the STL string class, but rather a char array. I would write a recursive function like this:

bool isPalindrome( char * str, char * end = NULL)

{

if(end == NULL)

{

end = str;

while(*end) ++end;

--end;

}

if(str >= end) return true;

if(*str == *end) return isPalindrome( str+1, end-1);

return false;

}

Daniel

2010-03-11 23:39:18 UTC

The below code is untested PHP. So you'll need to convert it to C++ and make sure it works, but it should definitely give you a good idea of how to get started. If you're unfamiliar with some of the PHP functions used below go to http://www.php.net and type it in where it says "search for" at the top right. Good luck!

// String which holds the potential palindrome. You can set it manually or get it from form data or where ever else.

$string = "potential palindrome";

// If you want the test to be case insensitive.

$string = strtolower($string);

// Int which holds the length of the above string (in this example it would be 20).

$length = count($string);

// Boolean which determines whether the string is a palindrome or not. We'll assume it is true unless the below code determines otherwise.

$palindrome = true;

// Loop through only the first half of the string (the reason for using floor is so that if the string doesn't divide evenly it means there is a character in the middle so we don't have to bother making sure it is the same as itself).

for($i = 0; $i < floor($length/2); $i++){

// Check to see if the current letter matches the letter on the opposing side. So the first test would check for position 0 ("p") and position 19 ("e"). The next test would be position 1 ("o") and position 18 ("m"). The final position would be 9 (" ") and 10 ("p").

if(substr($string, $i, 1) == substr($string, $length - $i - 1, 1)){

// The letters do match. Keep testing.

continue;

} else {

// The letters don't match, meaning the string is not a palindrome. Set the boolean to false and break out of the loop since no further testing is required.

$palindrome = false;

break;

}

}

// If the above code didn't change the boolean to false, it will remain true meaning the string is infact a palindrome.

if($palindrome){

echo "the following string IS a palindrome: " . $string;

} else {

echo "the following string IS NOT a palindrome: " . $string;

}

anonymous

2010-03-11 23:05:35 UTC

I think maybe they just dont want you to use the vector class and the reverse algorithm (part of the STL) - which would make writing your program really easy and quick.

just use for loops and stuff instead.

but this is what the STL is -> http://www.sgi.com/tech/stl/stl_introduction.html

cja

2010-03-12 05:37:37 UTC

There are STL containers that can be very useful here, but it seems the point of the assignment is to create your own container, a stack, and use it to check if a string is a palindrome. You say "I was thinking, you could pop the original stack to another and check if the two are the same", and you are correct. Here's how I would do it:

#include

#include

#include "Stack.h"

using namespace std;

bool isPalindrome(const string&);

int main(int argc, char *argv[]) {

string s;

while (true) {

cout << "> ";

getline(cin,s);

cout << "\"" << s << "\" is ";

if (isPalindrome(s) == false) cout << "not ";

cout << "a palindrome." << endl;

}

return 0;

}

bool isPalindrome(const string &str) {

Stack *s,*u,*r;

string::const_iterator i;

bool isPal = true;

s = new Stack(str.size(),' ');

u = new Stack(str.size(),' ');

r = new Stack(str.size(),' ');

//

// Push characters of str onto stacks s and u

//

for (i = str.begin(); i != str.end(); i++) {

s->push(*i);

u->push(*i);

}

//

// Pop each character from u and push it onto r

// so r contains the reverse of u (and of s).

//

do {

r->push(u->pop());

} while (u->empty() == false);

//

// Pop from s and r and compare, until s is

// empty or a mismatch is found.

//

while ((s->empty() == false) && (isPal == true)) {

isPal = (s->pop() == r->pop());

}

delete s;

delete u;

delete r;

return isPal;

}

#if 0

Sample run:

> kayak

"kayak" is a palindrome.

> I saw I was I

"I saw I was I" is a palindrome.

> abcd

"abcd" is not a palindrome.

> abba

"abba" is a palindrome.

>

#endif

And here's my Stack template class:

Stack.h

- - - - - - - - -

#ifndef _STACK_H

#define _STACK_H

#include

using namespace std;

template

class Stack {

public:

Stack(size_t size, T resetValue, size_t growIncr = 2) :

_maxSize(size), _growIncr(growIncr),

_resetValue(resetValue) {

_stackData = new T[size+1];

_top = &_stackData[size];

init(_stackData,size+1);

}

~Stack() { if (_stackData != NULL) delete [] _stackData; }

void init(T *data, size_t size) {

for (size_t i = 0; i < size; i++) {

data[i] = _resetValue;

}

}

void clear() { init(_stackData,_maxSize); }

inline bool full() { return _top == _stackData; }

inline bool empty() { return _top == &_stackData[_maxSize]; }

inline unsigned stackLen() { return &_stackData[_maxSize] - _top; }

inline unsigned getMaxSize() { return _maxSize; }

void push(T n) {

if (full() == true) grow();

*(--_top) = n;

}

T pop() {

T x = *_top;

if (empty() == false) _top++;

return x;

}

void grow() {

size_t newSize = _maxSize + _growIncr, i, j;

T *temp = new T[newSize + 1];

init(temp,newSize+1);

for (i = _growIncr, j = 0; j < _maxSize+1; i++,j++) {

temp[i] = _stackData[j];

}

_maxSize += _growIncr;

delete [] _stackData;

_stackData = temp;

_top = &_stackData[_growIncr];

}

void stackDump() {

if (empty() == false) {

size_t len = stackLen();

T *p = _top;

for (size_t i = 0; i < len; i++) {

cout << *p++ << endl;

}

}

cout << endl;

}

private:

Stack() { }

size_t _maxSize;

size_t _growIncr;

T *_top;

T *_stackData;

T _resetValue;

};

#endif