Sitzung 2

Aufgabe 3 Allgemeine Bäume

   program baumToArray;

const D=3;

type 
   elem= String; 
   refNode = ^node;
   node= record key:elem;
   leftmostChild:refNode;
   rigthSibling:refNode;
   end; 
   tRefFeld= ^tFeld;
   tFeld= record key:elem;
   sons: array[1..D] of tRefFeld;
   end; 
   
   var wurzel,p,q,r:^node;
   feld: tRefFeld;

procedure alle_schluessel(p: refNode);
   begin
   if (p <> nil) then
   begin
   writeln(p^.key);
   alle_schluessel(p^.leftmostChild);
   alle_schluessel(p^.rigthSibling);
   end;

end;

function max_grad(p: refNode; grad:integer): integer;
   var max1,max2,max3:integer;
   begin
   if (p = nil) then max_grad := 0
   else
   begin
   max1:=max_grad(p^.rigthSibling, grad+1);
   max2:=max_grad(p^.leftmostChild,1);
   if (max1 > max2) then max3 := max1
   else max3 := max2;
   if (grad > max3) then max_grad := grad
   else max_grad := max3;
   end
   
   end;

function umwandlung(p: refNode; feld: tRefFeld; stelle:integer): tRefFeld;
   var i:integer;
   f:tRefFeld;
   begin
   if (p <> nil) then 
   begin
   writeln(p^.key);
   new(f);
   for i:=1 to D do
   f^.sons[i]:= nil;
   f^.key := p^.key;
   if (feld<>nil) then 
   begin
   feld^.sons[stelle]:=f;
   end;
   umwandlung := umwandlung(p^.leftmostChild,f,1);
   umwandlung := umwandlung(p^.rigthSibling, feld, stelle+1); 
   umwandlung := f;
   end;
   end;

procedure durchlauf(feld: tRefFeld);
   var i:integer;
   begin
   if (feld<>nil) then
   begin
   writeln(feld^.key);
   for i:=1 to D do
   begin
   if (feld^.sons[i]=nil) then
   {writeln('-')}
   else
   begin
   {writeln(feld^.sons[i]^.key);}
   durchlauf(feld^.sons[i]);
   end; 
   end
   end;
   end;
   
   BEGIN
   new(wurzel);
   wurzel^.key := 'Heinrich'; 
   
   new(p);
   p^.key := 'Barbara'; 
   
   wurzel^.leftmostChild := p;
   
   new(q);
   q^.key := 'Clara'; 
   p^.rigthSibling := q;
   
   new(r);
   r^.key := 'A';
   p^.leftmostChild := r;
   
   new(p);
   p^.key := 'B';
   r^.rigthSibling := p;
   
   new(r);
   r^.key := 'Dora';
   q^.rigthSibling := r;
   
   new(p);
   p^.key := 'D';
   r^.leftmostChild := p;
   
   new(q);
   q^.key := 'E';
   p^.rigthSibling := q;
   
   new(p);
   p^.key := 'F';
   q^.rigthSibling := p;
   
   alle_schluessel(wurzel);
   
   writeln();
   
   writeln(max_grad(wurzel,1));
   writeln();
   
   feld:=umwandlung(wurzel,nil,1);
   writeln();
   
   durchlauf(feld);
   END.

Aufgabe 4 Postfix

In dieser Version testen die Operatoren selber, ob sie zuständig sind. Im Test vergleichen sie die Operation mit ihrem Typ.

Der Operator Const testet, ob der übergebene Wert eine Zahl vom Typ double ist.

Postfix

import java.util.*;

class Postfix {
   
   Operator[] ops;
   
   Postfix(Operator[] operators){
   ops = operators;
   }
   
   double eval(String expr ){
   Stack  stack = new Stack();
   String teil="";
   double erg=0.0;
   StringTokenizer st = new StringTokenizer(expr," ");
   while (st.hasMoreTokens()) {
   teil= st.nextToken();
   for (int i=0;i<ops.length ;i++ ) {
   if (ops[i].test(teil)) {
   erg=ops[i].rechnen(stack,teil);
   } // end of if
   } // end of for
   };
   return erg;
   }
   
   public static void main(String[] args){
   String eingabe="3.2 4 + 3 *";
   Operator[] ops = {new Const(),new Plus(),
   new Mult(),new Minus(),new Div()};
   Postfix p= new Postfix(ops);
   System.out.println(p.eval(eingabe));
   }
   }

Operator

import java.util.*;

abstract class Operator{
   String typ;
   abstract double rechnen(Stack s, String teil);
   abstract boolean test(String ausdruck);
   }
 

Const

import java.util.*;

class Const extends Operator{
   
   double rechnen(Stack s, String teil){
   //System.out.println("c");
   s.push(teil);
   return Double.parseDouble(teil);
   }
   Const(){
   typ="c";
   }
   boolean test(String ausdruck){
   try {
   double value = Double.parseDouble ( ausdruck ) ;
   return true;
   } catch ( Exception e ) {
   return false;
   }
   };
   }
 

Plus

import java.util.*;

class Plus extends Operator{
   
   double rechnen(Stack s, String teil){
   //System.out.println("+");
   double op1= Double.parseDouble((String) s.pop()) ;
   double op2= Double.parseDouble((String) s.pop());
   double erg= op1+op2;
   s.push(""+ erg);
   return erg;
   }
   Plus(){
   typ="+";
   }
   boolean test(String ausdruck){
   if (ausdruck.equals(typ))
   return true;
   else
   return false;
   };
   }
 

Minus

import java.util.*;

class Minus extends Operator{
   
   double rechnen(Stack s, String teil){
   //System.out.println("+");
   double op1= Double.parseDouble((String) s.pop()) ;
   double op2= Double.parseDouble((String) s.pop());
   double erg= op2-op1;
   s.push(""+ erg);
   return erg;
   }
   Minus(){
   typ="-";
   }
   boolean test(String ausdruck){
   if (ausdruck.equals(typ))
   return true;
   else
   return false;
   };
   }
 

Mult

import java.util.*;

class Mult extends Operator{
   
   double rechnen(Stack s, String teil){
   //System.out.println("+");
   double op1= Double.parseDouble((String) s.pop()) ;
   double op2= Double.parseDouble((String) s.pop());
   double erg= op1*op2;
   s.push(""+ erg);
   return erg;
   }
   Mult(){
   typ="*";
   }
   boolean test(String ausdruck){
   if (ausdruck.equals(typ))
   return true;
   else
   return false;
   };
   }
 

Div

import java.util.*;

class Div extends Operator{
   
   double rechnen(Stack s, String teil){
   //System.out.println("+");
   double op1= Double.parseDouble((String) s.pop()) ;
   double op2= Double.parseDouble((String) s.pop());
   double erg= op2/op1;
   s.push(""+ erg);
   return erg;
   }
   Div(){
   typ="/";
   }
   boolean test(String ausdruck){
   if (ausdruck.equals(typ))
   return true;
   else
   return false;
   };
   }