Palindrome Program

[mrgreen]

hello,

I'm fairly new to programming in general, and i'm having some trouble figuring out how to use a stack and queue to check to see if a word or certain order of numbers/letters form a palindrome or not.

My logic is to read in the original string, push/pop characters into the stack/queue, and then compare the original string with the reversed string, but I am having trouble understanding where to loop I think.

a sample input/output would be:

Infile: mom

outFile: mom is a palindrome

Here is my code thus far:

#include "stack.h"
#include "queue.h"

int main()
{
   ifstream inFile;
   ofstream outFile;
   Queue q;
   StackType s;
   string oWord;
   string revWord = "";
   int i = 0;
   int z = 0;

   inFile.open("in.data");
   outFile.open("out.data");

   if (inFile.fail() || outFile.fail()){
     cout << "File error, check input or output files." << endl;
     return 1;
   }

    inFile >> oWord;
    outFile << oWord;

    while ((!q.IsFull) && (!s.IsFull)){
      q.Enqueue(oWord[i]);
      s.Push(oWord[i]);
      i++;
    }

    while ((!q.IsEmpty()) && (!s.IsEmpty())){
      s.Pop(oWord[z]);
      q.Dequeue(oWord[z]);
      revWord = oWord[i];
      i--;
    }

    if (revWord == oWord)
      outFile << " is a palindrome" << endl;
    else
       outFile << " is not a palindrome" << endl;


    return 0;

}

I know there's a lot of things wrong, I just am stumped on how to figure out this logic.

Thanks for your time and help.

[Red Goose]

Why use a queue at all? The queue is only gonna return the same thing as your string in the first place.

Remember the nature of a stack. A stack is somewhat unfair and believes that the last person to come should be the first to go. Think of a "stack" of objects. You always place both on top of the stack, and take off the top of the stack. Because its "last come, first serve", all you need to do is fill a stack and compare that to your original string.

[mrgreen]

so are you saying that the original string is each of the characters pushed, and the characters popped out of the stack is the reverse string?

If so, how do I pop the characters into a string?

maybe like

revString = Pop(oWord)
i--
?

and queue is part of the assignment, so i have to use it.

But i agree i dont understand why we have to use both

[Red Goose]

so are you saying that the original string is each of the characters pushed, and the characters popped out of the stack is the reverse string?

If so, how do I pop the characters into a string?

maybe like

revString = Pop(oWord)
i--
?

and queue is part of the assignment, so i have to use it.

But i agree i dont understand why we have to use both

"Pop" is an STL function that deletes a value in an STL container. You don't need to "pop" anything in your string. You don't need "revString" at all is my point. If you're using both containers and (I assume) your containers hold char variables, you just need to compare both your queue and your stack to ensure that they're equal.

if (stack.top() != queue.front())
  isEqual = false;

Do this until one of them is empty (doesn't matter which, they should be the same size). If "isEqual" is false by the end, then, clearly, the word is not a palindrome. A simple if statement is all that's needed at that point. Assuming you're populating your containers properly, there shouldn't be much else to it.

The point of this exercise seems (to me) to teach you the difference between stack and queue. Remember, stack is "last come, first serve" and queue is "first come, first serve", meaning, when you access a variable in a stack, you're accessing the newest variables to come into the stack, while in a queue, you're accessing the oldest variable to go into the queue.

If you're still having trouble with it, compile and run this, and see exactly what it's doing (look at both the output, and the source code):

#include <iostream>
#include <stack>
#include <queue>

using std::cout;
using std::cin;
using std::queue;
using std::stack;

int main()
{
 // Non-relevant set-up.
 char input[5];
 cout << "Input Number: ";
 for (int i = 0; i != 5; i++)
 {
  while (true)
  {
   cin >> input[i];
   if ((int(input[i])) > int('9')||(int(input[i]) < int('0')))
   {

    cout << "\nInvalid Entry\n";
    cout << "Input Number: ";
   }
   else
    break;
  }
  cout << "Input Number: ";
 }
  int output[5];
  for (int i = 0; i != 5; i++)
   output[i] = int(input[i]) - int('0');
 // This is the relevant part
 queue<int> queueOutput;
 stack<int> stackOutput;
 for (int i = 0; i != 5; i++)
 {
  queueOutput.push(output[i]); //Notice that the procedure to add to both containers
  stackOutput.push(output[i]); //is the same.
 }
 cout << "\nStack = ";
 while (!stackOutput.empty())
 {
  cout << stackOutput.top() << " "; //You can only access one variable in each
  stackOutput.pop();                //Container, thus, indexes are not necessary.
 }
 cout << "\nQueue = ";
 while (!queueOutput.empty()) //Same thing as above
 {
  cout << queueOutput.front() << " "; //Though the wording is different, this does the
  queueOutput.pop();                  //same thing, accesses the only available
 }                                    //variable
 cout << "\n";
 return 0;
}

[mrgreen]

So i should read in character by character instead of the whole string?

Also, we were taught that push/pop is only associated with stack and enqueue/dequeue is associated with queue, so it is a little confusing to me.

So this is my thought process: When you push from a stack, the string "ABCD" will be in order in that stack. When you pop, that string will be "DCBA." Is this correct?

[Red Goose]

So i should read in character by character instead of the whole string?

Of course, If you read the whole string, it will equal the same no matter what kind of container you use.

Also, we were taught that push/pop is only associated with stack and enqueue/dequeue is associated with queue, so it is a little confusing to me.

push and pop particularly are, however, other STL containers use similar wording like "push_back" or "pop_back".

So this is my thought process: When you push from a stack, the string "ABCD" will be in order in that stack. When you pop, that string will be "DCBA." Is this correct?

Remember, when you're "poping", you're just deleting the variable in front, so you can access the next one in the stack. The command "stack.top()" is what actually accesses the variable.

Other than that, you're right, because a stack displays the newest variable first and the oldest last, and if you enter "ABCD" D is the newest, while A is the oldest.

[mrgreen]

alright thanks a lot for your help. My only other question is top() a built-in function or is it a function that you have to declare/create yourself?

[Red Goose]

alright thanks a lot for your help. My only other question is top() a built-in function or is it a function that you have to declare/create yourself?

top() is a member function of the stack class. You don't need to create your own.

Oh, also, remember you want to declare your stack and queue with

#include <stack>

.

Declaring it with double quotes makes the compiler look in the same folder as your program. You want to use the STL header.

[biljith]

is this necessary cant v use arrays and for loop sorry if i m rong i m new to c++