import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.Vector;
/**
* Dieser Parser kann mathematische Formeln, welche +,-,*,/ enthalten berechnen.
* Dabei kann der Parser Klammern mit einbeziehen, Konstanten (z.B: pi )
* an passender Stelle einfügen, und die Priorität von Operationen (* vor +) beachten.
*
* @author Benjamin Sigg
*/
public class Parser{
/**
* Dieses Objekt zeigt die Stellen auf, an denen eine öffnende Klammer zu
* finden ist
*/
private static final Object OPEN = new Object();
/**
* Dieses Objekt zeigt an, wo eine schliessende Klammer zu finden ist.
*/
private static final Object CLOSE = new Object();
/**
* Eine Liste aller Operationen, welche benutzt werden können.
*/
private List operations = new Vector();
/**
* Eine Liste aller Funktionen, welche benutzt werden können.
*/
private List functions = new Vector();
/**
* Eine Schlüssel-Wert -Datenstruktur, welche alle Konstanten aufführt.
*/
private Map constants = new Hashtable();
/**
* Defaultkonstruktor: füllt die Liste der Operationen und die
* Map der Konstanten mit +,-,*,/ bzw. "e" und "pi".
*/
public Parser(){
// Die Operationen hinzufügen
operations.add( new Operation(){
public int getPriority() {
return 1;
}
public String getSymbol() {
return "+";
}
public boolean asPrefix() {
return true;
}
public double calculate( double a, double b ) {
return a+b;
}
public String toString() {
return getSymbol();
}
});
operations.add( new Operation(){
public int getPriority() {
return 1;
}
public String getSymbol() {
return "-";
}
public boolean asPrefix() {
return true;
}
public double calculate( double a, double b ) {
return a-b;
}
public String toString() {
return getSymbol();
}
});
operations.add( new Operation(){
public int getPriority() {
return 2;
}
public String getSymbol() {
return "*";
}
public boolean asPrefix() {
return false;
}
public double calculate( double a, double b ) {
return a*b;
}
public String toString() {
return getSymbol();
}
});
operations.add( new Operation(){
public int getPriority() {
return 2;
}
public String getSymbol() {
return "/";
}
public boolean asPrefix() {
return false;
}
public double calculate( double a, double b ) {
return a/b;
}
public String toString() {
return getSymbol();
}
});
//entspricht Quadrat (pow) - in ProE als ^ geschrieben
operations.add( new Operation(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "^";
}
public boolean asPrefix() {
return false;
}
public double calculate( double a, double b ) {
return Math.pow(a, b);
}
public String toString() {
return getSymbol();
}
});
//Funktionen hinzufügen
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "sqrt";
}
public double calculate( double a) {
return Math.sqrt(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "exp";
}
public double calculate( double a) {
return Math.exp(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "ceil";
}
public double calculate( double a) {
return Math.ceil(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "floor";
}
public double calculate( double a) {
return Math.floor(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "log";
}
public double calculate( double a) {
return Math.log10(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "ln";
}
public double calculate( double a) {
return Math.log(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "sin";
}
public double calculate( double a) {
//erst in Radianswert umrechnen, dann sin-Fkt. anwenden; analog ProE-Rechnung
double angleInRadians = Math.toRadians(a);
return Math.sin(angleInRadians);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "sinh";
}
public double calculate( double a) {
return Math.sinh(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "cos";
}
public double calculate( double a) {
//erst in Radianswert umrechnen, dann sin-Fkt. anwenden; analog ProE-Rechnung
double angleInRadians = Math.toRadians(a);
return Math.cos(angleInRadians);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "cosh";
}
public double calculate( double a) {
return Math.cosh(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "tan";
}
public double calculate( double a) {
//erst in Radianswert umrechnen, dann sin-Fkt. anwenden; analog ProE-Rechnung
double angleInRadians = Math.toRadians(a);
return Math.tan(angleInRadians);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "tanh";
}
public double calculate( double a) {
return Math.tanh(a);
}
});
functions.add( new Function(){
public int getPriority() {
return 3;
}
public String getSymbol() {
return "abs";
}
public double calculate( double a) {
return Math.abs(a);
}
});
// Die Konstanten hinzufügen
constants.put( (Object)"e", new Double(Math.E) );
constants.put( (Object)"pi", new Double(Math.PI) );
}
/**
* Parst eine mathematische Formel.
* @param formula Die Formel
* @return Der Wert dieser Formel
* @throws IllegalArgumentException Sollte der übergebene String gar keine Formel sein.
*/
public double parse( String formula ){
// Es ist unpraktisch die Formel als String zu behandeln, deshalb
// wird sie zuerst in Operationen, Doubles sowie die Konstanten
// OPEN und CLOSE umgewandelt
List parts = split( formula );
/* Die Formel parsen, das Ergebnis wird direkt in die Liste "parts"
geschrieben.
Beginnt die Formel mit einem "(", wird vielleicht nicht die ganze
Formel geparst, deshalb wird der Parse-Algorithmus solange aufgerufen
bis nur noch ein Element übrig ist.
Um sicherzugehen, dass der Algorithmus beendet, wird verlangt, dass
bei jedem Schritt wenigstens ein Element aus der parts-Liste
entfernt wird (lieber eine Exception als eine Endlosschleife...)
*/
int size = parts.size();
while( size > 1 ){
parse( parts, 0 );
if( parts.size() >= size ){
throw new IllegalArgumentException(
"Die Formel wird nicht vollständig geparst, evtl. wurde eine Operation vergessen?" );
}
size = parts.size();
}
if( size != 1 || !(parts.get( 0 ) instanceof Double))
throw new IllegalArgumentException( "Diese Formel stimmt nicht" );
return (Double)parts.get( 0 );
}
/**
* Parst den Teil einer Formel, der zwischen 2 Klammern steht. Dabei
* kann es innerhalb dieses Teiles weitere Klammern haben.<br>
* Es ist auch möglich die gesammte Formel zu übergeben, der Algorithmus
* arbeitet gleich, nur werden zwei "imaginäre Klammern" um die Formel
* gepackt.
* @param formula Die Formel
* @param offset Der Index des ersten Zeichens der Klammer. Ist dies
* das öffnende Klammerzeichen muss auch ein schliessendes Klammerzeichen
* gefunden werden. Ist dies ein anderes Element, darf sich keine schliessende
* Klammer auf derselben Ebene befinden.
*/
private void parse( List formula, int offset ){
// Das Ende der Klammer suchen. Gleichzeitig Klammern innerhalb
// Der Teilformel berechnen.
int end = offset+1;
while( end < formula.size() && formula.get( end ) != CLOSE ){
if( formula.get( end ) == OPEN )
parse( formula, end );
end++;
}
// open gibt an, ob diese Formel echte Klammern benutzt.
// (open=false bedeutet, dass imaginäre Klammern benutzt werden).
boolean open = formula.get( offset ) == OPEN;
if( end == formula.size() && open )
throw new IllegalArgumentException( "Schliessende Klammer fehlt" );
if( end != formula.size() && !open )
throw new IllegalArgumentException( "Schliessende Klammer zuviel" );
if( open ){
formula.remove( end-- );
formula.remove( offset );
}
// Die Formel, nun ohne Klammern, parsen
parse( formula, offset, end );
}
/**
* Parst alle Elemente in der Formel von offset bis end.
* @param formula Die Formel
* @param offset Der Beginn der Teilformel (inklusive).
* @param end Das Ende der Teilformel (exklusive).
*/
private void parse( List formula, int offset, int end ){
// Zuerst werden alle Operationen welche als Präfixe dienen
// gesucht, und berechnet.
for( int i = end-2; i >= offset; i-- ){
if( formula.get( i ) instanceof Operation ){
Operation operation = (Operation)formula.get( i );
if( operation.asPrefix() ){
if( (formula.get( i+1 ) instanceof Double) &&
(i == offset || !(formula.get( i-1 ) instanceof Double) ) ){
double value = operation.calculate( 0, (Double)formula.get( i+1 ) );
formula.remove( i+1 );
formula.set( i, value );
end--;
}
}
}
else if( formula.get( i ) instanceof Function ){
if( formula.get( i+1 ) instanceof Double) {
Function function = (Function)formula.get( i );
double value = function.calculate((Double)formula.get( i+1 ) );
formula.remove( i+1 );
formula.set( i, value );
end--;
}
}
}
/*
Nun werden die normalen Operationen gesucht.
Es wird jeweils die Operation mit der höchsten Priorität, welche
am weitesten links liegt, berechnet.
*/
loop: while( end - offset > 1 ){
int index = -1;
int priority = -1;
for( int i = offset; i < end; i++ ){
Object element = formula.get( i );
if( element instanceof Operation ){
Operation operation = (Operation)element;
if( operation.getPriority() > priority ){
index = i;
priority = operation.getPriority();
}
}
}
if( index == -1 )
throw new IllegalArgumentException( "Zuwenig Operationen in der Formel" );
if( index == offset )
throw new IllegalArgumentException( "Operation die nicht Präfix hat links keine Argumente" );
if( index+1 == end )
throw new IllegalArgumentException( "Operation hat rechts keine weiteren Elemente" );
if( !(formula.get( index+1 ) instanceof Double && formula.get( index-1 ) instanceof Double ))
throw new IllegalArgumentException(
"Operationen sind Nachbarn, es muss aber ein Wert zwischen zwei Operationen stehen" );
double value = ((Operation)formula.get( index )).calculate(
(Double)formula.get( index-1 ),
(Double)formula.get( index+1 ) );
formula.remove( index+1 );
formula.remove( index );
formula.set( index-1, value );
end -= 2;
}
}
/**
* Wandelt die Formel welche als Text vorliegt in eine Liste von
* Operationen, Doubles sowie OPEN und CLOSE um.
* @param formula Die Formel
* @return Die Teile der Formel
*/
private List split( String formula ){
int offset = 0; // Index des Chars, der zurzeit betrachtet wird.
int length = formula.length();
List parts = new ArrayList();
while( offset < length ){
char current = formula.charAt( offset );
// Tabulator, Leerzeichen etc. interessieren nicht
if( !Character.isWhitespace( current )){
if( current == '(' ){
parts.add( OPEN );
offset++;
}
else if( current == ')' ){
parts.add( CLOSE );
offset++;
}
else if( Character.isDigit( current ) || current == '.' ){
// Es folgt nun eine Zahl, welche ausgelesen werden muss
int end = offset+1;
boolean pointSeen = current == '.';
while( end < length ){
char next = formula.charAt( end );
if( Character.isDigit( next ))
end++;
else if( next == '.' && !pointSeen ){
pointSeen = true;
end++;
}
else
break;
}
parts.add( Double.parseDouble( formula.substring( offset, end ) ) );
offset = end;
}
else{
// Eine Operation oder eine Konstante wird ausgelesen
// Es wird diejenige Operation/Konstante gesucht, welche den
// längsten Namen hat, und noch in die Formel passt.
int bestLength = 0;
Object best = null;
// Alle Operationen prüfen
for( Operation operation : operations ){
String sign = operation.getSymbol();
if( formula.startsWith( sign, offset )){
if( sign.length() > bestLength ){
bestLength = sign.length();
best = operation;
}
}
}
//Alle Funktionen prüfen
for( Function function : functions ){
String sign = function.getSymbol();
if( formula.startsWith( sign, offset )){
if( sign.length() > bestLength ){
bestLength = sign.length();
best = function;
}
}
}
// Alle Konstanten prüfen
for( String key : constants.keySet() ){
if( formula.startsWith( key, offset )){
if( key.length() > bestLength ){
bestLength = key.length();
best = constants.get( key );
}
}
}
if( best == null )
throw new IllegalArgumentException( "An dieser Formel stimmt was nicht" );
offset += bestLength;
parts.add( best );
}
}
else
offset++;
}
return parts;
}
}
!
