Dividir polinomio en monomios C++

gomezjuan · 18 Mayo 2020, 13:39 PM

Necesito hacer un programa que dado un polinomio lo guarde en un string, lo divida en monomios y se asegure de que la estructura es correcta y devuelva error si no tiene esa estructura.
La estructura que debe tener el monomio es:
```
1. Signo + o -
2. COEFICIENTE: uno o mas dígitos enteros (0,...,9)
3. x
4. signo ^
5. EXPONENTE: uno o mas dígitos enteros (0,...,9)
```
He pensado en dividir el polinomio en monomios cada vez que lea un signo y guardarlo en un vector, pero no se como asegurarme de que cumple la estructura:
Tengo:

Código (cpp) [Seleccionar]

int main(){
  std::string ecuacion = "+3x^2-2x^1+9x^5-4+5x^3+1";
  
  for(int i = 1; i <= ecuacion.size(); i++){
    std::cout << ecuacion[i-1];
    if(ecuacion[i] == '+' || ecuacion[i] == '-'){
      std::cout << std::endl;
    }
  }  
return 0;
}

Por consola imprime:

Código [Seleccionar]

+3x^2
-2x^1
+9x^5
-4
+5x^3
+1

K-YreX · 18 Mayo 2020, 17:05 PM

Cita de: gomezjuan en 18 Mayo 2020, 13:39 PM
La estructura que debe tener el monomio es:
```
1. Signo + o -
2. COEFICIENTE: uno o mas dígitos enteros (0,...,9)
3. x
4. signo ^
5. EXPONENTE: uno o mas dígitos enteros (0,...,9)
```

Esta estructura que dices que debe cumplirse no se cumple. Casos:

Término independiente -> solo tiene signo y coeficiente.
Monomio grado 1 -> solo tiene signo, coeficiente y x.

De todas maneras, una vez que ya lo tienes separado en monomios, te digo cómo puedes validar cada uno de estos. Mi recomendación es que crees una clase Monomio con coeficiente y exponente. Así podrás manejar los datos fácilmente y no desperdigarlos. Una idea del algoritmo sería:
Código [Seleccionar] Expandir
validarMonomio(string) : Monomio // Funcion que recibe un string (monomio) y devuelve un objeto de tipo Monomio INICIO exponente = 0 // Exponente por defecto i := 1 // El 0 ya sabes que es '+' o '-' // Calcular la longitud del coeficiente: MIENTRAS i < monomio.size() AND es_digito(monomio[i]) HACER // Recuerda la primera condicion para no salirte del string i := i + 1 FIN MIENTRAS SI i = 1 ENTONCES // No hay digitos despues del signo Mostrar Error Salir FIN SI coeficiente = monomio.substring(0, i) // Ya tienes el COEFICIENTE y con signo // Comprobar si es el termino independiente: SI i < monomio.size() ENTONCES // Si no acaba ahi y entonces no es el termino independiente... SI monomio[i] != 'x' ENTONCES // ...debe continuar con una 'x' Mostrar Error Salir FIN SI coeficiente = 1 // y ahora el coeficiente por defecto sera 1, no 0 i := i + 1 // Si no acaba con la x, tiene que seguir '^' y el exponente SI i < monomio.size() ENTONCES SI monomio[i] != '^' ENTONCES Mostrar Error Salir FIN SI // Procedemos a calcular el exponente i := i + 1 inicio := i MIENTRAS i < monomio.size() AND es_digito(monomio[i]) HACER i := i + 1 FIN MIENTRAS // Si no hay digitos despues de '^' o hay algo mas despues de los digitos, esta mal SI i = inicio OR i < monomio.size() ENTONCES Mostrar Error Salir FIN SI exponente = monomio.substring(inicio, i) // Ya tienes el EXPONENTE FIN SI FIN SI RETURN new Monomio(coeficiente, exponente) FIN

Es un poco largo pero no lo podía probar así que he ido separando y explicando cada posible situación para procurar no dejarme nada.
Ahora pásalo a C++ y si te da algún problema, coméntalo.
Suerte.

PD: Además puede darse que tengas varios monomios del mismo grado (como en tu ejemplo: -4 y +1). Una vez separados todos, deberías comprobarlo y juntarlos.

gomezjuan · 18 Mayo 2020, 18:05 PM

Muchas gracias, no entiendo muy bien a que te refieres con la primera linea la de validar monomio.
La estructura del monomio seria así?

Código [Seleccionar]

struct monomio {
 int coeficiente;
 int exponente;
};

Y como puedo guardar los monomios en la estructura?

gomezjuan · 18 Mayo 2020, 18:58 PM

He eliminado lo del signo ^ y ahora despues de la x tendria que ir un numero directamente o nada si el exponente es 1.

Código [Seleccionar]

#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <iostream>

typedef struct{
 int coeficiente;
 int potencia;
}monomio;
 
int main(){
  std::string ecuacion = "+3x2-2x1+9x5-4+5x3+1";
  
  for(int i = 0; i < ecuacion.size(); i++){
    //std::cout << ecuacion[i];
    if(ecuacion[i] == '+' || ecuacion[i] == '-'){
           
 }
  }
  int exponente = 0; //Exponente por defecto
  int j = 1; //La posicion 0 ya sabemos que es + o -
  // Longitud del coeficiente:
  while(j < monomio.size() && isdigit(monomio[j]){
   j = j + 1;
  }
  if(j = 1){//No hay numeros despues del signo
   std::cout << "La estructura no es correcta, no hay numeros despues del signo " << std::endl;
   return 1;
  }
  coeficiente = monomio.substring(0,j); //Ya tenemos el coeficiente con el signo
  
  //Comprobar si es el termino independiente
  if( i < monomio.size()){
   if(monomio[i] != 'x'){
    std::cout << "La estructura no es correcta, falta una x" << std::endl;
    return 1;
   }
 coeficiente = 1; //El coeficiente por defecto sera 1
 int j = j + 1;
 //Si no acaba en la x tiene que seguir con el exponente
 int inicio = 1;
 while( j < monomio.size() && isdigit(monomio[j])){
  j = j + 1;
 }
 // Si no hay digitos despues de la x o hay algo mas devuelve error.
 if(j = inicio || j < monomio.size()){
  std::cout << "Error" << std::endl;
  return 1;
 }
 exponente = monomio.substring(inicio,j));
  }
  
  
return 0;
}

Serapis · 18 Mayo 2020, 19:08 PM

Se te está pidiendo un reconocedor de lenguaje, un autómata.
Tienes que empezar por definir correctamente el problema.
La mejor manera es hacerlo en BNF...

expresion = valor operador valor|operador valor // operación binaria y monaria
valor = [signo] numero [variable]
expresion = monomio|numero [operador expresion] // uno y/o más numeros o monomios
monomio = [signo] numero [potencia]
potencia = opPotencia numero
signo = "+"|"-" // un signo también es un operador como se verá más abajo.
numero = digito numero // uno o más dítitos.
digito = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
operador = "+"|"-"|"*"|"/" // Se puede añadir los operadores que se quiera.
opPotencia = "^"
variable = "a"|"b"|"c"| ... |"x"|"y"|"z" // OJO: Variable es una sola letra minúscula (deducido a partir de la expresión de ejemplo)

Desde ahí se puede pasar ya a codificarlo, pero se requiere cierta experiencia para poder hacerlo clara y eficientemente... para aprender es mejor interponer el propio autómata sus estados, así que es ése el pseudocódigo que te pongdré más abajo...

Ahora se trata de generar una tabla con los estados de transición conforme a las reglas previas:
Una tabla de estados es un cuadro donde se colocan todas las variables en juego (pueden agruparse caso de 0-9, a-z cuando para ellos se dan idénticas condiciones sin excepción), esto es, el estado actual, los estados previos y se rellena con el estado de transición.

En vertical el token actualmente siendo leído, en horizontal el token previo (no hay problema en intercambiarlo, siempre que quede claro).
La tabla recoge a que estado avanza desde el token previo al token actual...

previo| signo | 0-9 | a-z | separador | operador | potencia |
----------------------------------------------------------------
actual|---------------------------------------------------------
----------------------------------------------------------------
signo | 6? | 1 | 5 | - | 2 | e |
----------------------------------------------------------------
0-9 | 6 | 1 | e | - | 2 | 1 |
----------------------------------------------------------------
a-z | 6 | 5 | e | - | 2 | e |
----------------------------------------------------------------
sepa. | x | x | x | - | x | e |
----------------------------------------------------------------
oper. | e | 1 | 2 | - | e | e |
----------------------------------------------------------------
opPow | e | e | 7 | - | e | e |
----------------------------------------------------------------
otros | e | e | e | - | e | e |
----------------------------------------------------------------

La tabla de estados se lee como sigue:
- Un valor 'e' significa un estado de error. Si se da debe abortarse y darse por fallida la validación de la expresión.
- Un valor 'x' significa que es un estado superfluo, no se hace nada (debe ignorarse, esto supone devolver a token su valor previo) y seguir leyendo.
- Un valor '-' significa que dicho estado no se dará, porque cuando sucedió, es transitorio en el mismo ciclo al estado previo.
- Un valor '6?' significa un estado 6, pero que debe hacerse una comprobación posterior (in situ).
- El resto de valores indican el estado al que se cambia, desde el token actual y sabiendo el token previo.
El estado final de la validación debe ser 1 ó 5. Estos valores señalan que se ha validado correctamente, si al llegar al final de la expresión se tiene un estado 2 ó 6, la expresión hasta ese momento es correcta, pero incompleta, por tanto se da como errónea.

Como hablamos de tokens... conviene crear una enumeración y un array que 'tokenice' cada carácter en nuestro 'lenguaje'
Antes de nada, pues, establecemos valores para reconocerlos.

Código [Seleccionar]

enumeracion TipoToken
      //TOKEN_ESCAPE = -2
      //TOKEN_ERROR = -1
      TOKEN_DESCONOCIDO = 0
      TOKEN_DIGITO = 1
      TOKEN_OPERADOR = 2
      TOKEN_SIGNO = 6  // es también un operador.
      TOKEN_SEPARADOR = 3
      TOKEN_VARIABLE = 5
      TOKEN_OPPOTENCIA = 7
fin enumeracion

TipoToken Tokens(0 a 255)

funcion Inicializar
     entero k

     // Digitos: 0-9
     bucle para k desde 48 hasta 57  
          Tokens(k) = TOKEN_DIGITO
     siguiente

    // Variables: a-z
    bucle para k desde 97 hasta 122
          Tokens(k) = TOKEN_VARIABLE
     siguiente

    // Operadores (y signo):
     // la función 'ASCII', es una forma de dejar claro el contenido asociado más que evitarse poner el valor ascii asociado a cada uno de ellos.
    Tokens(ascii("+")) = TOKEN_SIGNO
    Tokens(ascii("-")) = TOKEN_SIGNO
    Tokens(ascii("*")) = TOKEN_OPERADOR
    Tokens(ascii("/")) = TOKEN_OPERADOR

    // Operador Potencia:
    Tokens(ascii("^")) = TOKEN_OPPOTENCIA   

    // Separadores:  'espacio' (pués es solo un jemeplo, que puedes ampliar)
    Tokens(ascii(" ")) = TOKEN_SEPARADOR
fin funcion

Inicialmente el 'estado previo' debe ponerse en 1.
Se empieza recorriendo carácter a carácter en un bucle... se obtiene un token y debe considerarse el estado previo, para asignar el estado conforme a la tabla de estados, decrita más arriba.

Código [Seleccionar]


// NOTA: considera un 'break;' con cada caso... (tramitándolo como 'C').
Buleano = Funcion ParseExpresion(array bytes Expresion())
    entero Index, Size, signos, IxImprime
    TipoToken token, prevToken
    
    index = 0
    size = Expresion.Length
    IxImprime = 0
    prevToken = 1

    Hacer mientras (index < Size)        
        token = Tokens(Expresion(Index))

        Seleccionar caso de Token
            caso TOKEN_DIGITO
                Seleccionar caso de  prevToken 
                    caso TOKEN_SIGNO
                        Estado = 6
                    caso TOKEN_DIGITO
                        Estado = 1   
                    caso TOKEN_VARIABLE
                        Estado = 0  //Error...   las digitos nunca aparecen tras una variable:  5+'b2'35-6
                        Salir del bucle     
                    caso TOKEN_OPERADOR
                        Estado = 2   
                    caso TOKEN_OPPOTENCIA
                        Estado = 1
                Fin caso

            caso TOKEN_VARIABLE
                Seleccionar caso de  prevToken 
                   caso TOKEN_SIGNO
                        Estado = 6
                    caso TOKEN_DIGITO
                        Estado = 5    
                    caso TOKEN_VARIABLE
                        Estado = 0   //Error...  las variables solo son de 1 caracter (no se toleran identificadores más largos): 5+'bh'-6
                        Salir del bucle 
                    caso TOKEN_OPERADOR
                        Estado = 2
                    caso TOKEN_OPPOTENCIA
                        Estado = 0   //Error...  detras del oppotencia debe aparecer digitos, solamente: 5x'^z'-6
                        Salir del bucle    
                Fin caso

            caso TOKEN_OPERADOR   // Signo, aunque conta como operador tiene valor 6, se trata en signo.                
                Seleccionar caso de  prevToken 
                   caso TOKEN_SIGNO
                        Estado = 0   //Error...  detrás de un signo no puede aparecer ningún operador:  5'-*'3
                        Salir del bucle   
                    caso TOKEN_DIGITO
                        Estado = 1    
                    caso TOKEN_VARIABLE
                        Estado = 2   
                    caso TOKEN_OPERADOR
                        Estado = 0   //Error...  detrás de un operador no puede aparecer otro operador: 5'/*'3
                        Salir del bucle
                    caso TOKEN_OPPOTENCIA
                        Estado = 0   //Error...  detras del oppotencia debe aparecer digitos, solamente: 5x'^z'-6
                        Salir del bucle   
                Fin caso

            caso TOKEN_SIGNO
                Seleccionar caso de  prevToken 
                   caso TOKEN_SIGNO                    
                        si (signos < 2)
                            Estado = 6
                            signos +=1
                        sino
                            Estado = 0  // Error...   No puede haber más de 2 signos seguidos:  5'+-2'; 5'-+'4
                        fin si 
                    caso TOKEN_DIGITO
                        Estado = 1   
                    caso TOKEN_VARIABLE
                        Estado = 5 
                    caso TOKEN_OPERADOR
                        signos =-1 
                        Estado = 2
                    caso TOKEN_OPPOTENCIA
                        Estado = 0   //Error...  detras del oppotencia debe aparecer digitos, solamente: 5x'^z'-6
                        Salir del bucle   
                Fin caso

            caso TOKEN_OPPOTENCIA
                Seleccionar caso de  prevToken 
                   caso TOKEN_VARIABLE
                        Estado = 7
                   resto casos                         
                        Estado = 0   //Error...  antes del oppotencia solo puede aparecer una variable (como en: 5'x^'2)
                        Salir del bucle   
                Fin caso                       

            caso TOKEN_SEPARADOR
                token =  prevToken 

            caso TOKEN_DESCONOCIDO
                Estado = 0  // 'e' el valor asociado al error.
                Salir del bucle
        Fin caso
        
        Si (token <> TOKEN_SIGNO)
            Si (signos = -1)
                signos =1
            Sino
                signos = 0
            Fin si
        fin si

        // Imprimir aquí el valor. si por monomio es la 'produccion/regla "valor" (descrita más arriba), 
        // debes ir concatenando tokens, y cuando TokenPrevio = 1 ó 5 y token = 2 ó 6, se imprime, sino se concatena... 
        // algo más eficiente que concatenar es recordar el index previo, y al imprimir usarlo desde ahí hasta el actual (incluído).
        Si ((prevToken = 1) o (prevToken =5))
            Si ((Token = 2) o (Token = 6))
                imprimir desde Entrada(IxImprime) hasta Entrada(Index)
                IxImprime = (Index +1)
            fin si
        fin si       

        prevToken = token
        index +=1 
    Repetir 

    Si ((Estado = 1) o (estado = 5))
        Devolver  TRUE
    Sino
        Devolver FALSE
    Fin si
fin funcion

p.d.: Intercambiado valores en token= signo y previo= digito con el opuesto token= digito y previo= signo.

Reasignando otros valores de estado, se puede dejar más claro...
0 = desconocido, 1 = separador, 2 = operador, 3 = signo, 4 = digito, 5 = variable
Prevtoken conviene que se establezca inicialmente siempre al estado asignado a 'digito', para que pase a un estado válido si el primer carácter lo es.

NOTA: Al ver que luego has puesto otra expresión he recalado en la previa y he visto que no me percaté de que usas expresiones algebraicas... El pseudocódigo como estaba resolvía acertadamente las expresiones aritméticas, pero no las algebraicas... como esa que pusiste al inicio: "+3x^2-2x^1+9x^5-4+5x^3+1".
Es solo añadir alguna regla más y un estado distinto para el operador de potencia y luego añadir en la función 'ParseExpresion', los casos para dicho nuevo estado. Hago los cambios para que quede correctamente.
También resolverá correctamente un término suelto como 3x^0+5 si se pone como 3x+5

K-YreX · 18 Mayo 2020, 22:01 PM

Cita de: gomezjuan en 18 Mayo 2020, 18:05 PM
Muchas gracias, no entiendo muy bien a que te refieres con la primera linea la de validar monomio.
La estructura del monomio seria así?
Código [Seleccionar] Expandir
struct monomio { int coeficiente; int exponente; };
Y como puedo guardar los monomios en la estructura?

La primera línea era solo para definir una función llamada validarMonomio() que recibe como parámetro un string y devuelve un Monomio. El prototipo de la función sería:

Código (cpp) [Seleccionar]

Monomio validarMonomio(string monomio);

Para usar la struct Monomio:

Código (cpp) [Seleccionar]


struct Monomio {
  int coeficiente;
  int exponente;
}; 

int main(){
  Monomio mon;
  int coeficiente = 2, exponente = 5;
  mon.coeficiente = coeficiente;
  mon.exponente = exponente;
}

También puedes crear constructores, gets()/sets(),... Incluso crear una class para hacer los atributos privados y manejar los objetos a partir de los métodos.

Test Foro de elhacker.net SMF 2.1

Dividir polinomio en monomios C++

gomezjuan

K-YreX

gomezjuan

gomezjuan

Serapis

K-YreX