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
Autor
En línea
