Coincide con un lenguaje equilibrado simple usando una cola -- ++ campo con parsing camp codereview Relacionados El problema

Match a simple balanced language using a queue


0
vote

problema

Español

Hice una pregunta similar aquí que es:

El idioma L = {A N B N } Dónde N ≥ 1, es un lenguaje de todas las palabras con Las siguientes propiedades:

  • Las palabras consisten en cadenas de A lo siguen B's.
  • El número de B es igual al número de A's.
  • Ejemplos de palabras que pertenecen a L son:

ab, donde n = 1;

AABB, donde n = 2;

aaabbb, donde n = 3;

aaaabbbb, donde n = 4.

Una forma de probar si una palabra w pertenece a este idioma l es usar un Pila para verificar si el número de A salga del número de B's. Usar el siguiente encabezado y escriba una función isinlanguagel2 que usa una pila para probar si alguna palabra pertenece a L. si w pertenece a l Luego, el isinlanguagel2 debería devolverlo de otra manera isinlanguagel2 debe devolver falso.

bool isinlanguagel (cadena w);

NOTA LO SIGUIENTE:

  • Solo las palabras que pertenecen a L deben ser aceptadas.
  • La palabra bbaa no pertenece a l.
  • No cuente el número de A's o B's.

Un seguimiento de esa pregunta solicita rehacer la pregunta utilizando las colas (me doy cuenta de que una cola probablemente no sea la mejor manera de hacer esto, sin embargo, ese no es el punto del ejercicio):

Repita la pregunta anterior utilizando el siguiente encabezado:

bool isinlanguagel (queuetype & lt; char & gt; & amp; w);

Mi solución para hacer esto sin contar realmente los A y B's está a continuación. Utiliza dos colas. I "Copia" a todos los A de la cola original en una cola de temperatura y eliminándolos de la cola original, que solo deberían tener B's Resting. Luego iterré a través de la cola Temp y estuve la cola original para cada una que está en la cola Temp. Después de revisar la cola TEMP y si ambas colas están vacías al final, la palabra es válida.

Mi pregunta: ¿Cómo puedo lograr esto usando una sola cola, ya que creo que usar una cola temporal sería un desperdicio de memoria?

Mi código:

  bool isInLanguageL(linkedQueueType<char> &w){      linkedQueueType<char> temp;      if(w.front() != 'a')    //queue must start with an a         return false;      while(w.front() == 'a'){ //iterate through the a's and add them to temp queue         temp.addQueue(w.front());         w.deleteQueue();    //remove a's from original queue     }      while(!temp.isEmptyQueue() && !w.isEmptyQueue()){    //delete b for each a         if(w.front() != 'b')    //only b's should remain in original queue             return false;         else{             w.deleteQueue();             temp.deleteQueue();         }     }      //both stacks must be empty then number of b=a and word is valid     if(w.isEmptyQueue() && temp.isEmptyQueue())         return true;     return false; }  int main() {      linkedQueueType<char> wordQueue;     std::string word;      std::cout << "Enter a word belonging to language L. ";     std::cin >> word;      for(int i = 0; i < word.length(); i++){         wordQueue.addQueue(word[i]);     }      if(isInLanguageL(wordQueue))         std::cout << word << " is a valid word.";     else         std::cout << word << " is not a valid word.";      return 0; }   
Original en ingles

I asked a similar question here which is:

The language L={anbn} where n xe2x89xa5 1, is a language of all words with the following properties:

  • The words consist of strings of axe2x80x99s followed by bxe2x80x99s.
  • The number of bxe2x80x99s is equal the number of axe2x80x99s.
  • Examples of words that belong to L are:

ab, where n=1;

aabb, where n=2;

aaabbb, where n=3;

aaaabbbb, where n=4.

One way to test if a word w belong to this language L is to use a stack to check if the number of axe2x80x99s balances the number of bxe2x80x99s. Use the following header and write a function isInLanguageL2 that uses a stack to test if any word belongs to L. If w belongs to L then the isInLanguageL2 should return true otherwise isInLanguageL2 should return false.

bool isInLanguageL(string w);

Note the following:

  • Only words belonging to L should be accepted.
  • The word bbaa does not belong to L.
  • Do not count the number of axe2x80x99s or bxe2x80x99s.

A follow up to that question asks to redo the question using queues (I realize a queue probably isn't the best way to do this, however that's not the point of the exercise):

Repeat the previous question using the following header:

bool isInLanguageL(queueType< char> & w);

My solution for doing this without actually counting the a's and b's is below. It uses two queues. I "copy" all the a's from the original queue into a temp queue and remove them from the original queue which should have only b's remaining. I then iterate through the temp queue and pop the original queue for every a that is in the temp queue. After checking through the temp queue and if both queues are empty at the end, then the word is valid.

My question: How can I accomplish this using a single queue as I think using a temporary queue would be a waste of memory.

My code:

bool isInLanguageL(linkedQueueType<char> &w){      linkedQueueType<char> temp;      if(w.front() != 'a')    //queue must start with an a         return false;      while(w.front() == 'a'){ //iterate through the a's and add them to temp queue         temp.addQueue(w.front());         w.deleteQueue();    //remove a's from original queue     }      while(!temp.isEmptyQueue() && !w.isEmptyQueue()){    //delete b for each a         if(w.front() != 'b')    //only b's should remain in original queue             return false;         else{             w.deleteQueue();             temp.deleteQueue();         }     }      //both stacks must be empty then number of b=a and word is valid     if(w.isEmptyQueue() && temp.isEmptyQueue())         return true;     return false; }  int main() {      linkedQueueType<char> wordQueue;     std::string word;      std::cout << "Enter a word belonging to language L. ";     std::cin >> word;      for(int i = 0; i < word.length(); i++){         wordQueue.addQueue(word[i]);     }      if(isInLanguageL(wordQueue))         std::cout << word << " is a valid word.";     else         std::cout << word << " is not a valid word.";      return 0; } 
     
       
       

Lista de respuestas

4
 
vote

A medida que Konrad Rudolph señala en comentarios sobre la otra pregunta, es probable que esto se trate de que se trate de autómatas Pushdown, para el cual Wikipedia Page tiene algunos ejemplos útiles , y este La respuesta de StackOverFlow es muy Útil .


usando una pila

La pila se utiliza para preservar los datos mientras está a lo largo de la entrada. Movemos de izquierda a derecha desde el carácter a carácter, tomando una decisión basada en el carácter actual y en los contenidos de la pila.

Si la entrada se vuelve inválida en un punto determinado (por ejemplo, contiene un 99887776655544330 , o tiene demasiados 9988776665544331 s, etc.), podemos rechazarlo. De lo contrario, continuamos hasta que hemos procesado la entrada completa.

Para las instrucciones que le han dado, en realidad no necesitamos una pila. Un contador sería suficiente. Sin embargo, una pila permitiría equilibrar múltiples conjuntos de caracteres (por ejemplo, cadenas de equilibrio de paréntesis ([]())[] ).

En cada 'a' nos encontramos, lo empujamos a la pila. En cada 'b' nos encontramos, salimos de la pila. Si alguna vez intentamos sacar algo de una pila vacía, la entrada no está equilibrada. Al final de la entrada, la pila debe estar vacía (salimos del mismo número de 'b' 'a' s empujamos).

  bool is_balanced(std::string const& input) {     if (input.empty()) // n == 0         return false;      std::stack<char> stack;     bool is_first_word = true;      for (auto c : input)         if (!pda(stack, is_first_word, c))             return false;      return stack.empty(); }   

La cola

Como se notó, tener la entrada contenida en una cola limita cómo se puede procesar. No conocemos la longitud de la entrada de antemano. Solo podemos sacar un carácter a la vez y procesarlo.

más generalmente en C ++, entrada como esta provendría de una Stream de algún tipo < / a>.

Nota, sin embargo, que el núcleo del algoritmo sigue siendo exactamente lo mismo:

  bool is_balanced(std::queue<char>& input) {     if (input.empty()) // n == 0         return false;      std::stack<char> stack;     bool is_first_word = true;      while (!input.empty())     {         auto c = input.front();         input.pop();          if (!pda(stack, is_first_word, c))             return false;     }      return stack.empty(); }   

Tomando decisiones

Los detalles de la función pda se dejan al lector;), pero se ve algo así:

  'b'0  

Verifica el carácter actual 'b'1 , verifica la pila y empuja / POPS si es necesario. Devuelve VERDADERO si debemos mantener la entrada de procesamiento, y False de lo contrario.


Cosas raras

Hay algunas cosas ligeramente inusuales sobre las instrucciones que le han dado:

  • La entrada vacía no es válida (N debe ser y GT; = 1). A menudo, una entrada vacía se consideraría una cadena equilibrada. Este es un cheque simple para hacer sin embargo.
  • solo 'b'2 y 'b'3 Los caracteres significan que la pila es técnicamente redundante. Por lo general, uno pensaría en equilibrar paréntesis, como en la pregunta de StackOverFlow vinculada.
  • La redacción implica que las entradas como 'b'4 no son válidas, ya que esto se consideraría más de una "palabra" en el idioma especificado. Esta es la razón del 'b'5 boolean arriba. Puede ser más sencillo simplemente ignorar esto para comenzar.
 

As Konrad Rudolph points out in comments on the other question, this is probably about Pushdown Automata, for which the wikipedia page has some useful examples, and this stackoverflow answer is very helpful.


Using a stack

The stack is used to preserve data while iterating along the input. We move left-to-right from character to character, making a decision based on the current character, and the contents of the stack.

If the input becomes invalid at a certain point (e.g. it contains a 'c', or has too many 's, etc.), we can reject it. Otherwise we continue until we have processed the entire input.

For the instructions you've been given, we don't actually need a stack. A counter would suffice. However, a stack would allow balancing multiple sets of characters (e.g. balancing strings of parentheses ([]())[]).

At every 'a' we encounter, we push it onto the stack. At every ' we encounter, we pop one off the stack. If we are ever attempting to pop something off an empty stack, the input is not balanced. At the end of the input, the stack must be empty (we popped off the same number of 's as the number of 'a's we pushed on).

bool is_balanced(std::string const& input) {     if (input.empty()) // n == 0         return false;      std::stack<char> stack;     bool is_first_word = true;      for (auto c : input)         if (!pda(stack, is_first_word, c))             return false;      return stack.empty(); } 

The queue

As you noticed, having the input contained in a queue limits how it can be processed. We don't know the length of the input in advance. We can only pop off one character at a time and process it.

More usually in C++, input like this would come from a stream of some sort.

Note, however, that the core of the algorithm remains exactly the same:

bool is_balanced(std::queue<char>& input) {     if (input.empty()) // n == 0         return false;      std::stack<char> stack;     bool is_first_word = true;      while (!input.empty())     {         auto c = input.front();         input.pop();          if (!pda(stack, is_first_word, c))             return false;     }      return stack.empty(); } 

Making Decisions

The details of the pda function are left to the reader ;) , but it looks something like this:

bool pda(std::stack<char>& stack, bool& is_first_word, char c) {     if (c == 'a')     {         // check the stack, push / pop, return true / false     }     else if (c == 'b')     {         // check the stack, push / pop, return true / false     }     else         return false; // invalid character } 

It checks the current character 'c', checks the stack, and pushes / pops if necessary. It returns true if we should keep processing input, and false otherwise.


Weird Things

There are a few slightly unusual things about the instructions you've been given:

  • Empty input is invalid (n must be >= 1). Often an empty input would be considered a balanced string. This is a simple check to make though.
  • Only 'a' and ' characters means the stack is technically redundant. Usually one would think about balancing parentheses, as in the linked stackoverflow question.
  • The wording implies that inputs like "abab" are invalid, as this would be considered more than one "word" in the specified language. This is the reason for the is_first_word boolean above. It might be simpler to just ignore this to start with.
 
 

Relacionados problema

7  Parser para fórmulas CNF  ( Parser for cnf formulas ) 
Tengo un analizador para las fórmulas CNF en Formato DIMACS , que es muy lento. ¿Alguna sugerencia sobre cómo mejorar su velocidad? Hice algún perfil y podrí...

4  Clase de análisis y manejo de URI  ( Uri parsing and handling class ) 
Escribí una clase simple para lidiar con el análisis y manejar URIS para el proyecto en el que estoy trabajando actualmente, ya que se basa mucho en esa funci...

4  Posibles peligros de desbordamiento de búfer en el programa de análisis de registro C  ( Possible buffer overflow dangers in c log parsing program ) 
Después de horas de trabajo, finalmente terminé mi primer programa de análisis de registro C! (Anteriormente fue un guión bash, ahora es C). ¡Aunque creo qu...

6  Otro analizador de JSON y serializador para QT, pero con características adicionales  ( Yet another json parser and serializer for qt but with additional features ) 
Escribí QJson , una clase de utilidad en / para qt, necesito que eche un vistazo. Tanto es un analizador y serializador JSON, sino con una funcionalidad exte...

8  Dividir datos de diccionarios de texto lisos a múltiples archivos  ( Splitting plain text dictionary data to multiple files ) 
Tengo un archivo de texto simple con el contenido de un diccionario ( Diccionario no arabidgigado de Webster ) en este formato: A A (named a in the Englis...

7  Analizador de cadena citado  ( Quoted string parser ) 
He escrito un analizador de cadena que está diseñado para dividir una cadena por espacios, excluyendo espacios envueltos en cuerdas. Aquí hay algunas entrad...

6  Programa de Convertidor de Infix a Postfix  ( Infix to postfix converter program ) 
Esta es mi tarea. Amablemente ayúdame a verificarlo? Las instrucciones son: Implementar una expresión de infIX en el convertidor de expresión postfix. De...

6  Usando GetOpt analizar y validar los argumentos de la línea de comandos  ( Using getopt parse and validate command line arguments ) 
Estoy aprendiendo getopt en Python para analizar y validar las entradas de la línea de comandos: #!/usr/bin/python ''' Mailing Script Usage: python scrip...

2  libconfini (biblioteca compartida)  ( Libconfini shared library ) 
Recientemente escribí una pequeña biblioteca de análisis INI. El código también está en GitHub , con documentación . Me gustaría tener opiniones, sugerencia...

8  Hola, Java World ~> analizando una cuadrícula de sudoku  ( Hello java world parsing a sudoku grid ) 
Este es mi primer intento, muy, muy, por primera vez en Java . No he empezado a abordar la resolución real de la sudoku Puzzle (ni siquiera estoy seguro de...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos