RedWing
Erfahrenes Mitglied
Hallo,
hier mal ein Bsp für einen Parser der die Bindung eines arithmethischen
Ausdrucks erkennt und das Ergebniss berechnet.
Dachte mir eignet sich mal ganz gutes Bsp für ein das Forum...
Also als erstes brauchen wir ein paar imports:
Danach brauchen wir ne geeignete DS um den Operatorbaum aufzubauen,
mit dessen Hilfe wir später den Ausdruck berechnen:
(Intressant ist hierbei die Methode getResult() die das Ergebniss
berechnet...)
Aber zuerst muessen wir den Syntaxbaum aufbauen welcher dann
auch gleich intern den Operatorbaum nach folgende Grammatik kreirt:
Und zum Schluss das Testprogramm:
Brauchbar oder nicht? Nur ein Produkt der Langeweile
Verbesserungsvorschläge sind natuerlich willkommen.
Viel Spass damit
RedWing
hier mal ein Bsp für einen Parser der die Bindung eines arithmethischen
Ausdrucks erkennt und das Ergebniss berechnet.
Dachte mir eignet sich mal ganz gutes Bsp für ein das Forum...
Also als erstes brauchen wir ein paar imports:
Code:
import java.util.Vector;
import java.util.StringTokenizer;
import java.lang.IllegalArgumentException;Danach brauchen wir ne geeignete DS um den Operatorbaum aufzubauen,
mit dessen Hilfe wir später den Ausdruck berechnen:
(Intressant ist hierbei die Methode getResult() die das Ergebniss
berechnet...)
Code:
/**
* the data structure which represents the operator tree
*/
class OpTree{
private OpTree right;
private OpTree left;
private String value;
public OpTree(String value){
right = null;
left = null;
this.value = value;
}
public void setLeftSon(OpTree left){
this.left = left;
}
public void setRightSon(OpTree right){
this.right = right;
}
/**
* generates the result from the created OpTree
* traverses the tree in postorder
*/
public int getResult(){
if(left == null && right == null){
int res = Integer.parseInt(value);
return res;
}
else{
if(value.equals("+"))
return left.getResult() + right.getResult();
else if(value.equals("-"))
return left.getResult() - right.getResult();
else if(value.equals("/"))
return left.getResult() / right.getResult();
else
return left.getResult() * right.getResult();
}
}
}Aber zuerst muessen wir den Syntaxbaum aufbauen welcher dann
auch gleich intern den Operatorbaum nach folgende Grammatik kreirt:
Code:
* expressiom ::= term | term '+' expression | term '-' expression
* term ::= factor | factor '*' term | factor '/' term
* factor ::= int | '(' expression ')'
Code:
class SyntaxTree{
private Vector<String> elements;
private OpTree root;
/**
* returns the postion of each closing bracket which belongs to a opening bracket
* if there is no closing bracket a IllegalArgumentException is thrown
*/
private int getClosingBracketPosition(Vector<String> tooperate, int beginIndex) throws IllegalArgumentException{
int number_opening_brackets = 0;
int number_closing_brackets = 0;
int ret = beginIndex;
while(ret < tooperate.size()){
if(tooperate.get(ret).equals("(")) number_opening_brackets++;
if(tooperate.get(ret).equals(")")) number_closing_brackets++;
if(number_opening_brackets == number_closing_brackets) break;
ret++;
}
if(number_opening_brackets != number_closing_brackets)
throw new IllegalArgumentException("There was a bracket missmatch");
return ret;
}
/**
* creates the non terminal expression according to the grammar rules
*/
private void expression(Vector<String> tooperate) throws IllegalArgumentException{
term(tooperate);
if(tooperate.size() > 0){
if(tooperate.get(0).equals("+") || tooperate.get(0).equals("-")){
OpTree oldRoot = root;
root = new OpTree(tooperate.get(0));
root.setLeftSon(oldRoot);
OpTree oldRoot2 = root;
tooperate.remove(0);
expression(tooperate);
oldRoot2.setRightSon(root);
root = oldRoot2;
}
}
}
/**
* creates the non terminal term according to the grammar rules
*/
private void term(Vector<String> tooperate) throws IllegalArgumentException{
factor(tooperate);
if(tooperate.size() > 0){
if(tooperate.get(0).equals("*") || tooperate.get(0).equals("/")){
OpTree oldRoot = root;
root = new OpTree(tooperate.get(0));
root.setLeftSon(oldRoot);
tooperate.remove(0);
OpTree oldRoot2 = root;
term(tooperate);
oldRoot2.setRightSon(root);
root = oldRoot2;
}
}
}
/**
* creates the non terminal factor according to the grammar rules
* if one input value which is expected as number is no number a llegalArgumentException is thrown
*/
private void factor(Vector<String> tooperate) throws IllegalArgumentException{
if(tooperate.size() > 0){
if(tooperate.get(0).equals("(")){
int begin_pos = 0;
int end_pos = getClosingBracketPosition(tooperate, begin_pos);
Vector<String> new_expression = new Vector<String>(tooperate.subList(begin_pos + 1, end_pos));
expression(new_expression);
for(int i = begin_pos; i <= end_pos; i++)
tooperate.remove(0);
}
else{
if((tooperate.get(0)).charAt(0) > '9' || (tooperate.get(0)).charAt(0) < '0')
throw new IllegalArgumentException("No number where a number was expected!");
root = new OpTree(tooperate.get(0));
tooperate.remove(0);
}
}
}
/**
* creates a new syntax tree which represent the given grammar
* @param expression the expression from which the syntax tree should be build
*/
public SyntaxTree(String expression) throws IllegalArgumentException{
StringTokenizer token = new StringTokenizer(expression, " ");
if(token.countTokens() % 2 == 0) throw new IllegalArgumentException("Unknown Syntax error occured!");
elements = new Vector<String>();
while(token.hasMoreTokens())
elements.add(token.nextToken());
}
/**
* computes the syntax tree and creates the OpTree
* @see OpTree
*/
void buildTree() throws IllegalArgumentException{
Vector<String> tooperate = new Vector<String>(elements);
expression(tooperate);
}
int getResult(){
if(root != null)
return root.getResult();
else
return 0;
}
}Und zum Schluss das Testprogramm:
Code:
class Parser{
public static void main(String[] args){
String expression = "3 * ( 15 - 6 / ( 2 + 1 ) )";
try{
SyntaxTree t = new SyntaxTree(expression);
t.buildTree();
System.out.println(t.getResult());
}catch(IllegalArgumentException e){
System.out.println(e.getMessage());
e.printStackTrace();
}
}
}Brauchbar oder nicht? Nur ein Produkt der Langeweile
Verbesserungsvorschläge sind natuerlich willkommen.
Viel Spass damit
RedWing
Zuletzt bearbeitet:
(z.B. beim Ausdruck "( 2 + 2 )" ). Durch den Lookup geht der Hauptvorteil dieser Parser dahin: linear mit der Eingabe zu sein (Der Parser geht zweimal drüber: einmal in getClosingBracketPosition(), einmal beim Parsen selbst).
