C++

Forum

 
Comparing two strings problem

avanhoes (25)
I am trying to create a palindrome checker using a single stack and pass by reference method.The program is correctly reversing the original string, but the problem lies in the checking of the two strings. I need to remove all the punctuation and spaces(which I think I am doing) and then letter by letter compare the original string and the reverse string to determine if the string is a palindrome of not. I think this is where my issue lies. The program is not correctly comparing the strings and is giving incorrect bool responses.

The code for the stack is as follows (I pulled it straight from the book I am using to learn):

StackInterface.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
//  Created by Frank M. Carrano and Tim Henry.
//  Copyright (c) 2013 __Pearson Education__. All rights reserved.

/** @file StackInterface.h */

#ifndef _STACK_INTERFACE
#define _STACK_INTERFACE

template<class ItemType>
class StackInterface
{
public:
   /** Sees whether this stack is empty.
    @return True if the stack is empty, or false if not. */
   virtual bool isEmpty() const = 0;
   
   /** Adds a new entry to the top of this stack.
    @post If the operation was successful, newEntry is at the top of the stack.
    @param newEntry The object to be added as a new entry.
    @return True if the addition is successful or false if not. */
   virtual bool push(const ItemType& newEntry) = 0;
   
   /** Removes the top of this stack.
    @post If the operation was successful, the top of the stack
    has been removed.
    @return True if the removal is successful or false if not. */
   virtual bool pop() = 0;
   
   /** Returns the top of this stack.
    @pre The stack is not empty.
    @post The top of the stack has been returned, and
    the stack is unchanged.
    @return The top of the stack. */
   virtual ItemType peek() const = 0;
}; // end StackInterface
#endif

ArrayStack.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
//  Created by Frank M. Carrano and Tim Henry.
//  Copyright (c) 2013 __Pearson Education__. All rights reserved.

/** ADT stack: Array-based implementation.
 Listing 7-1
 @file ArrayStack.h */

#ifndef _ARRAY_STACK
#define _ARRAY_STACK

#include "StackInterface.h"

const int MAX_STACK = 50;

template<class ItemType>
class ArrayStack : public StackInterface<ItemType>
{
private:	
	ItemType items[MAX_STACK]; // Array of stack items
	int      top;              // Index to top of stack
	
public:
	 ArrayStack();             // Default constructor
	 bool isEmpty() const;
	 bool push(const ItemType& newEntry);
	 bool pop();
	 ItemType peek() const;	
}; // end ArrayStack

#include "ArrayStack.cpp"
#endif

ArrayStack.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
//  Created by Frank M. Carrano and Tim Henry.
//  Copyright (c) 2013 __Pearson Education__. All rights reserved.

/** Listing 7-1
    @file ArrayStack.cpp */
#include <cassert>       // For assert
#include "ArrayStack.h"  // Header file

template<class ItemType>
ArrayStack<ItemType>::ArrayStack() : top(-1)
{
}  // end default constructor

// Copy constructor and destructor are supplied by the compiler

template<class ItemType>
bool ArrayStack<ItemType>::isEmpty() const
{
	return top < 0;	
}  // end isEmpty

template<class ItemType>
bool ArrayStack<ItemType>::push(const ItemType& newEntry)
{
	bool result = false;	
	if (top < MAX_STACK - 1)  // Does stack have room for newEntry?
	{
		top++;
		items[top] = newEntry;
		result = true;
	}  // end if
   
	return result;
}  // end push


template<class ItemType>
bool ArrayStack<ItemType>::pop()
{
	bool result = false;
	if (!isEmpty())
	{
		top--;
		result = true;
	}  // end if
   
	return result;
}  // end pop


template<class ItemType> 
ItemType ArrayStack<ItemType>::peek() const
{
	assert(!isEmpty());  // Enforce precondition
   
	// Stack is not empty; return top
	return items[top];
}  // end peek
// End of implementation file.


Now here is the code I am writing:
Palindrome.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#include <string>
#include <cctype>
#include "ArrayStack.h"
using namespace std;
class Palindrome
{
private:
   /**
    * stores the letters in the string while it is being evaluated
    * to determine if it is a palindrome
    */
   ArrayStack<char> letters; 

   /**
    * original phrase to evaluate to determine if it is a palindrome
    */
   string phrase;

public:
   /**
    * Default constructor. Initializes expression to an empty string.
    */
   Palindrome () 
   {
      phrase = "";
   }


   /**
    * Overloaded constructor that initializes the phrase.
    * @param - newPhrase - original phrase tested to determine if it is a 
    *          palindrome
    */
   Palindrome (string newPhrase) 
   {
      phrase = newPhrase;
   }
   
   /**
    * Evaluates the phrase to determine if it is a palindrome. Uses
    * a stack to reverse the order of the letters in the phrase and
    * to determine if the original phrase is a palindrome. A palindrome
    * is a sequence of letters that reads the same forward and backward;
    * however, all spaces and punctuation are ignored.
    * @return isPalindrome - true if phrase is a palindrome; false
    *                        otherwise
    * @param reversePhrase - orginal phrase in reverse order, including
    *                        all puncutation and spaces
    */
   bool evalPalindrome (string& reversePhrase); 
};

Palindrome.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <cstdlib>
#include <iostream>
#include <string>
#include <ctype.h>
#include "Palindrome.h"

 /**
    * @file Palindrome.cpp
    * Evaluates the phrase to determine if it is a palindrome. Uses
    * a stack to reverse the order of the letters in the phrase and
    * to determine if the original phrase is a palindrome. A palindrome
    * is a sequence of letters that reads the same forward and backward;
    * however, all spaces and punctuation are ignored.
    * @return isPalindrome - true if phrase is a palindrome; false
    *                        otherwise
    * @param reversePhrase - orginal phrase in reverse order, including
    *                        all puncutation and spaces
    */
   bool Palindrome::evalPalindrome (string& reversePhrase)
   {
     char ch;
     int phraseLength = phrase.length();
     int i = 0;
     int j = 0;
     int k = 0;
     bool isPalindrome;
     int revLength = reversePhrase.length();
     string tempRev;
     string tempOrig;
     int tempPLength = tempOrig.length();
     int tempRLength = tempRev.length();

        while(i < phraseLength)
        {
          ch = phrase[i];
          letters.push(ch);
          i++;          
        }//end while
        
        while(!letters.isEmpty())
        {
          reversePhrase += letters.peek();
          letters.pop();
          j++;
        }//end while
        
        while(i < phraseLength)
        {
           if(ispunct(phrase[i]) || phrase[i] != ' ')
           {
              i++;
           }
           else
           {
              char c = phrase[i];
              tempOrig += tolower(c);
              i++;
           }
        }//end while
        
        while(i < revLength)
        {
           if(ispunct(reversePhrase[i]) || reversePhrase[i] != ' ')
           {
              i++;
           }
           else
           {
              char c = reversePhrase[i];
              tempRev += tolower(c);
              i++;
           }
        }//end while

        
        while(k <= tempPLength && k <= tempRLength)
        {
           char curLetter = tempOrig[k];
           if(curLetter == tempRev[k])
           {
              isPalindrome = true;
              k++;
           }
           else
           {
              isPalindrome = false;
              k++;
           }
        }

   }

Last edited on
avanhoes (25)
UPDATE: I edited the code Palindrome.cpp to show what I fixed. However, the comparison is still not working. I can't figure it out.
unsensible (78)
What error are you receiving? Are you getting an unresolved external error or something else?

From what I can tell initially your isPalindrome function doesn't return a value. So outside all of the loops at the bottom of the function you need to add a return isPalindrome; statement.

When testing the function, you will need to have a section of code like the following:

1
2
3
4
5
6
7
8
9
 
string test="test";
Palindrome pali;

if(pali.isPalindrome(test)){
      cout<<"String is a palindrome! "<<endl;
}
else{
      cout<<String is not a palindrome :( "<<endl;
}


otherwise, you function won't return anything so you won't see anything on the screen.

Last edited on
avanhoes (25)
Thank you. Didn't notice that. However, now it will only output the correct bool if the input is in all upper or all lower. I'm not sure what is wrong with that portion.
unsensible (78)
An easy way around that is to take whatever the user inputted and change the string to all lowercase or all uppercase before passing it through your palindrome function.

An easy way to do that would be with the following code:

1
2
3
4
 
#include <algorithm>

string test="test";
transform(str.begin(), str.end(),str.begin(), toupper);


test should then be "TEST" and you can pass it into your palindrome function.
avanhoes (25)
I can't use transform to change it I have to use a loop. I need to remove the spaces and punctuation first, then convert tolower.

Here's my updated code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#include <cstdlib>
#include <iostream>
#include <string>
#include <ctype.h>
#include "Palindrome.h"

 /**
    * @file Palindrome.cpp
    * Evaluates the phrase to determine if it is a palindrome. Uses
    * a stack to reverse the order of the letters in the phrase and
    * to determine if the original phrase is a palindrome. A palindrome
    * is a sequence of letters that reads the same forward and backward;
    * however, all spaces and punctuation are ignored.
    * @return isPalindrome - true if phrase is a palindrome; false
    *                        otherwise
    * @param reversePhrase - orginal phrase in reverse order, including
    *                        all puncutation and spaces
    */
   bool Palindrome::evalPalindrome (string& reversePhrase)
   {
     char ch;
     int phraseLength = phrase.length();
     int i = 0;
     int j = 0;
     int k = 0;
     bool isPalindrome;
     int revLength = reversePhrase.length();
     string tempRev;
     string tempOrig;
     int tempPLength = tempOrig.length();
     int tempRLength = tempRev.length();

        while(i < phraseLength)
        {
          ch = phrase[i];
          letters.push(ch);
          i++;          
        }//end while
        
        while(!letters.isEmpty())
        {
          reversePhrase += letters.peek();
          letters.pop();
          j++;
        }//end while
        
        for(i; i < phraseLength; i++)
        {
           if(ispunct(phrase[i]) || phrase[i] == ' ')
           {
              phrase.erase(i, 1);
              phraseLength = phrase.length();
           }
           
           phrase[i]= tolower(phrase[i]);
        }//end while
        
        for(i; i < revLength; i++)
        {
           if(ispunct(reversePhrase[i]) || reversePhrase[i] == ' ')
           {
              phrase.erase(i, 1);
           }
           reversePhrase[i]= tolower(reversePhrase[i]);
        }//end while
        
        cout << "reverse" << reversePhrase << endl;

        
        while(k <= phraseLength && k <= revLength)
        {
           char curLetter = phrase[k];
           if(curLetter == reversePhrase[k])
           {
              isPalindrome = true;
              k++;
           }
           else if(curLetter != tempRev[k])
           {
              isPalindrome = false;
              k++;
           }
        }
        
        return isPalindrome;

   }
unsensible (78)
ok so before this while loop:

1
2
3
4
5
6
 
while(i < phraseLength)
        {
          ch = phrase[i];
          letters.push(ch);
          i++;          
        }//end while


you need to remove white space from your string. You can do this with the following

reversePhrase.erase (remove_if (reversePhrase.begin(), reversePhrase.end(), isspace), reversePhrase.end());

Be sure to #include <algorithm>

Or can you not use any algorithms at all?
Last edited on
Topic archived. No new replies allowed.