3

Tengo una duda con respecto a la creación de una pila es c++ con la librería stl. Dicha pila tiene que ser aquella que, cuando el usuario ingrese una expresión algebraica por teclado, por ejemplo (a + { b * c – d } / e), entonces como salida del programa sería, si dicha expresión algebraica es correcta o incorrecta, es decir, si esta correctamente construida o no. Un ejemplo de un error sería por ejemplo (a + b o { d + [ e * f } ]. Mi duda principal sería que, aunque sé como se hace una pila en general, no sé como comparar los elementos entre sí para saber si los paréntesis, corchetes y llaves están formados correctamente. Sé que hay que usar una variable tipo caracter para la "ecuación" y un booleano que se active cuando sea correcta o incorrecta la ecuación, para posteriormente mostrar por pantalla si la ecuación algebraica es correcta o no.

Lo que llevo es lo siguiente, que también plantee un algoritmo dentro del programa mientras lo analizaba:

#include<iostream>
#include<stack>
using namespace std;

int main(){

    stack<char> pila;

    int a,b,c,d;

 cout<<"Ingrese valor para a,b,c,d"<<endl;
 cout<<"Ingrese valor para a"<<endl;
 cin>>a;
 cout<<"Ingrese valor para b"<<endl;
 cin>>b;
 cout<<"Ingrese valor para c"<<endl;
 cin>>c;
 cout<<"ingrese valor para d"<<endl;
 cin>>d;

    //Algoritmo para la función que se situa en esta parte del programa
// i) Leer el primer símbolo 
//(1) Si es un símbolo de apertura de ( ‘(‘, ‘[‘, ó ‘{‘ ), guardarlo en la PILA.
//(2) Si es un símbolo de cierre de parentización ( ‘)’, ‘]’, ‘}’ ), extraer el tope de la PILA y comprobar que ambos símbolos se corresponden.
//(3) En otro caso, no hacer nada.
//ii) Si no estamos al final, leer el siguiente símbolo de la LISTA e ir a (i.1).
//iii) Si estamos al final:
//(1) Si la PILA está vacía -> OK.
//(2) Caso contrario, la expresión es errónea

    char ecuacion; //le he puesto char porque lleva llaves, corchetes y parentesis {[(
    cout<<"Ingrese la ecuacion que desea resolver (usando parentesis, corchetes y llaves)"<<endl;
    cin>>ecuacion;

    int sw=0; //este sw se colocara en cero si la ecuacion esta bien formada, es decir, primero { despues [ y despues ( lo mismo para los cierres
    int sw=1; //este sw se colocara en 1 si dicha ecuacion esta incorrecta

    if (sw==0)
    cout<<"Verdadero. La ecuación esta correctamente escrita"<<endl;

    if (sw==1)
    cout<<"Falso. La escuación esta escrita de forma incorrecta"<<endl;


}

Lo de declarar las variables para que me calcule el resultado matemático de la ecuación no es importante ni lo necesito (es opcional), pero me gustaría saber como lograrlo ya que no sé como implementarlo, aunque creo que hay que usar una librería especial.

Con respecto a mi duda principal, como dije anteriormente, no sé como comparar los elementos para saber si la ecuación esta correctamente formada, ni como hacer para buscar dentro de una "variable" tipo carácter, un paréntesis, un corchete y una llave, y como se haría para buscarlas por orden de prioridad para después compararlas entre si? es decir, primero buscar en la variable tipo carácter el paréntesis, después el corchete y después la llave, o en orden inverso, que sería la llave, el corchete y después el paréntesis, que posiblemente sería la mejor manera de implementarla la ultima porque que estamos hablando de una estructura de datos tipo pila (ultimo en llegar, primero en salir). Agradecería mucho sus respuestas

1
  • Hola. si declaras char ecuacion solamente obtendras el primer char de la ecuacion es decir solo te leerá un (1) caracter, debes declararlo tipo string y luego ir recorreriendo el string con ecuacion[i] en un ciclo for (por ejemplo) que valla de i=0 hasta i < ecuacion.strlen() luego puedes usar la funcion == para comparar dentro de un if el 30 mar. 2017 a las 0:21

3 respuestas 3

2

Mi duda principal sería que, aunque sé como se hace una pila en general

Una pila, por definición, es un contenedor en el que los elmementos se insertan y extraen en un orden determinado. Existen dos tipos:

  • LIFO (o pila): Similar a una pila de platos, el último en añadirse al montón es el primero en fregarse.
  • FIFO (o cola): Como para comprar entradas, el primero que llega es el primero en ser atendido.

Implementar una pila a mano es algo bastante tedioso ya que te obligaría a lidiar con la memoria dinámica. En vez de implementar una puedes aprovechar, ya que hablas de la STL, del contenedor stack que implementa una pila LIFO que es la que tienes que usar en tu caso.

no sé como comparar los elementos entre sí para saber si los paréntesis, corchetes y llaves están formados correctamente

Una posibilidad es crear un mapa que relacione los elementos:

std::map<char,char> mapa;
mapa[')'] = '(';
mapa[']'] = '[';
mapa['}'] = '{';

Así, para saber si las llaves son complementarias podrías hacer algo tan trivial como:

char cierre = ')';
char elementoExtraidoDeLaPila = '(';
if( mapa[cierre] == elementoExtraidoDeLaPila )
  // ok
else
  // error

Otra forma, quizás más fácil de entender si estás aprendiendo, es usar dos cadenas alineadas: Una contiene las llaves de apertura y la otra las de cierre.

const std::string aperturas = "([{"; const std::string cierres = ")]}";

Comprobar entonces si las llaves son complementarias sería tan sencillo como averiguar la posición que ocupa la llave de cierre actual en su cadena y comprobar que la llave de apertura que se encuentra en su correspondiente cadena es igual a la que extraes de la pila:

char cierre = ')';
char elementoExtraidoDeLaPila = '(';
size_t pos = cierres.find(cierre);
if( llaves[pos] == elementoExtraidoDeLaPila )
  // ok
else
  // error

Sé que hay que usar una variable tipo caracter para la "ecuación" y un booleano que se active cuando sea correcta o incorrecta la ecuación

Si necesitas usar la ecuación a posteriori, por ejemplo para resolverla, no puedes recuperarla caracter a caracter sino que necesitas almacenarla al completo y eso solo es posible en una cadena. En este caso yo te recomendaría std::string en vez de las cadenas estilo C char[]:

std::string ecuacion;
std::cin >> ecuacion;

En cuanto al booleano. Es cierto, el chequeo únicamente puede devolver dos posibles resultados: correcto o incorrecto y eso se debería representar con un booleano. Fíjate que, en este caso, has declarado sw como un int... el tipo correcto debería ser bool:

bool sw = true;

if( /* ... */ )
  sw = false;

if( sw )
  std::cout << "Correcto";
else
  std::cout << "Error";

Dicho esto, el problema se puede plantear desde diferentes enfoques, aunque en líneas generales el algoritmo debería seguir el siguiente esquema:

  • Recorres la cadena de la fórmula caracter a caracter
  • Si te encuentras con un caracter de apertura, verificas que el caracter sea el esperado (segun la prioridad que comentas) y, si es correcto, lo añades a la pila.
  • Si te encuentras un caracter de cierre, verificas que sea el complementario al elemento que extraes de la pila.
  • Cuando termines de recorrer la fórmula verificas que la pila está vacía.

Lo de declarar las variables para que me calcule el resultado matemático de la ecuación no es importante ni lo necesito

Todo aquello que no sea necesario para reproducir el problema que planteas te sugiero que lo omitas en la pregunta. Crear un ejemplo mínimo que verifique el problema puede no ser sencillo pero ayuda a que te demos respuestas más concretas.

no sé como comparar los elementos para saber si la ecuación esta correctamente formada

Una posible implementación, en base a lo que te he puesto, puede ser la siguiente:

#include <iostream>
#include <string>
#include <stack>

int main()
{
  std::string ecuacion;
  const std::string llaves  = "([{";
  const std::string cierres  = ")]}";

  std::cin >> ecuacion;

  bool sw = 1; // Inicialmente la ecuacion sera correcta

  std::stack<char> pila;
  std::string::const_iterator llaveEsperada = llaves.begin();
  for( size_t i=0; i<ecuacion.size() && sw; ++i )
  {
    const char caracterActual = ecuacion[i];

    if( llaves.find(caracterActual) != std::string::npos )
    {
      sw = caracterActual == *llaveEsperada;
      ++llaveEsperada;
      pila.push(caracterActual);
    }
    else
    {
      const size_t posCierre = cierres.find(caracterActual);
      if( posCierre != std::string::npos )
      {
        if( pila.empty() )
          sw = 0;
        else
        {
          const char caracterEnPila = pila.top();
          pila.pop();

          sw = (caracterEnPila == llaves[posCierre]);
        }
      }
    }
  }

  if( !pila.empty() )
    sw = false;

  std::cout << sw;
}

Daría como buenas tanto llaves anidadas como sin anidar aunque no obliga a usar necesariamente todas las llaves:

([{}])
([]{})
()[{}]
()[]{}
([])

Y detecta tanto solapamientos como el orden incorrecto:

([)]
(
)(
{}
[()]

Y, como puedes ver, no tiene en cuenta si el contenido entre las llaves es algo válido o no, pero se ajusta a los comentarios que has puesto.

2
  • Gracias por la respuesta me ha servido bastante, aunque hay un pequeño detalle que se me olvido mencionar en la pregunta que era que, la expresión { d + [ e * f ] – ( d / e) } también es correcta, tanto como (a + { b * c – d } / e) por eso como errores "{}" y "[()]" más bien serian tomados como correctos el 30 mar. 2017 a las 16:18
  • @GreciaV.P.Valero en los comentarios de tu código das a entender que los operadores tienen un orden concreto
    – eferion
    el 30 mar. 2017 a las 20:15
2

¿Pila? ¿¡Por qué pila!?

No se de dónde sale la idea de usar una pila (stack) para este tipo de tarea, pero no es la primera vez que lo leo y no es para nada correcto.

Una pila se caracteriza por mantener el orden en que se insertan los datos y el orden en que éstos son extraídos, también dependiendo del orden de inserción (pudiendo ser FIFO o LIFO); en tu caso el orden de inserción o extracción de los datos te es indiferente y lo que realmente te interesa es recorrer los elementos de la pila.

Por desgracia, una pila no está pensada para ser recorrida de manera secuencial si no para añadir (push) y quitar (pop) elementos en un orden determinado, por eso una pila (stack) no ofrece ninguna función o utilidad para recorrer sus elementos y por este motivo es completamente inútil para el objetivo que sigues. Así que seguramente una pila no sea el contenedor que debes escoger (echa un vistazo a esta pregunta para hacerte una idea).

Cambia a std::string y ¡usa una pila! O_o

Seguramente te han comentado que debes usar una pila no para almacenar la expresión si no para analizarla. Es el contenedor ideal para este cometido, si sigues esta lógica:

  • Inserta (push) un elemento a la apertura de un agrupador ([, ( o {).
  • Al encontrar el cierre de un agrupador (], ) o }) elimínalo (pop) siempre y cuando el techo de la pila (top) sea la apertura del agrupador del que has encontrado el cierre, en caso contrario la expresión no será válida.
  • También será una expresió no válida si al finalizar la expresión la pila no está vacía.

Implementación.

Una posible implementación sería esta:

bool expresion_correcta(const std::string &expresion)
{
    std::stack<char> agrupadores;

    for (const auto &caracter : expresion)
    {
        if (es_apertura(caracter))
        {
            agrupadores.push(caracter);
        }
        else if (es_cierre(caracter))
        {
            if (mi_cierre(agrupadores.top()) == caracter)
            {
                agrupadores.pop();
            }
            else
            {
                std::cout << "Error en \""
                          << expresión
                          << "\": se esperaba '"
                          << mi_cierre(agrupadores.top())
                          << "' se encuentra '"
                          << caracter << "'\n";
                return false;
            }
        }
    }

    if (agrupadores.empty())
    {
        std::cout << "Expresion: \""
                  << expresión
                  << "\" correcta\n";
        return true;
    }

    std::cout << "Error en \""
              << expresión
              << "\": '"
              << agrupadores.top()
              << "' sin cierre\n";
    return false;
}

Esta implementación no es perfecta a nivel de diseño pero es correcta a nivel funcional. Puedes ver el código funcionando En Wandbox 三へ( へ՞ਊ ՞)へ ハッハッ.

7
  • Shunting Yard utiliza 2 pilas?
    – NaCl
    el 30 mar. 2017 a las 11:25
  • @NaCl no tengo ni idea de qué me estás hablando. el 30 mar. 2017 a las 12:22
  • El algoritmo Shunting Yard, creo que de eso se habla en esta pregunta :O
    – NaCl
    el 30 mar. 2017 a las 12:27
  • 1
    @NaCl eres el primero que menciona dicho algoritmo en todo el hilo ;) pero es posible que alguno lo estemos usando sepamos o no sepamos de su existencia... en cuanto a mi: no lo conozco. el 30 mar. 2017 a las 12:28
  • Gracias por la respuesta, pero me sale error al compilarlo en DevC++ i86.photobucket.com/albums/k103/greciavpv/… el 30 mar. 2017 a las 16:37
1

Esto es una posible implementación de lo que entiendo quieres hacer.

Se limita a contar los símbolos de apertura y cierre, para comprobar que estén presentes en la misma cantidad. Si hay 5 (, tiene que haber otros 5 ).

No comprueba otros posibles factores, como que estén mezclados en un orden incorrecto.

#include <iostream>

using namespace std;

int checkEqu( const string &equ ) {
  int phars = 0, // (
      bracs = 0, // {
      cors = 0;  // [
  size_t idx;

  for( idx = 0; idx < equ.size( ); ++idx )
    switch( equ[idx] ) {
    case '(':
      ++phars;
      break;

    case ')':
      --phars;
      break;

    case '{':
      ++bracs;
      break;

    case '}':
      --bracs;
      break;

    case '[':
      ++cors;
      break;

    case ']':
      --cors;
      break;
    }

    if( phars )
      cout << ( phars > 0 ? "Faltan" : "Sobran" ) << " paréntesis de cierre.\n";

    if( bracs )
      cout << ( bracs > 0 ? "Faltan" : "Sobran" ) << " llaves de cierre.\n";

    if( cors )
      cout << ( cors > 0 ? "Faltan" : "Sobran" ) << " corchetes de cierre.\n";

  return phars | bracs | cors;
}

int main( void ) {
  string equ;

  cout << "Ingrese ecuación: ";
  getline( cin, equ );

  if( !checkEqu( equ ) )
    cout << "Expresión correcta." << endl;

  return 0;
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.