使用三个堆栈的回文 - 仅输出 "is a palindrome" （java 逻辑错误）

Question

我一直在查看每一个 post 与回文这个词，但我没有遇到任何与我遇到的相同类型的问题...

我的目标是使用三个堆栈来识别回文——当输入“madam”时，输出应该是“madam is a palindrome”，当输入“orange”时，输出应该是“orange is not a palindrome” ”。无论如何，我只能得到“...是回文”输出

我正在尝试遵循以下算法：

将每个字符压入原始栈和临时栈
从临时堆栈弹出每个字符并将字符推入新堆栈（颠倒顺序）
将原始堆栈与反向堆栈进行比较

这背后的思考过程是每次原始堆栈中的一个字符与反向堆栈不匹配时，变量 mismatches 递增，如果不匹配的次数超过零，则单词输入的是回文

代码如下：

import java.util.Scanner;
import java.util.Stack;

public class Palindrome {

    public static boolean is_palindrome(String input) {
        
        Stack<Character> original = new Stack<Character>();
        Stack<Character> reversedStack = new Stack<Character>();
        Stack<Character> tempStack = new Stack<Character>();
        
        Character letter;           //one character from the input string
        int mismatches = 0;         //number of spots that mismatched
        int index;                  //index for the input string
        
        for(index = 0; index < input.length(); index++) {
            
            letter = input.charAt(index);
            
            if(Character.isLetter(letter)) {
                
                original.push(letter);
                tempStack.push(letter);
                
            }
            
            reversedStack.push(tempStack.pop());
            
        }
        
        while(!original.isEmpty()) {
            
            if(!original.pop().equals(reversedStack.pop())) { mismatches++; }
            
        }
        return (mismatches == 0);
        
    }
    
    //main() method, used for testing program
    @SuppressWarnings("resource")
    public static void main(String[] args) {
        
        Scanner input = new Scanner(System.in);         //user input
        String word;                                    //one input line
        
        do {
            
            System.out.print("Enter a word: ");
            word = input.nextLine();
            
            if(is_palindrome(word)) { System.out.println(word + " is a palindrome."); }
            else { System.out.println(word + " is not a palindrome."); }
            
            break;
            
        } while(word.length() != 0);

    }

}

关于为什么只打印“...是回文”的任何提示？

Answer 1

假设输入全是字母。然后，您的初始 for 循环将：

将字母推到original。
将字母推到tempStack。
弹出 tempStack，然后将其推入 reversedStack。

换句话说，这只是一种愚蠢的做法：

将字母推到original
把字母推到reversedStack
tempStack 仍然是空的。

显然不是你想要的。 'pop tempStack and push into reversedStack' 功能需要一个新的独立 while 循环。

注意：作为旁注，这是一个非常复杂的算法来完成这项工作，但大概任务是学习堆栈，并通过做 Rube Goldberg 机器工作来做到这一点。以防万一这不是重点，这可以通过简单地循环一次，从 0 到输入长度的一半，并将索引 i 处的字符与索引 len - i 处的字符进行比较来简单地完成。整个方法可以放在 4 行中，并使用零个对象来完成工作。

Answer 2

你不需要三叠。单栈即可解决

将每个字符推送到 Stack。
将弹出的字符与字符串从头开始的字符进行比较。 Return false 一旦发现不匹配；否则，return true 如果所有字符都匹配。

演示：

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // Test
        System.out.println(isPallindrome("madam"));
        System.out.println(isPallindrome("orange"));
    }

    static boolean isPallindrome(String s) {
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        for (char c : arr) {
            stack.push(c);
        }

        for (char c : arr) {
            if (c != stack.pop()) {
                return false;
            }
        }

        return true;
    }
}

输出：

true
false

不过，如果您有空可以使用其他任何方法来解决，下面给出的是更简单的方法：

public class Main {
    public static void main(String[] args) {
        // Test
        System.out.println(isPallindrome("madam"));
        System.out.println(isPallindrome("orange"));
    }

    static boolean isPallindrome(String str) {
        return new StringBuilder(str).reverse().toString().equals(str);
    }
}

输出：

true
false

Answer 3

这个方法极其复杂！您可以在一个 for 循环中确定一个单词是否为回文（并且您只需要遍历单词的一半） - 比较索引 i 和索引长度处的字符 - i，遍历 Math.floor(wordLength / 2) 个字符如果有一处不匹配，则不是回文 - 中断循环并打印失败...

使用三个堆栈的回文 - 仅输出 "is a palindrome" （java 逻辑错误）

Palindrome using three stacks - only output is "is a palindrome" (java logical error)

java

stack

palindrome