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:
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:
+3x^2
-2x^1
+9x^5
-4
+5x^3
+1
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:
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.
Muchas gracias, no entiendo muy bien a que te refieres con la primera linea la de validar monomio.
La estructura del monomio seria así?
struct monomio {
int coeficiente;
int exponente;
};
Y como puedo guardar los monomios en la estructura?
He eliminado lo del signo ^ y ahora despues de la x tendria que ir un numero directamente o nada si el exponente es 1.
#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;
}
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.
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.
// 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
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í?
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:
Monomio validarMonomio(string monomio);
Para usar la struct Monomio:
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.