Using Stack and Queue to check a text file for Palindromes

[Mike1986]

A palindrome is a phrase that reads the same forwards as it does backwards. For example, “a man, a plan, a canal, Panama,” is a palindrome. Write a program that uses a stack data structure to check for palindromes in each line of a text file. Test your program on the following example text file,

A man, a plan, a canal, Panama.
This line is not a palindrome
Don't nod
The next one might be my favorite
Taco Cat!
Another non-palindrome
Rats live on no evil star.
If your program finds this line, it's not working
Neil, a trap! Sid is part alien!
Step on no pets.
Dammit, I'm mad!
Madam, I'm Adam.
Madam, in Eden, I'm Adam.
Rise to vote, sir.
Never odd or even
If I had a hi-fi
Yo, banana boy!
Do geese see God?
No devil lived on.
Ah, Satan sees Natasha.
Lewd did I live & evil I did dwel!
A dog, a panic in a pagoda
Was it a cat I saw?
Was it a car or a cat I saw?
A Toyota's a Toyota.
Another non-palindrome
No lemons, no melon
Now I see bees, I won.
Ma is as selfless as I am.
Nurse, I spy gypsies—run!
The next one isn't as cool as the Panama one
A dog, a plan, a canal, pagoda
Was it Eliot's toilet I saw?
Some of these are hilarious. Papaya war?!
No, sir, away! A papaya war is on!
Go hang a salami, I'm a lasagna hog.
I, madam, I made radio! So I dared! Am I mad? Am I?
Swap God for a janitor, rot in a jar of dog paws.
Eva, can I see bees in a cave?
Not a palindrome
So many dynamos!
Red rum, sir, is murder.

This is my code that I did, but for all of the lines I get "is not a Palindrome."
So I need help with this if anyone can tell me what is the error in the program that only gives is not a Palindrome message!

[Mike1986]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.Scanner;
import java.io.*;

public class Palindrome 
{

public static void main(String[] args) throws IOException
{
BufferedReader in=new BufferedReader(new FileReader("Palindrome.txt"));

PrintStream out=new PrintStream(new File("palsout.txt"));

boolean palin;
String input,reveresed;
input=in.readLine();
while(input!=null)
{
if (isPalindrome(input))
   out.println(input+" is a Palindrome");
else
    out.println(input+" is not a Palindrome");
input=in.readLine();

}}

   /**
   * The return value is true if and only if the input string is a palindrome.
   * All non-letters is ignored, and the case of the letters is also ignored.
   **/
   public static boolean isPalindrome(String input) 
   {   
      Queue<Character> q = new LinkedList<Character>( );
      Stack<Character> s = new Stack<Character>( );
      Character letter;   // One character from the input string
      int mismatches = 0; // Number of spots that mismatched
      int i;              // Index for the input string

      for (i = 0; i < input.length( ); i++)
      {
     letter = input.charAt(i);
         if (Character.isLetter(letter))
         {
            q.add(letter);
            s.push(letter);
         }
      }

      while (!q.isEmpty( ))
      {
         if (q.remove( ) != s.pop( ))
            mismatches++;
      }

      // If there were no mismatches, then the string was a palindrome.
      return (mismatches == 0); 
   }

}

Sorry I forgot to type my code to the screen.

[~s.o.s~]

Instead of directly pointing out the answer, I would like to help you understand the technique for tackling these sort of issues (which are very common when programming anything). So basically you have a problem statement and the code written to solve it. But, like code written by most programmers, it isn't working as expected on the first try.

I believe the very first step in such a situation should be to reproduce the issue with the smallest possible data set. You are currently printing out the result for an entire file which might look daunting to debug. An approachable first step would be to try out the code for something which you know for sure is a palindrome and then call the function only for that input.

Let's pick up "A man, a plan, a canal, Panama.". What happens if you invoke the method for this input? Let's say it prints "not a palindrome". This output is not very helpful for us since it doesn't tell us exactly why it is not a palindrome. Wouldn't it be nice to find out "which" letters are triggering the not palindrome result? Two way of achieving this:

1. Debug the program in an IDE like Eclipse
2. Add in print statements inside the loop to find out the letters which cause this logic bug

Can you try the above and post your findings?

[Mike1986]

Thank you for responding, but I get no error message when debugging the program. And for print statements, I don't know what you mean by the letters which cause this logic bug. So can you explain this more? Thanks.

[~s.o.s~]

You won't get error messages when debugging logical bugs, which is what we have in this case i.e. the code works, but doesn't do what is expected from it. With respect to print statements, I meant something like:

while (!q.isEmpty()) {
    char ch1 = q.remove();
    char ch2 = s.pop();
    if (ch1 != ch2) {
        mismatches++;
        System.out.printf("Mismatch found for ch1=%s and ch2=%s%n", ch1, ch2);
    }
}

[Mike1986]

So where in the program does this loop statement go?

[~s.o.s~]

I have just re-written the code:

  while (!q.isEmpty( ))
  {
     if (q.remove( ) != s.pop( ))
        mismatches++;
  }

from your original post, so you just need to replace the above with what I wrote above.

[Mike1986]

Ok I got the following result after compiling the program:
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=p and ch2=P
Mismatch found for ch1=P and ch2=p
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=T and ch2=e
Mismatch found for ch1=h and ch2=m
Mismatch found for ch1=i and ch2=o
Mismatch found for ch1=s and ch2=r
Mismatch found for ch1=l and ch2=d
Mismatch found for ch1=i and ch2=n
Mismatch found for ch1=n and ch2=i
Mismatch found for ch1=e and ch2=l
Mismatch found for ch1=i and ch2=a
Mismatch found for ch1=s and ch2=p
Mismatch found for ch1=n and ch2=a
Mismatch found for ch1=o and ch2=t
Mismatch found for ch1=t and ch2=o
Mismatch found for ch1=a and ch2=n
Mismatch found for ch1=p and ch2=s
Mismatch found for ch1=a and ch2=i
Mismatch found for ch1=l and ch2=e
Mismatch found for ch1=i and ch2=n
Mismatch found for ch1=n and ch2=i
Mismatch found for ch1=d and ch2=l
Mismatch found for ch1=r and ch2=s
Mismatch found for ch1=o and ch2=i
Mismatch found for ch1=m and ch2=h
Mismatch found for ch1=e and ch2=T
Mismatch found for ch1=D and ch2=d
Mismatch found for ch1=d and ch2=D
Mismatch found for ch1=T and ch2=e
Mismatch found for ch1=h and ch2=t
Mismatch found for ch1=e and ch2=i
Mismatch found for ch1=n and ch2=r
Mismatch found for ch1=e and ch2=o
Mismatch found for ch1=x and ch2=v
Mismatch found for ch1=t and ch2=a
Mismatch found for ch1=o and ch2=f
Mismatch found for ch1=n and ch2=y
Mismatch found for ch1=e and ch2=m
Mismatch found for ch1=m and ch2=e
Mismatch found for ch1=i and ch2=b
Mismatch found for ch1=g and ch2=t
Mismatch found for ch1=t and ch2=g
Mismatch found for ch1=b and ch2=i
Mismatch found for ch1=e and ch2=m
Mismatch found for ch1=m and ch2=e
Mismatch found for ch1=y and ch2=n
Mismatch found for ch1=f and ch2=o
Mismatch found for ch1=a and ch2=t
Mismatch found for ch1=v and ch2=x
Mismatch found for ch1=o and ch2=e
Mismatch found for ch1=r and ch2=n
Mismatch found for ch1=i and ch2=e
Mismatch found for ch1=t and ch2=h
Mismatch found for ch1=e and ch2=T
Mismatch found for ch1=T and ch2=t
Mismatch found for ch1=c and ch2=C
Mismatch found for ch1=C and ch2=c
Mismatch found for ch1=t and ch2=T
Mismatch found for ch1=A and ch2=e
Mismatch found for ch1=n and ch2=m
Mismatch found for ch1=t and ch2=r
Mismatch found for ch1=h and ch2=d
Mismatch found for ch1=e and ch2=n
Mismatch found for ch1=r and ch2=i
Mismatch found for ch1=n and ch2=l
Mismatch found for ch1=o and ch2=a
Mismatch found for ch1=n and ch2=p
Mismatch found for ch1=p and ch2=n
Mismatch found for ch1=a and ch2=o
Mismatch found for ch1=l and ch2=n
Mismatch found for ch1=i and ch2=r
Mismatch found for ch1=n and ch2=e
Mismatch found for ch1=d and ch2=h
Mismatch found for ch1=r and ch2=t
Mismatch found for ch1=m and ch2=n
Mismatch found for ch1=e and ch2=A
Mismatch found for ch1=R and ch2=r
Mismatch found for ch1=r and ch2=R
Mismatch found for ch1=I and ch2=g
Mismatch found for ch1=f and ch2=n
Mismatch found for ch1=y and ch2=i
Mismatch found for ch1=o and ch2=k
Mismatch found for ch1=u and ch2=r
Mismatch found for ch1=r and ch2=o
Mismatch found for ch1=p and ch2=w
Mismatch found for ch1=r and ch2=t
Mismatch found for ch1=g and ch2=n
Mismatch found for ch1=r and ch2=s
Mismatch found for ch1=a and ch2=t
Mismatch found for ch1=m and ch2=i
Mismatch found for ch1=f and ch2=e
Mismatch found for ch1=i and ch2=n
Mismatch found for ch1=n and ch2=i
Mismatch found for ch1=d and ch2=l
Mismatch found for ch1=t and ch2=i
Mismatch found for ch1=i and ch2=t
Mismatch found for ch1=l and ch2=d
Mismatch found for ch1=i and ch2=n
Mismatch found for ch1=n and ch2=i
Mismatch found for ch1=e and ch2=f
Mismatch found for ch1=i and ch2=m
Mismatch found for ch1=t and ch2=a
Mismatch found for ch1=s and ch2=r
Mismatch found for ch1=n and ch2=g
Mismatch found for ch1=t and ch2=r
Mismatch found for ch1=w and ch2=p
Mismatch found for ch1=o and ch2=r
Mismatch found for ch1=r and ch2=u
Mismatch found for ch1=k and ch2=o
Mismatch found for ch1=i and ch2=y
Mismatch found for ch1=n and ch2=f
Mismatch found for ch1=g and ch2=I
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=S and ch2=s
Mismatch found for ch1=s and ch2=S
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=S and ch2=s
Mismatch found for ch1=s and ch2=S
Mismatch found for ch1=D and ch2=d
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=d and ch2=D
Mismatch found for ch1=M and ch2=m
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=m and ch2=M
Mismatch found for ch1=M and ch2=m
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=E and ch2=e
Mismatch found for ch1=e and ch2=E
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=m and ch2=M
Mismatch found for ch1=R and ch2=r
Mismatch found for ch1=r and ch2=R
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=Y and ch2=y
Mismatch found for ch1=y and ch2=Y
Mismatch found for ch1=D and ch2=d
Mismatch found for ch1=g and ch2=G
Mismatch found for ch1=G and ch2=g
Mismatch found for ch1=d and ch2=D
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=S and ch2=s
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=s and ch2=S
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=L and ch2=l
Mismatch found for ch1=l and ch2=L
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=W and ch2=w
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=w and ch2=W
Mismatch found for ch1=W and ch2=w
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=w and ch2=W
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=T and ch2=t
Mismatch found for ch1=t and ch2=T
Mismatch found for ch1=T and ch2=t
Mismatch found for ch1=t and ch2=T
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=A and ch2=e
Mismatch found for ch1=n and ch2=m
Mismatch found for ch1=t and ch2=r
Mismatch found for ch1=h and ch2=d
Mismatch found for ch1=e and ch2=n
Mismatch found for ch1=r and ch2=i
Mismatch found for ch1=n and ch2=l
Mismatch found for ch1=o and ch2=a
Mismatch found for ch1=n and ch2=p
Mismatch found for ch1=p and ch2=n
Mismatch found for ch1=a and ch2=o
Mismatch found for ch1=l and ch2=n
Mismatch found for ch1=i and ch2=r
Mismatch found for ch1=n and ch2=e
Mismatch found for ch1=d and ch2=h
Mismatch found for ch1=r and ch2=t
Mismatch found for ch1=m and ch2=n
Mismatch found for ch1=e and ch2=A
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=M and ch2=m
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=m and ch2=M
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=T and ch2=e
Mismatch found for ch1=h and ch2=n
Mismatch found for ch1=e and ch2=o
Mismatch found for ch1=n and ch2=a
Mismatch found for ch1=e and ch2=m
Mismatch found for ch1=x and ch2=a
Mismatch found for ch1=t and ch2=n
Mismatch found for ch1=o and ch2=a
Mismatch found for ch1=n and ch2=P
Mismatch found for ch1=i and ch2=h
Mismatch found for ch1=s and ch2=t
Mismatch found for ch1=n and ch2=s
Mismatch found for ch1=t and ch2=a
Mismatch found for ch1=a and ch2=l
Mismatch found for ch1=s and ch2=o
Mismatch found for ch1=c and ch2=o
Mismatch found for ch1=o and ch2=c
Mismatch found for ch1=o and ch2=s
Mismatch found for ch1=l and ch2=a
Mismatch found for ch1=a and ch2=t
Mismatch found for ch1=s and ch2=n
Mismatch found for ch1=t and ch2=s
Mismatch found for ch1=h and ch2=i
Mismatch found for ch1=P and ch2=n
Mismatch found for ch1=a and ch2=o
Mismatch found for ch1=n and ch2=t
Mismatch found for ch1=a and ch2=x
Mismatch found for ch1=m and ch2=e
Mismatch found for ch1=a and ch2=n
Mismatch found for ch1=o and ch2=e
Mismatch found for ch1=n and ch2=h
Mismatch found for ch1=e and ch2=T
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=W and ch2=w
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=E and ch2=e
Mismatch found for ch1=e and ch2=E
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=w and ch2=W
Mismatch found for ch1=S and ch2=r
Mismatch found for ch1=o and ch2=a
Mismatch found for ch1=m and ch2=w
Mismatch found for ch1=e and ch2=a
Mismatch found for ch1=o and ch2=y
Mismatch found for ch1=f and ch2=a
Mismatch found for ch1=t and ch2=p
Mismatch found for ch1=h and ch2=a
Mismatch found for ch1=e and ch2=P
Mismatch found for ch1=e and ch2=u
Mismatch found for ch1=a and ch2=o
Mismatch found for ch1=r and ch2=i
Mismatch found for ch1=e and ch2=r
Mismatch found for ch1=h and ch2=a
Mismatch found for ch1=i and ch2=l
Mismatch found for ch1=l and ch2=i
Mismatch found for ch1=a and ch2=h
Mismatch found for ch1=r and ch2=e
Mismatch found for ch1=i and ch2=r
Mismatch found for ch1=o and ch2=a
Mismatch found for ch1=u and ch2=e
Mismatch found for ch1=P and ch2=e
Mismatch found for ch1=a and ch2=h
Mismatch found for ch1=p and ch2=t
Mismatch found for ch1=a and ch2=f
Mismatch found for ch1=y and ch2=o
Mismatch found for ch1=a and ch2=e
Mismatch found for ch1=w and ch2=m
Mismatch found for ch1=a and ch2=o
Mismatch found for ch1=r and ch2=S
Mismatch found for ch1=N and ch2=n
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=n and ch2=N
Mismatch found for ch1=G and ch2=g
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=g and ch2=G
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=a and ch2=A
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=A and ch2=a
Mismatch found for ch1=S and ch2=s
Mismatch found for ch1=G and ch2=g
Mismatch found for ch1=g and ch2=G
Mismatch found for ch1=s and ch2=S
Mismatch found for ch1=E and ch2=e
Mismatch found for ch1=I and ch2=i
Mismatch found for ch1=i and ch2=I
Mismatch found for ch1=e and ch2=E
Mismatch found for ch1=N and ch2=e
Mismatch found for ch1=o and ch2=m
Mismatch found for ch1=t and ch2=o
Mismatch found for ch1=a and ch2=r
Mismatch found for ch1=p and ch2=d
Mismatch found for ch1=a and ch2=n
Mismatch found for ch1=l and ch2=i
Mismatch found for ch1=i and ch2=l
Mismatch found for ch1=n and ch2=a
Mismatch found for ch1=d and ch2=p
Mismatch found for ch1=r and ch2=a
Mismatch found for ch1=o and ch2=t
Mismatch found for ch1=m and ch2=o
Mismatch found for ch1=e and ch2=N
Mismatch found for ch1=S and ch2=s
Mismatch found for ch1=s and ch2=S
Mismatch found for ch1=R and ch2=r
Mismatch found for ch1=r and ch2=R

What does this mean if I came up with no error?

[~s.o.s~]

This means that the current method coded to find out palindromes doesn't properly implement the palindrome logic. Look at the very first print output line:

Mismatch found for ch1=A and ch2=a

Is this expected? Since A will never be equal to a (due to upper/lower case differences), what do you think should change in logic to accomodate this?

[Mike1986]

I think I have to change the character comparisons to case sensitive. But there are other characters for example line 5 it says ch1=T and ch2=e and line 6 is ch1=h and ch2=m. Is there a way to change it to case sensitive and change other characters to the same thing? I'm really confused on this so do you know what to change in logical perspective? Please tell me if I have to change the coding any how thanks.

[~s.o.s~]

I think I have to change the character comparisons to case sensitive

Yup, nice catch! Your character comparisons need to be case insensitive. So for the purpose of palindrome, A should be considered equal to a. One way of doing this is to convert the entire string to lowercase before applying the palindrome logic (input.toLowerCase()).

But there are other characters for example line 5 it says ch1=T and ch2=e and line 6 is ch1=h and ch2=m

I'm not sure what was the input you used for generating that output so can't comment. Can you just pick up a simple palindrome like "Don't nod" and post the output if you still have issues?

[Mike1986]

OK so where should I place the (input.toLowerCase()) method?

[~s.o.s~]

You need to do it before you start iterating over the string and adding the individual characters to queue/stack...

[Mike1986]

OK, I really don't know where in the program should the (input.toLowerCase()) method be written in order to run the program the right way. I tried to place it where you told me, but I get error message: Palindrome.java:41: error: not a statement. Please tell me if you can, thank you.

[stultuske]

It would be easier to see what you did wrong, if you showed us how you did it.

the input variable is supposedly the variable containing the text you want to check, so, best place to do it: at the beginning of the method:

public static boolean isPalindrome(String input) 
   {  

becomes:

public static boolean isPalindrome(String input) 
   {  
   input = input.toLowerCase();

since all the comparisons are being done later in this method.

[nagasai_1]

can any one write this topic in python3 language please

[JamesCherrill]

Lots of people can. If you can't it's because you haven't bothered to try.
Try to do it. If you get stuck post your code here with an explanation of why you're stuck, and someone will help.

[nagasai_1]

def reverse(s):
return s[::-1]

def isPalindrome(s):
rev = reverse(s)

if (s == rev): 
    return True
return False

s = str(input())
ans = isPalindrome(s)

if ans == 1:
print(s)
else:
print("Not Palindrome")

[nagasai_1]

i have done this above code. But not getting the idea to read the spaces
if i enter the input as "taco cat" it is showing not palindrome

[JamesCherrill]

You need to remove all the spaces (and maybe other punctuation or non-alphabetic characters) from the input before testing for being a palindrome.