Como les mencione en un post previo, estoy leyendo el libro el arte de programar en Java, el primer ejercicio consiste en un analizador de expresiones algebraicas recursivo descendente, el mismo consiste en la posibilidad de tomar una cadena que contenga una expresión matemática, la misma puede contener valores en punto flotante, sumar, restar, dividir, multiplicar, sacar exponente (potencia), uso de paréntesis para priorizar una operación, etc.
A continuación clase a clase, con una pequeña explicación
Lo primero que definiremos es una suite de excepciones para reportar errores, no tiene mucha ciencia, hay una para la division entre cero, cuando no existe una expresión valida, error de sintaxis o cuando los paréntesis no se encuentran balanceados, veamos
package cap2;
/**
* Exception para reportar que hay al intentar dividir entre cero
*
* User: jsanca
* Date: 4/16/13
* Time: 1:30 AM
* @author jsanca
*/
public class DividedByZeroException extends RuntimeException {
public DividedByZeroException() {
}
public DividedByZeroException(String message) {
super(message);
}
public DividedByZeroException(String message, Throwable cause) {
super(message, cause);
}
public DividedByZeroException(Throwable cause) {
super(cause);
}
}
//////
package cap2;
/**
* Exception para reportar que no Hay expresion presente
*
* User: jsanca
* Date: 4/16/13
* Time: 1:30 AM
* @author jsanca
*/
public class NonExpressionDefinedException extends RuntimeException {
public NonExpressionDefinedException() {
}
public NonExpressionDefinedException(String message) {
super(message);
}
public NonExpressionDefinedException(String message, Throwable cause) {
super(message, cause);
}
public NonExpressionDefinedException(Throwable cause) {
super(cause);
}
}
////////
package cap2;
/**
* Exception para reportar que hay un error de sintaxis
*
* User: jsanca
* Date: 4/16/13
* Time: 1:30 AM
* @author jsanca
*/
public class SintaxErrorException extends RuntimeException {
public SintaxErrorException() {
}
public SintaxErrorException(String message) {
super(message);
}
public SintaxErrorException(String message, Throwable cause) {
super(message, cause);
}
public SintaxErrorException(Throwable cause) {
super(cause);
}
}
package cap2;
/**
* Exception para reportar que hay parentesis desbalanceados
*
* User: jsanca
* Date: 4/16/13
* Time: 1:30 AM
* @author jsanca
*/
public class UnbalanceParenthesesException extends RuntimeException {
public UnbalanceParenthesesException() {
}
public UnbalanceParenthesesException(String message) {
super(message);
}
public UnbalanceParenthesesException(String message, Throwable cause) {
super(message, cause);
}
public UnbalanceParenthesesException(Throwable cause) {
super(cause);
}
}
Seguidamente veremos el parser; el mismo contiene un constructor donde pasaras la formula a evaluar, seguidamente se normalizara (se eliminan los espacios). Lo siguiente que podrás ver, es el TokenType. Este enumera los tipos de tokens, delimilador (un operador), variables (no soportadas en este ejemplo), números, fin de ecuación, etc. Lo tercero son las variables de la clase, la expresión antes mencionada, el índice que se utilizara como veras mas adelante para recorrer la expresión índice a índice, el token (el numero, operador, etc, actual, en análisis) y el tipo de token como antes mencionamos. Seguimos con la función "getResult" única función publica con la que el usuario puede interactuar, lo primer que hace la función es pedir el primer token, si este es fin de ecuación disparamos un excepción pues no debería ser (en este caso una expresión vacía), seguidamente por recursividad llamamos a evalExp2 (ya veras que lo que hace el algoritmo es encadenas descendentemente del operador de menor prioridad al de mayor, es decir vamos de sumas y restas, hasta multiplicación, exponentes, etc), esta evalExp2 debes conceptualizarla como la evaluacion de una suma si esta existe, pero antes buscara funciones de mayor prioridad; evalExp3. EvalExp3 presenta un panorama similar, en este vemos como se evalúa las operaciones de multiplicar, division y modulo, sin no antes llamar antes a evalExp4. La versión 4, evalúa la potencia, el exponente; así mismo este llamara al evalExp5 que evalua los algún signo de un operador como + o - (positivo o negativo). Por ultimo evalExp6, evaluara paréntesis y valores atómicos, en nuestro caso solo números. En el caso de los paréntesis tomar en cuenta que cuando se encuentra un match, se vuelve a iniciar el proceso a través de un llamado recursivo a evalExp2, que evaluara la expresión dentro de los paréntesis. No estoy seguro si entendiste la dinámica del algoritmo, pero este se basa en llamar primero a la operación de menor prioridad hasta ir directamente a la de mayor prioridad (paréntesis y números, el eslabón final en la cadena de la ecuación). Lo ultimo que veras es el nexToken, este analizador resulta muy sencillo básicamente evalúa el carácter actual, en el caso de los delimitadores simplemente lo tome y suma uno mas para ir al siguiente índice en la llamada a nextToken consiguiente, en el caso de los números o variables (no soportadas en el ejemplo); se sacaran todos los digitos hasta encontrar otra cosa (un delimitador en este caso), esta función sera llamada a medida que se necesite analizar el siguiente token. Pues ahora al código:
package cap2;
import java.text.MessageFormat;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* Representa el parser para las expresiones
* * User: jsanca
* Date: 4/16/13
* Time: 12:29 AM
*
* @author jsanca
*/
public class Parser {
/**
* Constructor.
*
* @param expresion String
*/
public Parser(String expresion) {
this.expresion = this.normalizeExpresion(expresion);
}
// define los tipos de token
private enum TokenType {
NONE, DELIMITER, VARIABLE, NUMBER, EOE
}
private String expresion = null;
private int expresionIndex = 0;
private String token = null;
private TokenType tokenType = null;
private Set delimiters = new HashSet(Arrays.asList(new Character[]{'+', '-', '/', '*', '%', '^', '=', '(', ')'}));
private String normalizeExpresion(String expr) {
return expr.replaceAll("\\s*", "");
}
/**
* Gets the results
*
* @return double
*/
public double getResult() {
double result = 0;
this.expresionIndex = 0;
this.nextToken();
if (this.tokenType == TokenType.EOE) {
throw new NonExpressionDefinedException();
}
// evalua la expresion
result = this.evalExp2();
if (this.tokenType != TokenType.EOE) {
throw new SintaxErrorException();
}
return result;
} // getResult.
/**
* Suma o resta terminos
*
* @return double
*/
private double evalExp2() {
char operator;
double result;
double partialResult;
// llamado decendente a la operacion de multiplicar
result = this.evalExp3();
while ( (this.tokenType != TokenType.EOE) &&
((operator = this.token.charAt(0)) == '+' || operator == '-')) {
this.nextToken();
partialResult = evalExp3();
switch (operator) {
case '-':
result = result - partialResult;
break;
case '+':
result = result + partialResult;
break;
}
}
return result;
} // evalExp2.
/**
* Multiplica y divide
*
* @return double
*/
private double evalExp3() {
char operator;
double result;
double partialResult;
// llamado decendente a la operacion de exponente
result = this.evalExp4();
while ( (this.tokenType != TokenType.EOE) &&
((operator = this.token.charAt(0)) == '*' || operator == '/' || operator == '%')) {
this.nextToken();
partialResult = evalExp4();
switch (operator) {
case '*':
result = result * partialResult;
break;
case '/':
if (partialResult == 0.0) {
throw new DividedByZeroException();
}
result = result / partialResult;
break;
case '%':
if (partialResult == 0.0) {
throw new DividedByZeroException();
}
result = result % partialResult;
break;
}
}
return result;
} // evalExp3,
/**
* Evalua el exponente
*
* @return double
*/
private double evalExp4() {
double result;
double partialResult;
// llamado decendente a la operacion de signo (unitario)
result = this.evalExp5();
if ("^".equals(this.token)) {
this.nextToken();
partialResult = this.evalExp4();
if (partialResult == 0.0) { // x^0.0 = 1.0
result = 1.0; // caso trivial
} else {
result =
Math.pow(result, partialResult);
}
}
return result;
} // evalExp4.
/**
* Evalua el signo de un valor + 0 -
*
* @return
*/
private double evalExp5() {
double result;
String operator = "";
if ((this.tokenType == TokenType.DELIMITER) &&
"+".equals(this.token) || "-".equals(this.token)) {
operator = this.token;
this.nextToken();
}
// decendente parentesis
result = this.evalExp6();
if ("-".equals(operator)) {
result = -result;
}
return result;
} // evalExp5.
/**
* Evalua los parentesis.
*
* @return double
*/
private double evalExp6() {
double result;
if ("(".equals(this.token)) {
this.nextToken();
result = this.evalExp2();
if (!")".equals(this.token)) {
throw new UnbalanceParenthesesException();
}
this.nextToken();
} else {
result = this.getAtomicValue();
}
return result;
} // evalExp6.
/**
* Obtiene un valor numerico atomico
*
* @return double
*/
private double getAtomicValue() {
double result = 0.0;
if (this.tokenType == TokenType.NUMBER) {
result = Double.parseDouble(this.token);
this.nextToken();
} else {
throw new SintaxErrorException();
}
return result;
} // getAtomicValue.
/**
* Obtiene el siguiente token
*/
protected void nextToken() {
this.tokenType = TokenType.NONE;
this.token = "";
if (!isTheEndOfExpresion()) {
// Si es un operador
if (this.isDelimiter(this.expresion.charAt(this.expresionIndex))) {
this.parseDelimiter();
} else if (this.isVariable(this.expresion.charAt(this.expresionIndex))) { // si es una variable.
this.parseVariable();
} else if (this.isNumber(this.expresion.charAt(this.expresionIndex))) { // si es un numero.
this.parseNumber();
} else {
this.tokenType = TokenType.EOE; // caracter desconocido.
}
} else {
this.tokenType = TokenType.EOE;
}
System.out.println(MessageFormat.format("token {0} and type {1}", this.token, this.tokenType));
} // nextToken.
private void parseFactor() {
while (!this.isTheEndOfExpresion() && !this.isDelimiter(this.expresion.charAt(this.expresionIndex))) {
this.token += this.expresion.charAt(this.expresionIndex);
this.expresionIndex++;
}
}
protected void parseNumber() {
this.parseFactor();
this.tokenType = TokenType.NUMBER;
}
protected void parseVariable() {
this.parseFactor();
this.tokenType = TokenType.VARIABLE;
}
protected void parseDelimiter() {
this.token +=
this.expresion.charAt(this.expresionIndex);
this.expresionIndex++;
this.tokenType = TokenType.DELIMITER;
}
private boolean isNumber(final char c) {
return Character.isDigit(c);
} // isNumber,
private boolean isDelimiter(final char c) {
return this.delimiters.contains(c);
} // isDelimiter.
private boolean isVariable(final char c) {
return Character.isLetter(c);
} // isVariable.
private boolean isTheEndOfExpresion() {
return (this.expresionIndex >= this.expresion.length());
} // isTheEndOfExpresion.
} // E:O:F:Parser.
Comentarios