Personal computing discussed

Moderators: renee, SecretSquirrel, just brew it!

 
malebolgia
Gerbil Elite
Topic Author
Posts: 973
Joined: Fri Apr 05, 2002 7:00 pm
Location: USA

Java & Palindrome?

Thu Dec 04, 2003 8:24 pm

I'm trying to write a simple palindrome program that returns true and false. I've hit a brick wall I can't think of what do to next. I setup a for loop that will get rid of the spaces and put it into a new string (I hope). I'm not sure how to reverse the string and how to use String.equals to test for a palindrome. Any help would be appreciated.
import java.io.*;
import java.util.*;

public class palindrome
{
 public static void main(String[] args)
  {

   String tstst = "MOM";
   String temp = "";

  for(int i = 0; i < tstst.length(); i++)
   {
    if((tstst.charAt(i)>= 'A') && (tstst.charAt(i)<= 'Z'))
     {
      temp = temp + tstst.charAt(i);
     } //end if statement
   } //enf for loop

  } //end main
} //end palindrome
 
moog
Gerbil Elite
Posts: 868
Joined: Wed Jun 11, 2003 9:10 am

Thu Dec 04, 2003 9:02 pm

... I've forgotten most of my java, but looks like a lot like C

public class palindrome 
{
public static void main(String[] args) {
   String tstst = "MOM";
   System.out.println(isPalindrome(tstst));
} //end main

public static bool isPalindrome(String s) {
   int i = 0, j = s.length()-1;
   for (; i < j; i++, j--)
      if (s.charAt(i) != s.charAt(j))
         return false;
   return true;
}
} //end palindrome


I don't guarantee it'll work (I've probably buggered something), just gives you the idea of checking if it isPalindrome.
 
Canuckle
Gerbil XP
Posts: 387
Joined: Sun Jul 13, 2003 6:20 pm

Thu Dec 04, 2003 9:10 pm

I have no clue as to what your IF statement code is for - Male's not moog ;)

The first part to solving a palindrome lies in the length of the string - you need to know if it's odd or even so that you compare the correct value(s). For instance, like in "MOM", you need to know that you don't need to check the "O" because it would equal itself - you only need to check positions 0 and 2 of the string to one another to see if the provided string satisfies the palindrome criteria. Because if you were to use "ANNA", you have to know how to handle it. The modulus operator would be a good idea...

The next part to solving palindromes is that you start comparing from the midpoint out... Ideally, this is an operation for using a stack or queue - can't remember ATM which is FIFO or FILO though, curse the theory... :)
 
malebolgia
Gerbil Elite
Topic Author
Posts: 973
Joined: Fri Apr 05, 2002 7:00 pm
Location: USA

Thu Dec 04, 2003 9:20 pm

I was thinking of just reversing temp and comparing it with the original string wouldn't the work?
 
moog
Gerbil Elite
Posts: 868
Joined: Wed Jun 11, 2003 9:10 am

Thu Dec 04, 2003 9:26 pm

It would work but unnecessarily complex.

In the simple sol'n we just keep checking the head and tail chars in the string one by one. We increment the head (i) and decrement the tail (j) and compare the chars. We stop when head >= tail, in other words, we've checked all the chars we care for. This will work for even or odd sized strings (in the odd case we won't check the middle char either [when head == tail]).

Edit: We can also return false once two chars don't match.

I'm also thinking you can try your idea, it might be a good exercise.
 
Canuckle
Gerbil XP
Posts: 387
Joined: Sun Jul 13, 2003 6:20 pm

Thu Dec 04, 2003 9:44 pm

public class Palindrome
{
   public static void main(String[] args)
   {
      Palindrome pal = new Palindrome();
      System.out.println(pal.checkString("ANNA"));
   }

   public boolean checkString(String str)
   {
      str = str.trim();

      int middle = str.length() / 2 - 1;

      int counter = 1;

      boolean flag = true;

      if(str.length() % 2 != 0)
      {
         //Have to move the starting point back cuz we know that there's no point
         //in comparing a value (in this case "O") against itself.
         middle = middle - 1;
      }

      for(int i = middle; i >= 0; i--)
      {
         if(str.charAt(i) == str.charAt(i + counter))
         {
            counter+=2;
         }
         else
         {
            flag = false;
         }
      }

      if(flag)
      {
         return true;
      }
      else
      {
         return false;
      }
   }
}


I've only tested that with MOM and ANNA - so go on, break it :D
Last edited by Canuckle on Thu Dec 04, 2003 10:03 pm, edited 1 time in total.
 
malebolgia
Gerbil Elite
Topic Author
Posts: 973
Joined: Fri Apr 05, 2002 7:00 pm
Location: USA

Thu Dec 04, 2003 9:59 pm

I was thinking that this would work:
public static void palindrome(String[] args)
 {

  String tstst = "MOM";
  String temp = "";
  String temp2 = "";

  for(int i = 0; i < tstst.length(); i++)
   {
    if((tstst.charAt(i)>= 'A') && (tstst.charAt(i)<= 'Z'))
     {
      temp = temp + tstst.charAt(i);
     }
   }

  for(int j = tstst.length(); j < 0; j--)
   {
    if((tstst.charAt(j)>= 'A') && (tstst.charAt(j)<= 'Z'))
     {
      temp2 = temp2 + tstst.charAt(j);
     }
   }

 temp.equals(temp2);

 } //end palindrome


I was trying to save the string from the last element to the first then compare the two to see if they're the same. Though I can't get it to work.
 
moog
Gerbil Elite
Posts: 868
Joined: Wed Jun 11, 2003 9:10 am

Thu Dec 04, 2003 10:35 pm

  for(int j = tstst.length()-1; j >= 0; j--) 
   {
    if((tstst.charAt(j)>= 'A') && (tstst.charAt(j)<= 'Z'))
     {
      temp2 = temp2 + tstst.charAt(j);
     }
   }

Your second loop index was off. (I don't see anything else wrong...)

What if the string has numbers and lower case? If you just want to cut off whitespace at head and tail you should write a separate function for that. The returned string can be passed to the palindrome check (and you can eliminate the first copy loop).
 
malebolgia
Gerbil Elite
Topic Author
Posts: 973
Joined: Fri Apr 05, 2002 7:00 pm
Location: USA

Thu Dec 04, 2003 10:43 pm

moog wrote:
  for(int j = tstst.length()-1; j >= 0; j--) 
   {
    if((tstst.charAt(j)>= 'A') && (tstst.charAt(j)<= 'Z'))
     {
      temp2 = temp2 + tstst.charAt(j);
     }
   }

Your second loop index was off. (I don't see anything else wrong...)

What if the string has numbers and lower case? If you just want to cut off whitespace at head and tail you should write a separate function for that. The returned string can be passed to the palindrome check (and you can eliminate the first copy loop).


For right now I'm ignoring numbers and lowercase. I still can't get it to print anything/compare how do I compare two strings to see if they're equal? I thought the String.equals method would work:
 temp.equals(temp2); 


But It's not even printing anything to the screen. So I'm not sure at all if it's right or wrong.
 
JediNinjaWizards
Irritating Rash
Posts: 1616
Joined: Tue Aug 19, 2003 9:46 am
Location: Player's Republic of Pimpachusetts
Contact:

Thu Dec 04, 2003 10:44 pm

An easy way to do this, and I am too lazy to provide any code, would be to push the string onto a stack and a queue. then pop the letter off the stack and the queue respectively, and see if each matches, as soon as you get a mismatch, its not a palindrome. This works because the stack is LIFO, and will"replay" the string backwards, while a queue is FIFO, and returns the string in order. so in other words, do this:
push "abcba"
queue "abcba"
while not stackempty and while not end of queue
{
pop stack into A
dequeue into B
are A and B equal?
yes, keep going
no, youre done, it isnt a palindrome
}
 
moog
Gerbil Elite
Posts: 868
Joined: Wed Jun 11, 2003 9:10 am

Thu Dec 04, 2003 10:45 pm

equals returns a bool

if (temp.equals(temp2))
System.out.println("A palindrome.");
else
System.out.println("Not a palindrome.");

Edit: Sigh. Profs must always love teaching things the hard way...
 
Yahoolian
Grand Gerbil Poohbah
Posts: 3577
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD
Contact:

Thu Dec 04, 2003 11:09 pm

*hint* Check out String class methods by going to http://java.sun.com/ and clicking on APIs(left hand side), then your v of java. Then click on the lower left frame, do ctl-f and put in String. Likewise for the Character class.

This is the most elegant solution I could come up with.
class IsPalindrome {

   public static void main(String args[])
   {
     System.out.println( "These should be palindromes: " );
    displayResult( "A" );
    displayResult( "Mom" );
    displayResult( "Hannah." );
    displayResult( "ABCDEDCBA." );
    displayResult( "A daffodil slid off Ada." );
    displayResult( "A Dan, a clan, a canal - Canada!" );
    displayResult( "A Toyota! Race fast, safe car. A Toyota." );
    System.out.println( "\nThese should not be palindromes: " );
    displayResult( "AB" );
    displayResult( "ABC" );
    displayResult( "ABCA" );
    displayResult( "ADOIA" );
  } // end test main

  public static void displayResult( String str )
  {
    System.out.println( str + ( ( isPalindrome( str ) ) ? " is " : " is not " ) + " a palindrome." );
  } // end displayResult


  public static boolean isPalindrome( String str )
  {
    str = str.toLowerCase();
    int begin = -1, end = str.length();
    do
    {


      do
      {
        begin++;
      } while( begin < str.length() - 1 && !Character.isLetter( str.charAt( begin ) ) );

      do
      {
        end--;
      } while( end > 0 && !Character.isLetter( str.charAt( end ) ) );

      if( str.charAt( begin ) != str.charAt( end ) )
          return false;


    } while( begin < end );

    return true;


  } // end isPlaindrome
} // end class

Some palindromes courtesy of http://www.palindromes.org/ (Guess which ones :wink:
 
JediNinjaWizards
Irritating Rash
Posts: 1616
Joined: Tue Aug 19, 2003 9:46 am
Location: Player's Republic of Pimpachusetts
Contact:

Thu Dec 04, 2003 11:25 pm

Sorry for the lack of codeness, but i tried this in another language we use at work, and it worked also. If Java has the ability to start at the beginning or end of a string, and increment up or down, you could just start at opposite ends of the string, and work toward the middle, allowing for the left over character if its an odd number of course, and keep comparing the characters...as soon as they dont match its not a palindrome. this only requires one "queue" and is more efficient than the last thing i suggested. Hope it helps
 
malebolgia
Gerbil Elite
Topic Author
Posts: 973
Joined: Fri Apr 05, 2002 7:00 pm
Location: USA

Thu Dec 04, 2003 11:25 pm

Thanks I got it working now, however when I put it in my other program as a method it doesn't print anything?
public static void palindrome(String[] args)
 {

  String tstst = "ABLE WAS I ERE I SAW ELBA";
  String temp = ""; //String holds tstst without spaces
  String temp2 = ""; //String holds tstst without spaces but in reverse order

    System.out.println(tstst); //Prints out value for tstst

    for(int i = 0; i <  tstst.length(); i++) //Takes out spaces from tstst
     {
      if((tstst.charAt(i)>= 'A') && (tstst.charAt(i)<= 'Z'))
       {
        temp = temp + tstst.charAt(i); //Stores no spaced words in new string
       }
     }

    for(int j = tstst.length()-1; j >= 0; j--) //Takes out spaces from tstst and arranges them reversed
     {
      if((tstst.charAt(j)>= 'A') && (tstst.charAt(j)<= 'Z'))
       {
        temp2 = temp2 + tstst.charAt(j); //Stores no spaced words in new string (reversed)
       }
     }

    if (temp.equals(temp2)) //Compares temp & temp2 to see if their equal to each other
     System.out.println("True");
    else
     System.out.println("False");
 } //end palindrome

 
Yahoolian
Grand Gerbil Poohbah
Posts: 3577
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD
Contact:

Thu Dec 04, 2003 11:31 pm

It returns a boolean true if it is a palindrome, false if it is not.

You could change return false to System.out.println( "False." ) and return true to System.out.println( "True." ), but the easiest way would be to paste the two methods besides main into it and call the displayResult with the String you want to test.

Hmm, looks like your v can't handle punctuation....
[edit]Nevermind it can, I don't know what I was thinking...

You might have to do tstst = tstst.toUpperCase(); because your version can only handle upper case letters.
 
malebolgia
Gerbil Elite
Topic Author
Posts: 973
Joined: Fri Apr 05, 2002 7:00 pm
Location: USA

Thu Dec 04, 2003 11:51 pm

I got now, and big thanks to everyone who helped me out here tonight. 8)

Who is online

Users browsing this forum: No registered users and 19 guests
GZIP: On