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

Match a simple balanced language


9
vote

problema

Español

Pido disculpas si el título no es muy descriptivo. Si alguien puede recomendarle a uno más claro, lo editaré. Tengo una pregunta de ejercicio como:

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.

He escrito el siguiente código que resuelve el problema.

  bool isInLanguageL2(string w){      linkedStackType<string> wordStack;      int size = w.length();     int a = 0;     int b = 0;      if(size % 2 != 0)   //word length must be an equal number         return false;     else{         //read first half of word         for(int i = 0; i < size/2; i++){    //check if the first half consists of A's             if(w[i] != 'a' && w[i] != 'A')                 return false;             else                 wordStack.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid         }          //read second half of word         for(int i = size/2; i < size; i++){     //check if the second half consists of B's             if(w[i] != 'b' && w[i] != 'B')                 return false;             else                 wordStack.push(string(1, w[i]));    //convert char to string and push to stack if the letter is valid         }     }      //check number of A's and B's in the stack     while(!wordStack.isEmptyStack()){         if(wordStack.top() == "b" || wordStack.top() == "B"){             b++;             wordStack.pop();         }         else{             a++;             wordStack.pop();         }     }      //check if number of B's is equal to number of A's     if(b==a)         return true;  }   

Sin embargo, dado que la pregunta dice "No cuente el número de A's o B's". En su lugar, he creado dos pilas y solo comparé sus longitudes. ¿Hay alguna manera de hacer esto usando una sola pila desde que se menciona la pregunta utilizando a pila sin contar explícitamente las A y B para probar la palabra.

  bool isInLanguageL2(string w){      linkedStackType<string> wordStackA, wordStackB;      int size = w.length();     int a = 0;     int b = 0;      if(size % 2 != 0)   //word length must be an equal number         return false;     else{         //read first half of word         for(int i = 0; i < size/2; i++){    //check if the first half consists of A's             if(w[i] != 'a' && w[i] != 'A')                 return false;             else                 wordStackA.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid         }          //read second half of word         for(int i = size/2; i < size; i++){     //check if the second half consists of B's             if(w[i] != 'b' && w[i] != 'B')                 return false;             else                 wordStackB.push(string(1, w[i]));    //convert char to string and push to stack if the letter is valid         }     }      //check if number of B's is equal to number of A's     if(wordStackA.length() == wordStackB.length());         return true;  }   

también, tengo un seguimiento de esta pregunta. Una especie de extensión. Si debo agregarlo aquí o crear una nueva pregunta para ello, ya que podría hacer que esta pregunta sea bastante larga.

Original en ingles

I apologise if the title is not very descriptive. If someone can recommend a clearer one I'll edit it. I have an exercise question as:

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.

I've written the following code which solves the problem.

bool isInLanguageL2(string w){      linkedStackType<string> wordStack;      int size = w.length();     int a = 0;     int b = 0;      if(size % 2 != 0)   //word length must be an equal number         return false;     else{         //read first half of word         for(int i = 0; i < size/2; i++){    //check if the first half consists of A's             if(w[i] != 'a' && w[i] != 'A')                 return false;             else                 wordStack.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid         }          //read second half of word         for(int i = size/2; i < size; i++){     //check if the second half consists of B's             if(w[i] != 'b' && w[i] != 'B')                 return false;             else                 wordStack.push(string(1, w[i]));    //convert char to string and push to stack if the letter is valid         }     }      //check number of A's and B's in the stack     while(!wordStack.isEmptyStack()){         if(wordStack.top() == "b" || wordStack.top() == "B"){             b++;             wordStack.pop();         }         else{             a++;             wordStack.pop();         }     }      //check if number of B's is equal to number of A's     if(b==a)         return true;  } 

However, since the question says "Do not count the number of axe2x80x99s or bxe2x80x99s.", I've instead created two stacks and just compared their lengths. Is there a way to do this using a single stack since the question mentions using a stack without explicitly counting the A's and B's to test the word.

bool isInLanguageL2(string w){      linkedStackType<string> wordStackA, wordStackB;      int size = w.length();     int a = 0;     int b = 0;      if(size % 2 != 0)   //word length must be an equal number         return false;     else{         //read first half of word         for(int i = 0; i < size/2; i++){    //check if the first half consists of A's             if(w[i] != 'a' && w[i] != 'A')                 return false;             else                 wordStackA.push(string(1, w[i])); //convert char to string and push to stack if the letter is valid         }          //read second half of word         for(int i = size/2; i < size; i++){     //check if the second half consists of B's             if(w[i] != 'b' && w[i] != 'B')                 return false;             else                 wordStackB.push(string(1, w[i]));    //convert char to string and push to stack if the letter is valid         }     }      //check if number of B's is equal to number of A's     if(wordStackA.length() == wordStackB.length());         return true;  } 

Also, I have a follow up to this question. A sort of extension. Should I add it here or create a new question for it as it might make this question rather long.

     
         
         

Lista de respuestas

14
 
vote
vote
La mejor respuesta
 

Este ejercicio es algo inquietante. Por un lado, un stack , como parte de una Automaton de empuje , es la forma canónica de decidir lenguas equilibradas como esta; Por otro lado, hay formas mucho más eficientes, idiomáticas y prácticas de resolver ese ejercicio en particular. No está claro si es un ejercicio de ciencias de la computadora o un ejercicio de aprendizaje de idiomas, uno para hacer que los conceptos se hundan en o uno para descubrir la expresividad de C ++.

Una pila se habría justificado más fácilmente si el argumento de la función había sido un 99887776655544331 , ya que se puede atravesar solo una vez; O si las etiquetas de inicio / finalización habían venido de diferentes tipos (si son todos los mismos que hacen un entero para una pila perfecta y el conteo no debería ser discriminado).

Como dijo @mike Borland, el truco para responder a esa pregunta es evitar el conteo explícito por pop ping la pila llena con a s Mientras itera sobre el resto de la cuerda. Algo a lo largo de las líneas:

  #include <stack> #include <string>  bool is_ab_balanced(const std::string& str) {     if (!str.size()) return false;      auto it = str.begin();     std::stack<char> as;     while (it != str.end() && *it == 'a') as.push(*it++);     while (!as.empty()) {         if (it == str.end() || *it != 'b') return false;         as.pop(); ++it;     }     return it == str.end(); }   

Por cierto, notará que:

  1. Es mejor usar contenedores estandarizados a menos que necesite un comportamiento personalizado: 9988776655544335 está mejor optimizado y probado que linkedStackType<>

  2. No debe tomar un 9988776665544337 por valor como un argumento, a menos que tenga la intención de modificarla mientras mantiene la cadena original sin cambios. Aquí, no hay modificación, así que use una referencia 99887766655443388 en su lugar.

  3. Debe deshacerse de las variables no utilizadas (consulte a y std::istream&0 en su segunda versión). Esas variables superfluas probablemente son un subproducto de los malos hábitos: declarar variables demasiado por delante de su uso, y no habilitar todas las advertencias cuando compila su código.

  4. std::istream&1 S es una mejor manera de iterar en un rango: es más idiomático, es necesario aprovechar la potencia del STL, y también evita que sea extra std::istream&2 < / Código> Variable.

  5. Unos pocos golpes de llave más son mejores que std::istream&3 , que es es una mala idea

Pero, como dije, un buen ejercicio debería parecerse más a la vida real. En la vida real, usas una pila solo si es la mejor manera de ir. Entonces, ¿cómo verificaría si una cadena pertenece al idioma si pudiera elegir sin restricciones?

Mi opinión sobre eso sería:

  std::istream&4  

O, otros ejercicios más significativos habrían sido:

  • ¿Cómo verificaría si los paréntesis están equilibrados en una expresión (yo tampoco usaría una pila aquí)?

  • ¿Cómo verificaría si las etiquetas HTML están correctamente equilibradas (aquí usando una pila es significativa)?

 

This exercise is somewhat unsettling. On the one hand, a stack, as part of a pushdown automaton, is the canonical way to decide balanced languages such as this one; on the other hand, there are much more efficient, idiomatic and practical ways to solve that particular exercise. It is unclear whether it's a computer science exercise or a language learning exercise, one to make concepts sink in or one to discover C++'s expressiveness.

A stack would have been more easily justified if the function argument had been a std::istream& for instance, since it can be traversed only once; or if starting / ending tags had come of different kinds (if they're all the same an integer makes for a perfect stack and counting shouldn't be discriminated).

As @Mike Borland said, the trick to answer that question is to avoid explicit counting by popping the stack filled with as while you iterate over the rest of the string. Something along the lines:

#include <stack> #include <string>  bool is_ab_balanced(const std::string& str) {     if (!str.size()) return false;      auto it = str.begin();     std::stack<char> as;     while (it != str.end() && *it == 'a') as.push(*it++);     while (!as.empty()) {         if (it == str.end() || *it != 'b') return false;         as.pop(); ++it;     }     return it == str.end(); } 

By the way, you'll notice that:

  1. it always is better to use standardized containers unless you need customized behavior: std::stack is certainly better optimized and tested than linkedStackType<>

  2. you shouldn't take a string by value as an argument, unless you intend to modify it while keeping the original string unchanged. Here, there's no modification, so use a const reference instead.

  3. you should get rid of unused variables (see a and b in your second version). Those superfluous variables probably are a by-product of bad habits: declaring variables too far ahead of their use, and not enabling all warnings when you compile your code.

  4. iterators are a better way to iterate over a range: it's more idiomatic, it's necessary to leverage the power of the STL, and it also avoids that extra size variable.

  5. A few more key-strokes are better than using namespace std, which is is a bad idea

But, as I said, a good exercise should look more like real life. In real life, you use a stack only if it is the best way to go. So how would you check if a string belongs to the language if you could choose without restriction?

My take on that would be:

#include <string> #include <algorithm>  using Iterator = std::string::iterator; bool is_balanced(Iterator first, Iterator last) {     auto middle = std::next(first, std::distance(first, last) / 2);     return std::equal(first, middle, middle, last, [](auto a, auto b) {         return a == 'a' && b == 'b';     }); } 

Or, other more meaningful exercises would have been:

  • how would you check if parenthesis are balanced in an expression (I wouldn't use a stack here either)?

  • how would you check if html tags are correctly balanced (here using a stack is meaningful)?

 
 
         
         
3
 
vote

Papagaga hace algunos puntos buenos.

Algunas cosas que agregaría son:

Me gusta la comprobación inicial de la longitud de la cadena. En términos de la intención de la pregunta subyacente, es un tipo de trampa: si está modelando un automatón de empuje hacia abajo, no tiene acceso a la longitud de entrada antes de leerla. Sin embargo, es el tipo de cheque rápido que a menudo vale la pena tener que no tiene que cumplir con las restricciones arbitrarias: las verificaciones que pueden evitar hacer un montón de trabajo innecesario y puede simplificar el problema de una manera que reduce la posibilidad de golpear errores .

Generalmente desea evitar el uso de cadenas para mantener caracteres individuales, ya que es innecesariamente lento y caro en términos de memoria. Una cadena de C ++ estándar sostiene al menos la longitud de la cadena (que no necesita mantener, ya que siempre está 1 en las entradas de su pila) en la parte superior de la cadena real, lo que significa que está usando al menos cinco veces Tanta memoria como necesites!

Cuando obtiene una tarea de programación. Lo primero que debe hacer es verificar la especificación de qué entrada está realmente permitida, porque le informa lo complicado que tiene que hacer el código. Por ejemplo, esperaría de esa descripción que las cuerdas no contenían letras mayúsculas, y si lo hicieran, entonces "A" no se consideraría el mismo símbolo que "A". Como tal, evitaría revisar las versiones de capital.

Sin embargo,

lo más importante es asegurarse de que entiende qué concepto está tratando de explorar la pregunta. La medición del tamaño de una pila es realmente una forma cara de contar caracteres. Lo clave a tener en cuenta acerca de la primera versión de Papagaga es que no necesita un concepto de cómo comparar enteros, ya sea un 99887776555544330 más sutil 998877655544331 .

 

papagaga makes some good points.

A few things that I'd add are:

I like the initial check about string length. In terms of the intention of the underlying question, it's kind of cheating: if you're modelling a push down automaton you don't have access to the input length before you read it. Nevertheless it's the sort of quick check that is often worth having if you don't have to comply with such arbitrary restrictions: checks that can avoid doing a bunch of unnecessary work and can simplify the problem in a way that reduces the chance of hitting bugs.

You generally want to avoid using strings to hold individual characters, because it is unnecessarily slow and expensive in terms of memory. A standard c++ string holds at least the length of the string (which you don't need to hold because it's always 1 in the entries on your stack) on top of the actual string, which means you're using up at least five times as much memory as you need!

When you get a programming task the first thing you should do is check the specification for what input is actually allowed, because that informs how complicated you have to make the code. For example, I would expect from that description that the strings would not contain capital letters, and if they did then "A" would not be considered the same symbol as "a". As such, I'd avoid checking for the capital versions.

The most important thing, though, is to make sure that you understand what concept the question is trying to explore. Measuring the size of a stack is really just an expensive way of counting characters. The key thing to note about papagaga's first version is that it doesn't need a concept of how to compare integers, whether an overt b==a or the more subtle wordStackA.length() == wordStackB.length().

 
 
0
 
vote

Aunque ya tiene algunas buenas comentarios sobre su código y una solución funcional corta en la respuesta aceptada, me gustaría ofrecer una solución de procedimiento alternativa. La observación aquí es que en realidad no tiene que contar el a 99887766555443333 S, solo tiene que pasar por la cadena en dos Instrucciones y compruebe que solo encuentre a S en un lado y 9988776655544335 s en el otro. Mientras la longitud sea incluso (y no cero), esto también le dará la respuesta correcta:

  bool isInLanguageL2(string w) {     int len = w.length();      // Exclude the empty string and odd-length strings     if(len == 0 || len % 2 == 1) {          return false;      }      // Can do this with one counter until len/2, but then      // you need to check index i and len - 1 - i.     for(int front = 0, back = len - 1; front < back; ++front, --back) {         if(w[front] != 'a' || w[back] != 'b') {              return false;          }     }      return true; }   
 

Although you already have some good remarks about your code and a short functional solution in the accepted answer, I'd like to offer an alternative procedural solution. The observation here is that you do not actually have to count the as and bs, you just have to go through the string in two directions and check that you only encounter as on one side and bs on the other. As long as the length is even (and not zero) this will give you the right answer too:

bool isInLanguageL2(string w) {     int len = w.length();      // Exclude the empty string and odd-length strings     if(len == 0 || len % 2 == 1) {          return false;      }      // Can do this with one counter until len/2, but then      // you need to check index i and len - 1 - i.     for(int front = 0, back = len - 1; front < back; ++front, --back) {         if(w[front] != 'a' || w[back] != 'b') {              return false;          }     }      return true; } 
 
 
 
 

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  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...

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...

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...

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...

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...

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...

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...




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