Para Programadores II
Interpretar y evaluar una expresión aritmética
En la segunda entrega de lo que probablemente se convierta en otro blog, quiero dejar la experiencia vivida al toparme con un problema, que inicialmente era secundario, al intentar interpretar y evaluar una expresión aritmética con un algoritmo.
Una expresión aritmética no es mas que "el conjunto de operandos y operaciones que resultan en un número", suena a ciencia de alto calibre, pero en realidad son operaciones que hacemos diariamente:
17*2 + 12 + 5*5 -3
Este es otro caso donde, para una persona, es muy sencillo de entender y evaluar, pero transmitir a un algoritmo que se debe hacer y como hacerlo, resulta un poco mas complicado. En específico, el problema que se presentó, resultó ser la evaluación de operaciones como:
(15 + (145 - N*2)*T)/100
Operaciones donde hay:
- Operandos numéricos
- Operandos no numéricos
- Operaciones agrupadas con paréntesis
- Operaciones aritméticas de suma, resta, multiplicación y división
Las premisas:
- La operación no tiene límite de operandos ni operadores
- Todos los operandos no numéricos deben evaluarse a números, es decir, las letras tienen un valor que puede encontrarse con algún método
- Solo se evaluarán las operaciones de suma, resta, multiplicación, división y agrupación con paréntesis
Lo interesante de este problema, es cómo hacer que un algoritmo pueda calcular efectivamente una expresión de este tipo sabiendo que:
- Las operaciones dentro de los paréntesis, deben resolverse primero
- Las operaciones con multiplicación y división, tienen precedencia sobre suma y resta
- Las operaciones de igual precedencia deben resolverse de izquierda a derecha
Investigando un poco, encontré y aprendí que la notación usada normalmente en estar expresiones se llama "infija" (léase Notación de Infijo), que para interpretar por un algoritmo, si bien es posible, es bastante complicada. Básicamente la notación infija permite colocar el operador en medio de los operandos, y para agrupar utiliza paréntesis.
Existen otras dos formas de expresar una operación aritmética, la "prefija" donde el operador se coloca antes de los operandos y la "postfija" donde el operador se coloca después de los operandos. Así que una misma operación puede expresarse de 3 maneras:
Infija:
34 + 25
Prefija
+ 34 25
Postfija
34 25 +
Tanto la prefija como la postfija son mas fácilmente "programables", es decir, el algoritmo necesario para interpretar y evaluar la operación es mas simple y genérico que en la infija. No lo sabía al iniciar a encontrar como resolver el problema, pero resulta que la postfija también es llamada NPI, pero no en su versión vulgar-coloquial usada mucho en Venezuela y que no pretendo repetir, NPI es Notación Polaca Inversa, que resulta ser la utilizada en las calculadoras HP, y eso lo sé porque la usaba a diario con mi HP en mi época de estudios de ingeniería, por allá en los noventa. Así que eso decantó mi decisión a ese modelo, y es el que pretendo explicar.
Primero lo primero, hablando de infijo y postfijo, y antes de ver como evaluar en postfijo, es necesario entender que no es necesario evaluar una expresión en postfijo, pueden hacerlo en infijo, todo depende del problema que se les presente. Por ejemplo, si el problema es calcular sumas y restas, es muy simple el algoritmo, si son solo multiplicaciones y divisiones, también es sencillo el algoritmo, en estos casos el problema se resuelve aplicando las operaciones de izquierda a derecha, tomando primer operando, operador, segundo operando, evaluar, y repetir hasta que no hayan mas operadores.
El caso se complica cuando las operaciones no pueden llevarse a cabo en un solo sentido, por ejemplo:
3*5 + 6
Esa expresión es fácil de evaluar: primer operando, operador, segundo operando, evaluar, siguiente operador, siguiente operando, evaluar... Pero si la cambiamos un poco:
6 + 3*5
Esa operación no se evalúa tan fácilmente, dado que antes de la operación de suma, debemos evaluar la multiplicación. Por ello, esa expresión debemos convertirla a algo que podamos evaluar con facilidad, y para ello son las expresiones infija y postfija.
Para resolver esa expresión, y cualquier otra expresión aritmética, debemos transformar de infijo a prefijo o postfijo, yo tomaré el camino de postfijo por ser el mas utilizado y por sentimentalismo (me recuerda mi calculadora HP), además que me parece mas elegante. Transformar de infijo a postfijo, es:
6 + 3*5 transformarlo en 6 3 5 * +
Así, al leer la expresión en postfijo se leería: toma operando 3, toma operando 5, multiplica, toma operando 6, suma con resultado anterior. La ventaja del postfijo (o prefijo) es que las operaciones siempre se llevan a cabo leyendo la expresión de izquierda a derecha, donde se tienen siempre dos operandos y luego una operación. Otra ventaja es que desaparecen los paréntesis de agrupación en la conversión, ya no se requiere hacer agrupaciones porque las operaciones se realizan siempre de izquierda a derecha.
Ahora, para transformar una expresión infija a postfija, se realiza el siguiente algoritmo:
Primer paso: es necesario separar cada elemento
Se que suena trivial y tonto, pero es necesario conocer que elementos componen la expresión. Tomemos como ejemplo la siguiente expresión:
45 + (54*6 -9)*5 - 34
Los elementos son:'45', '+', '(', '54', '*', '6', '-', '9', ')', '*', '5', '-' y '34'
Tenemos en esa expresión 13 elementos diferentes
Segundo paso: crear una pila (LIFO) y una cola (FIFO), en este ejemplo, las llamaremos pilaAnalisis y colaSolucion, con estos tres componentes, ejecutamos nuestro algoritmo.
Tercer paso: convertir infijo en postfijo:
1. Si el elemento es '(', agrego a la pilaAnalisis
2. Si el elemento es ')', tomo todos los elementos de pilaAnalisis y los paso a colaSolucion hasta encontrar '('
3. Si el elemento es un número, lo agrego a colaSolucion
4. Si el elemento es '*', '+', '-' o '/', realizo una de estas acciones:
a. Si pilaAnalisis esta vacía, agrego a pilaAnalisis
b. Si el elemento en el tope de pilaAnalisis es '+', '-' o '(', agrego a pilaAnalisis
c. Si el elemento en el tope de pilaAnalisis es '*' o '/', muevo todos los '*' y '/' de pilaAnalisis a colaSolucion y agrego el elemento a la pilaAnalisis
5. Si ya no tengo mas elementos, pero pilaAnalisis no esta vacía, muevo todos los elementos de pilaAnalisis a colaSolucion
Al terminar, en colaSolución tendremos nuestra expresión en notación postfija:
'45', '54', '6', '*', '9', '-', '5', '*', '34', '-', '+'
Ahora solo resta evaluar la expresión postfija, usamos una pilaResultado para las operaciones, leyendo pilaResultado de izquierda a derecha:
1. Si el elemento es un número, guardo en pilaResultado
2. Si el elemento es un operando, tomo dos elementos consecutivos de pilaResultado, el primero va a la izquierda de la operación, el segundo a la derecha, y realizo la operación. El resultado lo guardo en pilaResultado.
3. Si ya no hay mas elementos en colaSolucion, el resultado esta en pilaResultado.
Ejecutando los pasos 1 y 2 con nuestro ejemplo, sería:
45 -> guardo en pilaResultado
54 -> guardo en pilaResultado
6 -> guardo en pilaResultado
* -> tomo de pilaResultado 6 a la izquierda y 54 a la derecha, opero 54 * 6 = 324. Guardo en pilaResultado
9 -> guardo en pilaResultado
- -> tomo de pilaResultado 9 a la izquierda y 324 a la derecha, opero 324 - 9 = 315. Guardo en pilaResultado
5 -> guardo en pilaResultado
* -> tomo 5 y 315 de pilaResultado, opero 315 * 5 = 1.575. Guardo en pilaResultado
34 -> guardo en pilaResultado
- -> tomo 34 y 1575 de pilaResultado, opero 1575 - 34 = 1.541. Guardo en pilaResultado
+ -> tomo 1.541 y 45 de pilaResultado, opero 45 + 1.541 = 1.586. Guardo en pilaResultado
Así el resultado de la expresión es 1.586.
Les dejo el código en Java:
Stack
LinkedList
LinkedList
String ejemplo = "45 + (54*6 -9)*5 - 34";
//Separando Elementos y llevandolos a colaElementos
char[] characteres = ejemplo.toCharArray();
int ini = -1;
int fin = -1;
for (int i = 0; i < characteres.length; i++) {
switch (characteres[i]) {
case '(':
case ')':
case '+':
case '-':
case '*':
case '/':
if (fin != -1) {
fin++;
}
if (ini != -1) {
colaElementos.add(ejemplo.substring(ini, fin).trim());
ini = -1;
fin = -1;
}
colaElementos.add("" + characteres[i]);
break;
case ' ':
fin++;
break;
default:
if (ini == -1) {
ini = i;
fin = i;
} else {
fin++;
}
break;
}
}
if (ini != -1) {
colaElementos.add(ejemplo.substring(ini).trim());
}
//Cambiando de INFIJO a POSTFIJO
Iterator
String elemento = null;
while (it.hasNext()) {
elemento = it.next();
switch (elemento) {
case "(":
pilaAnalisis.push(elemento);
break;
case "*":
case "/":
case "+":
case "-":
if (pilaAnalisis.isEmpty()) {
pilaAnalisis.push(elemento);
} else if (pilaAnalisis.peek().equals("+") || pilaAnalisis.peek().equals("-") || pilaAnalisis.peek().equals("(")) {
pilaAnalisis.push(elemento);
} else if (pilaAnalisis.peek().equals("*") || pilaAnalisis.peek().equals("/")) {
while (!pilaAnalisis.isEmpty() && (pilaAnalisis.peek().equals("*") || pilaAnalisis.peek().equals("/"))) {
colaSolucion.add(pilaAnalisis.peek());
pilaAnalisis.pop();
}
pilaAnalisis.push(elemento);
}
break;
case ")":
while (!pilaAnalisis.peek().equals("(")) {
colaSolucion.add(pilaAnalisis.peek());
pilaAnalisis.pop();
}
pilaAnalisis.pop();
break;
default:
colaSolucion.add(elemento);
break;
}
}
while (!pilaAnalisis.isEmpty()) {
colaSolucion.add(pilaAnalisis.peek());
pilaAnalisis.pop();
}
//Evaluo la expresion
Stack
for (int i = 0; i < colaSolucion.size(); i++) {
try {
pilaResultado.push(Double.valueOf(colaSolucion.get(i)));
} catch (Exception e) {
String op = colaSolucion.get(i);
Double iz = pilaResultado.peek();
pilaResultado.pop();
Double de = pilaResultado.peek();
pilaResultado.pop();
switch (op) {
case "+":
pilaResultado.push(de + iz);
break;
case "-":
pilaResultado.push(de - iz);
break;
case "*":
pilaResultado.push(de * iz);
break;
case "/":
pilaResultado.push(de / iz);
break;
}
}
}
}
Espero les sea de utilidad.
Gracias por leerme
Comentarios