[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 300
  • Last Modified:

checking for a palindrome

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
jandhb
Asked:
jandhb
  • 16
  • 10
1 Solution
 
bcladdCommented:
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
 
jandhbAuthor Commented:
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
 
jandhbAuthor Commented:
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
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
bcladdCommented:
(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
 
bcladdCommented:
Also, the loop should run until the containers are empty rather than to 5 every time.

-bcl
0
 
jandhbAuthor Commented:
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
 
jandhbAuthor Commented:
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
 
bcladdCommented:
(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
 
jandhbAuthor Commented:
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
 
jandhbAuthor Commented:
My empty() looks like this..

bool Stack::empty() const
{
    return (count == 0);
}
0
 
jandhbAuthor Commented:
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
 
bcladdCommented:
How does pop change the value of count? s.pop every time should shorten the number of elements on the list.

-bcl
0
 
jandhbAuthor Commented:
My pop function looks like this...

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

Should it decrement count?? Is that what your saying??
0
 
jandhbAuthor Commented:
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
 
bcladdCommented:
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
 
jandhbAuthor Commented:
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
 
jandhbAuthor Commented:
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
 
jandhbAuthor Commented:
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
 
bcladdCommented:
(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
 
jandhbAuthor Commented:
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
 
bcladdCommented:
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
 
jandhbAuthor Commented:
yeah, I changed it to %, but for this input "ABCBA" it displays..

weird symbol
a
b
c
b

Why?
0
 
jandhbAuthor Commented:
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
 
bcladdCommented:
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
 
jandhbAuthor Commented:
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
 
bcladdCommented:
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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 16
  • 10
Tackle projects and never again get stuck behind a technical roadblock.
Join Now