Solved

checking for a palindrome

Posted on 2004-10-02
26
251 Views
Last Modified: 2012-06-21
I have my class for the stack and queue built. The queue and stack are both holding the values of the string in an array. My question is how do I write the function to check if this is a palindrome?

Here are my classes...

-------------------------------------------
#ifndef STACK_H
#define STACK_H

#include <iostream>

using namespace std;

typedef char stackElement;
const int MAX = 50;

class Stack
{
public:
      Stack();
      ~Stack();
      void push(stackElement& ch);
      void pop();
      stackElement top() const;
      bool empty()const;
      bool full()const;
private:
      stackElement arr[MAX];
      int stackTop;
      int count;
};
#endif
--------------------------------------------------
Queue class

#ifndef QUEUE_H
#define QUEUE_H

typedef char queueElement;
const int SIZE = 50;

class Queue
{
public:
      Queue();  
      void enqueue(char);
      bool full() const;
      void dequeue();
      bool empty() const;
      queueElement front() const;
private:
      queueElement arr[SIZE];
      int queueFront;
      int back;
      int count;
      int maxQSize;
};
#endif

I can push and enqueue just fine. Its just comparing them that I need help with. I have tried.

      if (s.top() != q.front())
      {
            cout << "The string is not a palindrome." << endl;      
      }
      else
      {
            cout << "The string is a palindrome." << endl;
      }      

but this always tells me it is even when it is not.
0
Comment
Question by:jandhb
  • 16
  • 10
26 Comments
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
Note: You are checking one character. You will want to check ALL of the characters you have stored in your queue against all of the characters stored in your queue.

You will need a loop that keeps track whether there was ever a mismatch. between the two structures.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
Exactly.

My question is how do I do that. I have a tried a while(!s.empty()) but that simply returns that it is for however many times the length of the string is. I have tried a for loop, which I am sure would work, but how do I write this?

I think it would be something like

for (int i = 0; i < all the elements in the stack/queue; i++){}

Help, please.
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
In other words, I have tried this with the input of "ABCBA" which is a palindrome.

      for (int i=0; i<5; ++i)
      {
            q.dequeue();
            s.pop();
      
      if (s.top() == q.front())
      {
            cout << "The string is a palindrome." << endl;      
      }
      else if (s.top() != q.front())
      {
            cout << "The string is not a palindrome." << endl;
      }      
      }

However, what it displays is...

"This is not a palindrome".... 5 times
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
(1) Check your front/top routines (print out what they are returning). You should see it IS a palindrome five times.

(2) Assuming that that works, you want to use a boolean to keep track of whether you ever saw a mismatch (the else part of your if); you don't want to print anything in the loop as you don't know anything in the loop. Instead, if you see a mismatch, set the flag. Then you can use an if (after the loop) to check if you saw a mismatch OR you didn't.

-bcl
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
Also, the loop should run until the containers are empty rather than to 5 every time.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
1) I am doing this in my push()

cout << "This is the value being pushed unto the stack." << ch << endl;

How do you suppose I do this in the top(). which now looks like this...

stackElement Stack::top() const
{
      return arr[stackTop - 1];
}

I don't understand how to write what your saying in #2. Is it possible for you to write some code here and show me?
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
I am also doing this in my enqueue()

cout << "This is the value being joined to the Queue." << item << endl;

Yes, I can tell that what is being pushed/joined are the same.

Again, How do you suppose I do this in the front() which now looks like this...

queueElement Queue::front() const
{
      return arr[queueFront];
}

I am not ever calling top/front except in my main() when I do the comparison.

Please SHOW me how this would be modified in main.

      for (int i=0; i<5; ++i)
      {
            while(!s.empty())
            {
            q.dequeue();
            s.pop();
            }
      
      if (s.top() == q.front())
      {
            cout << "The string is a palindrome." << endl;      
      }
      else
      {
            cout << "The string is not a palindrome." << endl;
      }      
      }
0
 
LVL 11

Accepted Solution

by:
bcladd earned 25 total points
Comment Utility
(1) This is homework, right? I cannot write the solution for you (membership agreement here). I can help you find the solution.

(2) How about making sure the following works:

while (!s.empty()) {
  cout << "s.top() = " << s.top() << ", "l
         << "q.front() = " << q.front() << endl;
 
  s.pop();
  q.dequeue();
}

This loop should show each of the pairs you should be comparing (I think in the first one you failed to compare the first element (in q) with the last element (in s) when you popped/dequeued before comparing values).

Then you need to keep track of what you have seen. Imagine, for a moment, that the interesting thing is whether or not the queue contained any letter "A".

bool sawAnA = false;
while (!q.empty()) {
  if (q.front() == 'A')
    sawAnA = true;
  q.dequeue();
}
if (sawAnA) {
  cout << "I saw an A" << endl;
} else {
  cout << "I saw absolutely no A's" << endl;
}

Hope this helps,
-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
This...

while (!s.empty()) {
  cout << "s.top() = " << s.top() << ",";
       cout << "q.front() = " << q.front() << endl;
 
  s.pop();
  q.dequeue();
}

puts the program into an endless loop??  
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
My empty() looks like this..

bool Stack::empty() const
{
    return (count == 0);
}
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
My top and front functions look like this...

stackElement Stack::top() const
{
      return arr[stackTop - 1];
}


queueElement Queue::front() const
{
      return arr[queueFront];
}

Are those correct?
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
How does pop change the value of count? s.pop every time should shorten the number of elements on the list.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
My pop function looks like this...

void Stack::pop()
{
      --stackTop;
}

Should it decrement count?? Is that what your saying??
0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
LVL 1

Author Comment

by:jandhb
Comment Utility
stackTop is representing the current number of values on the stack. So, to me that would mean every time pop is called take an element off the stack, right?

Here is entire Stack class. Maybe this will help.

#ifndef STACK_H
#define STACK_H

#include <iostream>

using namespace std;

typedef char stackElement;
const int MAX = 50;

class Stack
{
public:
      Stack();
      ~Stack();
      void push(stackElement& ch);
      void pop();
      stackElement top() const;
      bool empty()const;
      bool full()const;
private:
      stackElement arr[MAX];
      int stackTop;
      int count;
};
#endif
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
If stackTop is the number of values on the stack, what is count? I would guess that you want to modify empty so that you check the NUMBER OF ELEMENTS IN THE STACK is zero.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
Ahhh....I think I found something here.
When you said How does pop change the value of count? it got me thinking.

I had this...

bool Stack::empty() const
{
      return (count == 0);
}

I changed it to this...

bool Stack::empty() const
{
      return (stackTop == 0);
}

Now your while loop works.

The results look like this from this input "ABCBA". Please help me to understand.

s.top = b
q.front = a
s.top = c
q.front =
s.top = b
q.front =
s.top = a
q.front =
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
From what I can understand from this output...

1) It does not look like the top most element "A" is being popped.

2) Besides the first element in the queue nothing else is being dequeued.

Why?
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
I changed my constructor to say,

Stack::Stack()
{
      stackTop = 0;
      arr[MAX]=0;
}


and changed  top to


stackElement Stack::top() const
{
      return arr[stackTop];
}

Now the stack appears to be ok, but the queue still displays only the first element and the last element is showing up as some weird looking P. Here is my Queue functions....

------------------------------------

#include "Queue.h"
#include <iostream>

using namespace std;

Queue::Queue() : count(0), maxQSize(50), queueFront(0), back(0)
{
      arr[SIZE]=0;
}

void Queue::enqueue(char item)
{
      if (full())
      {
            cout << "The queue is full." << endl;
      }
      else
      {
            //Calculate back position
            back = (back + 1) & maxQSize;
            //Insert new item
            arr[back] = item;
            //Update item count
            ++count;
            cout << "This is the value being joined to the Queue." << item << endl;
      }
}

bool Queue::full() const
{
      return (count == maxQSize);
}

void Queue::dequeue()
{
      if (!empty())
      {
            --count;
            queueFront = (queueFront + 1) % maxQSize;
      }
}

bool Queue::empty() const
{
      return (count == 0);
}

queueElement Queue::front() const
{
      return arr[queueFront];
}
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
(1) Look at the pushing of the elements. That is, did all 5 get pushed on the stack? You might want to dump the length of the stack after each push (or inside of pop) to make sure the element count is right.

(2) Look at enqueue. I am guessing that the problem with the queue is what got put there. You can check whether the element being dequeued is the first or the last a you should try enqueuing something like "abcde" and see what you get out.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
Yeah, the queue is not quite right. I think something has to change in my enqueue()...Hmmm...

            back = (back + 1) % maxQSize;
            //Insert new item
            arr[back] = item;
            //Update item count
            ++count;
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
Your stack is broken (I am pretty sure): stackTop is the # of elements so the topmost element will be at stackTop - 1 OR stackTop is the index of the topmost element in which case empty is true when stackTop is something below 0...

In queue:
  back = (back + 1) & maxQSize;
 & is the wrong operator. I would guess you want %.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
yeah, I changed it to %, but for this input "ABCBA" it displays..

weird symbol
a
b
c
b

Why?
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
I am not  seeing what is wrong with my queue functions. Do you?

#include "Queue.h"
#include <iostream>

using namespace std;

Queue::Queue() : count(0), maxQSize(50), queueFront(0), back(0)
{
      arr[SIZE]=0;
}

void Queue::enqueue(char item)
{
      if (full())
      {
            cout << "The queue is full." << endl;
      }
      else
      {
            //Calculate back position
            back = (back + 1) % maxQSize;
            //Insert new item
            arr[back] = item;
            //Update item count
            ++count;
            cout << "This is the value being joined to the Queue." << item << endl;
      }
}

bool Queue::full() const
{
      return (count == maxQSize);
}

void Queue::dequeue()
{
      if (!empty())
      {
            --count;
            queueFront = (queueFront + 1) % maxQSize;
      }
}

bool Queue::empty() const
{
      return (count == 0);
}

queueElement Queue::front() const
{
      return arr[queueFront];
}
 
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
front starts at 0; back starts at 0; when you insert the first object you increment back and then insert a value at location....location 1. At that point front refers to uninitialized memory in position 0 so the first front() operation returns whatever garbage was there. You can see the problem if you look at the fact that the elements in the queue are one further back than they should be when you print them out. Again, I would suggest testing the queue with a NON palindrome so you can be sure all of the elements are appearing the the right places.

-bcl
0
 
LVL 1

Author Comment

by:jandhb
Comment Utility
I have inserted a non palindrome - fedba

The results are like this. Is this correct?

s.top = f
q.front = f
s.top = e
q.front = e
s.top =d
q.front = d
s.top = b
q.front = b
s.top = a
q.front = a
0
 
LVL 11

Expert Comment

by:bcladd
Comment Utility
It was my assumption that you knew what a stack and a queue were supposed to do. A stack is a LIFO data structure: last in, first out. Thus a stack should effectively reverse the sequence pushed into it. The queue is a FIFO or first-in, first out structure like the line at the grocery store. You would expect elements to reach the front in the same order they entered at the rear. Look at the output you get from the stack and the queue and see if they are FIFO and LIFO...I would not think they would be the same on a non-palindrome.

-bcl
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now