Как сравнить строку, чтобы увидеть, равны ли символы, введенные до «$», символам после нее?

Question

Я реализовал алгоритм для книги, который выглядит следующим образом:

L = {w $ w ': w, возможно, пустая строка символов, чем $ w' = reverse (w)}

Следуя псевдокоду books, я написал код для моей программы, который будет принимать введенную вами строку, например (A $ A, ABC $ CBA), и сравнивать символы до и после $, чтобы определить, являются ли они палиндромом. , Я написал код точно так, как было указано в книге, но программа работает неправильно. Независимо от того, что я ввожу, оно всегда возвращает false.

Я не знаю, что я делаю неправильно.

Вот код, который я написал:

#include <iostream>
#include "stack.h"
#include <string>
using namespace std;

bool isInLanguage(string aString)
{
  Stack<char> aStack;

  int i = 0;
  // ch is aString[i]
  while( aString[i] != '$')
  {
      aStack.push(aString[i]);
      ++i;
  }

  //skip the $
  ++i;

  //match the reverse of w
  bool inLanguage = true; // assume string is in language
  while(inLanguage && i < aString.length())
  {

      char stackTop;
      aStack.pop(stackTop);
      if(stackTop == aString[i])
          ++i; //characters match
      else
          //top of stack is not aString[i]
          inLanguage = false; //reject string
      if(aStack.isEmpty())
  {
      //pop failed, stack is empty. first half of string
      //is shorter than second half)
      inLanguage = false;
  } // end if

  } // end while
   if (inLanguage && aStack.isEmpty())
          return true;
      else
          return false;
} // end isInLanguage

int main()
{
    string str;
    bool boolean;
    cout << "Enter a string to be checked by the algorithm : ";
    cin >> str;
    boolean = isInLanguage(str);
    if (boolean == true)
        cout << "The string is in language.\n";
    else 
        cout << "The string is not in language.\n";
    return 0;

}

Answer 1

Даже после извлечения последнего символа из строки вы проверяете if(aStack.IsEmpty()), который возвращает true, что в свою очередь устанавливает inLanguage в false.Таким образом, даже если строка была палиндромом, вы все равно устанавливаете inLanguage в false после добавления последнего символа.

Answer 2

Ваша логика в цикле while неверна, как сказал Навин.Посмотрите, что происходит с простым случаем $ a:

push 'a' in the stack
skip $
pop 'a' and compare with 'a' -> inLanguage == true
stack is empty -> inLanguage == false

Это явно не то, что вы хотите.Вам необходимо проверить размер стека в состоянии цикла.Я бы упростил цикл примерно до следующего:

while (i < aString.size() && !aStack.isEmpty()) {
    char stackTop;
    aStack.pop(stackTop);
    if(stackTop != aString[i]) break;
    ++i;  
}

if (i == aString.size() && aStack.isEmpty())
    return true;
else
    return false;

Answer 3

вы не переинициализировали переменную i = 0 перед циклом while операции pop.

....
 ++i; 

  //match the reverse of w 
  bool inLanguage = true; // assume string is in language 
  while(inLanguage && i < aString.length()) 
  { 
 .....

в соответствии с вашим кодом условие i < aString.length в цикле while всегда будет ложным.

попробуйте это до цикла while ..

i = 0;