Is there better way to check for palindrome string by inserting half of stack

[raghu kalachar]

Hi,

Below is my code. Is there better way to check for palindrome of string by inserting half of stack and also considering odd and even length ?

public class PalindromeString_Stack {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the expression");
		String exp=sc.next();
		System.out.println(isStringPalindrome(exp));

	}

	private static boolean isStringPalindrome(String exp) {
		boolean result = false;
		int length=exp.length();
		Stack<Character> s=new Stack<Character>();
		char[] pal_String=exp.toCharArray();
		int i;
		for(i=0;i<=(length-1)/2;i++){
			s.push(pal_String[i]);
		}
		
		if(length%2!=0)
			s.pop();
		
		while(!s.isEmpty()){
					if(pal_String[i]==s.pop())
						i++;
				else
					return result;
		}
		return result=true;
	}

}

[Carey Brown]

A stack is overkill and so is making a char[]. You should simply use a for() loop with an index and do comparison using charAt(index) vs charAt(length-index-1).

[Piet Souris]

Thinking of several ways is both good exercise and often more interesting than a simple for loop. But first of all, clean the string from unwanted characters, like spaces, comma's Et cetera.

Another way (also overkill) is to make a frequency table of the characters. Now, at most one character can have an odd frequency. But that is only a necessary condition, not a sufficient one. So, look at the Collection class, there may be some useful methods available (for instance rotate, but there are some more).

[Carey Brown]

This -->

Piet Souris wrote:But first of all, clean the string from unwanted characters, like spaces, comma's Et cetera.

[raghu kalachar]

Carey,
Yes I understand stack is overkill but just wanted to try out is their any much more efficient method.

[Stephan van Hulst]

Like Carey said, the most efficient method is using a simple loop that iterates through the characters of the string from both ends.

Even though it's not the most efficient, I would prefer the clearest solution:

return new StringBuilder(string).reverse().toString().equals(string);

If the solution must be stack-based, I'd use the call stack:

static boolean isPalindrome(String string) {
  if (string.length() <= 1)
    return true;

  return isPalindrome(new StringBuilder(string));
}

private static boolean isPalindrome(StringBuilder chars) {
  int length = chars.length();

  if (length <= 1)
    return true;

  char first = chars.charAt(0);
  char last  = chars.charAt(length - 1);

  if (first != last)
    return false;

  chars.deleteCharAt(length - 1);
  chars.deleteCharAt(0);

  return isPalindrome(chars);
}

Note that my second example only works for characters that fall within the Basic Multilingual Plane. My first example does work for all other Unicode characters, but does not take combining characters into account. For instance, it may or may not return true for the string "hèh".

[Robert D. Smith]

Why not something as simple as reversing a copy of the string, and then check if they are equal?  Seems much simpler than running through a loop, counting characters, and such.

Just a thought,

Regards,
Robert

[Junilu Lacar]

Robert D. Smith wrote:Why not something as simple as reversing a copy of the string, and then check if they are equal?  Seems much simpler than running through a loop, counting characters, and such.

This:

Stephan van Hulst wrote:... I would prefer the clearest solution:

return new StringBuilder(string).reverse().toString().equals(string);

To make it even clearer:

boolean isPalindrome(String s) {
    return s.equals(reverseOf(s));
}

String reverseOf(String s) {
    return new StringBuilder(s).reverse().toString();
}

To the point about removing spaces and punctuation, that would be correct if you're checking for imperfect palindromes. The examples given that don't remove spaces and such check for perfect palindromes.

[Campbell Ritchie]

return result=true;That is really confusing code. If you want to do that sort of thing, simply write return true; In that case you can probably get rid of your boolean local variable.

[Campbell Ritchie]

Robert D. Smith wrote:. . . reversing a copy of the string . . .

How would you suggest one should reverse a String?

[Junilu Lacar]

raghu kalachar wrote:
Below is my code.

...
	private static boolean isStringPalindrome(String exp) {
		boolean result = false;
		int length=exp.length();
		Stack<Character> s=new Stack<Character>();
		char[] pal_String=exp.toCharArray();
		int i;
		for(i=0;i<=(length-1)/2;i++){
			s.push(pal_String[i]);
		}
		
		if(length%2!=0)
			s.pop();
		
		while(!s.isEmpty()){
					if(pal_String[i]==s.pop())
						i++;
				else
					return result;
		}
		return result=true;
	}

Compare your code with this cleaned up version:

import java.util.ArrayDeque;
...
  private static boolean isPalindrome(String s) {
    
    ArrayDeque<Character> stack = new ArrayDeque<>();
    char[] cs = s.toCharArray();
    
    int half = cs.length / 2;
    for (int i = 0; i < half; i++) {
      stack.push(cs[i]);
    }

    if (cs.length % 2 != 0) {
      half++;
    }
    
    while (!stack.isEmpty()) {
      if (stack.pop() != cs[half++]) {
        return false;
      }
    }
    
    return true;
  }

Alternatively,
  ...   while (!stack.isEmpty() && stack.pop() == cs[half++]) {        ;   }   return stack.isEmpty(); }
This version may seem a little more clever but it is also less clear, in my opinion. It still works the same though.

Try it out here: https://repl.it/@jlacar/StackBasedPalindromeCheck

[Stephan van Hulst]

I know I've mentioned this before, but a friendly reminder that that code will only work for characters that fall within the Basic Multilingual Plane. In practice this probably isn't much of a problem, as long as you're not trying to determine whether a string containing unified Han characters or Egyptian hieroglyphs is a palindrome.

For strings containing ligatures or accents, you might have to convert them to either of two normalized Unicode forms, depending on whether you want to consider the reverse of "æ!æ" either "æ!æ" or "ea!ea".

This is not always obvious. For instance, while people usually consider the ligature 'æ' one character, they also usually consider the ligature 'fi' a combination of the 'f' and 'i' characters.

[Junilu Lacar]

Stephan van Hulst wrote:I know I've mentioned this before, but a friendly reminder that that code will only work for characters that fall within the Basic Multilingual Plane. In practice this probably isn't much of a problem...

Good reminder but as you said, probably isn't much of a problem. Haven't run into a situation in real life where I actually need to check for palindromes. Really more an academic exercise in algorithms.

[Campbell Ritchie]

Junilu Lacar wrote:. . . Haven't run into a situation in real life where I actually need to check for palindromes. . . .

They occur about every other week in the crossword puzzle. Spoonerisms are slightly less frequent. When I see phrases like, “both ways,”  or, “up and down,” I can suspect the solution will be palindromic. Of course I only use the letters A...Z.

[Junilu Lacar]

I meant in a real life programming situation. I don't do crossword puzzles that much either

[Campbell Ritchie]

Crossword puzzles are good for you; they prevent dementia by keeping your ??? ??? [What do you call the thing inside your head?] working. Of course I am in England, where crosswords have a twist; the clues are often “cryptic”.