Defunct Old Assignment

Programmet skall läsa uttrycken och bygga upp en internrepresentation som lämpar sig för evaluering. Ni skall använda en trädstruktur där operatorer och funktioner lagras i de interna noderna och konstanter och variabler i löven.

Det matematiska uttrycket

sin x + 5*a - 3*(u+1) = z = t

skall alltså representeras av trädet nedan.

Gemensamt för alla noder är (bl.a.) att de skall kunna evalueras men evaluering beter sig olika beroende på vad det är för typ av nod (konstant, variabel, addition, …).

Eftersom noderna ska kunna vara av olika typer (operatorer, funktioner, variabler, konstanter, …) är det lämpligt att implementera dem i en klasshierarki med en generell basklass som skulle kunna kallas SymbolicExpression. Av layout-skäl kan det dock vara bra att använda ett kortare namn som Sexpr eftersom detta namn kommer att vara oerhört frekvent i koden.

Gör egna klasser för varje operation och funktion (Assignment, Addition, Subtraction, Sin, …) samt en klass för variabler och en för konstanter.

Det finns tre tydligt urskiljbara grupper av noder: de med två operander (binära operatorer), de med en en operand (funktioner, unärt minus) och de utan operander (konstanter, variabler). Det är inte bara antalet operander som är gemensamt för varje grupp utan även vissa metoder. Sålunda kan bl.a. toString()-metoderna skrivas på samma sätt t.ex. för alla binära operatorer.

Således skall man samla binära operatorer under klassen Binary och unära operatorer (inklusive funktioner) under klassen Unary. Av ”symmetriskäl” är det lämpligt att samla konstanter och variabler under klassen Atom även om det nog inte finns så mycket som kan utnyttjas gemensamt mellan dessa två grupper.

Det leder till följande design (ytterligare metoder kommer behöva tillföras):

OBS! Konstruktorer är inte angivna i figuren.

Det är lämpligt att placera Sexpr och dess subklasser ett eget paket (symbolic). Basklassen Sexpr bör således ha följande utseende.

package symbolic;
import ...;

public abstract class Sexpr {

   public Sexpr() {
   }
   ...
}

Ett exempel på en klass på mellannivån i hierarkin är Unary:

package symbolic;

public abstract class Unary extends Sexpr {

   private Sexpr argument; // bör denna vara private?

   public Unary(Sexpr a) {
      argument = a;
   }

   public String toString() {...}
   public priority() {...}
}

Uttryck byggs av en parser som implementerar recursive descent, liksom den från screencasten i ämnet. Den modifieras nu så att varje metod som förut returnerade ett tal (en double) nu returnerar en referens till en skapad nod (alltså en Sexpr). Du hittar originalkoden på samma ställe som screencasten.

Exempel: Parsermetoden expression() får följande uteseende (med en StreamTokenizer st):

public Sexpr expression() {
   Sexpr sum = term();
   while (st.ttype=='+' || st.ttype=='-') {
      int operation = st.ttype;
      st.nextToken();
      if (operation=='+') {
          sum = new Addition(sum, term());
      } else {
          sum = new Subtraction(sum, term());
      }
   }
   return sum;
}

Där man tidigare utförde en addition eller en subtraktion skapar man nu en additionsnod respektive en subtraktionsnod.

Som vanligt använder man toString()-metoder för att skapa en textrepresentation av de lagrade uttrycken. Dessa metoder gör i princip en inordertraversering av trädet. Ett problem är att i trädet är evalueringsordningen given av strukturen men i den externa bestäms den av prioriteter och parenteser. Således måste toString()-metoderna, vid behov, sätta ut parenteser för att uttrycken skall bli korrekta. Man kan göra det lätt för sig genom att alltid sätta ut parenteser men det blir inte så vackert.

Eftersom parenteshanteringen kan göras på samma sätt för alla unära respektive alla binära operatorer så placeras toString()-metoderna i klasserna Unary respektive Binary. Själva operatornamnet erhålles av getName().

Så här ser klassen Unary ut med en naiv implementation (d.v.s. en som sätter ut parenteser var sig det behövs eller ej) av toString():

public abstract class Unary extends Sexpr {
   Sexpr argument;

   public String toString() {
      return getName() + "(" + argument.toString() + ")";
   }
   ...
}

Eftersom värden nu är symboliska och inte numeriska måste värdetypen i variabellistan (hashtabellen) vara av Sexpr:

Map<String,Sexpr> variables = new HashMap<String,Sexpr>();

Observera att variabellistan inte alls skall användas i parsern utan evalueringsmetoderna!

Följande struktur i main() (eller annan drivmetod) är lämplig (men bör utökas för att hantera vissa specialfall som quit, och eventuellt även andra ändringar):

Parser p = new Parser();
Map<String,Sexpr> variables = new HashMap<String,Sexpr>();

while (true)
   try {
      System.out.print("? ");
      Sexpr e = p.statement();
      System.out.println("Inläst uttryck: " + e)  // För kontroll
      System.out.println(e.eval(variables));
   } catch (...) {
   ...

(Kräver lite eftertanke om vad kommandonas toString()- och eval()-metoder skall returnera)

Som synes ovan evalueras ett lagrat uttryck genom att eval()-metoden för dess rotnod anropas. Beroende på rotnodens typ kan eventuella operanders eval()-metoder anropas. Dessa metoder utför helt enkelt en postordertraversering av trädet. En nods eval()-metod avgör först vad som skall göras med operanderna. De flesta operatorers operander skall evalueras. Ett undantag finns dock: tilldelningsoperatorn evaluerar sin vänstra men inte sin högra operand (1+2=a tilldelar värdet av 1+2 dvs 3 till variabeln a – inte till värdet av variabel a).

Till evalueringsmetodernas hjälp skall ni skriva en klass Symbolic som har ett antal statiska metoder som utför olika symboliska operationer: symbolisk addition, subtraktion, och så vidare… Dessa metoder utför numeriska operationer när det går och gör förenklingar när det går men returnerar alltid ett uttryck av typ Sexpr.

Exempel

Sinusklassens evalueringsmetod ser typiskt ut så här:

public Sexpr eval(HashMap<String,Sexpr> variables) {
    return Symbolic.sin(argument.eval(variables));
}

och metoden sin() i klassen Symbolic har följande utseende:

public static Sexpr sin(Sexpr arg) {
   if (arg.isConstant()) {
       return new Constant(Math.sin(arg.getValue()));
   } else {
       return new Sin(arg);
   }
}

Eller, mer kompakt:

public static Sexpr sin(Sexpr arg) {
   return (arg.isConstant()) ?
       new Constant(Math.sin(arg.getValue())) : new Sin(arg);
}

Observera att metoderna i Symbolic aldrig anropar någon eval()-metod!

Liknande metoder skrivs för de övriga funktionerna samt för alla operatorer som kan utföra någon form av aritmetisk beräkning. Om det är möjligt att utföra en numerisk beräkning ska det ske, annars får man utföra operationen symboliskt genom att skapa en ny nod av lämplig typ. Observera dock att metoden alltid måste returnera ett Sexpr, även om den lyckats beräkna ett numeriskt värde.

Exemplet ovan visar även att det finns ett behov av metoder som isConstant() och getValue() i klassen Sexpr.

OBS! Använd inte instanceof och inte heller typkastning utan utnyttja den dynamiska bindningen! Om man vill veta t.ex. om ett meddelande är quit implementeras detta lämpligen med hjälp av ett singleton-mönster (design pattern) och identitetsjämförelse eller annan teknik, t.ex. tillägg av metoder isQuit() etc. i rotklassen Sexpr.

När en variabel evalueras söker man efter den i variabellistan. Hittar man den där returnerar man dess värde, annars variabeln själv. Värdet som hämtas ur listan skall inte evalueras.

En konstant evalueras alltid till sig själv.

Att evaluera en tilldelning innebär att man evaluerar den vänstra operanden och lägger in dess värde i variabellistan som den högra operanden (variabeln). Det är sedan värdet av den evaluerade operanden som returneras.

I felhanteringen måste man skilja på syntaxfel (som inträffar under inläsningen) och evalueringsfel (som inträffar under evalueringen). Har ett syntaxfel inträffat måste man rensa bort resterna av det misslyckade uttrycket från input-strömmen. Rör det sig däremot om ett evalueringsfel har inläsningen gått bra och det räcker att meddela användaren vad som gick snett.

• Definiera klasshierarkin. Ta endast med konstruktorer och toString()-metoder och låt dessa sätta ut parenteser ”ovillkorligt”.
• Modifiera och bygg ut den parser som tidigare delats ut så att den bygger uttryck (utan evaluering).
• Testa att enskilda uttryck hanteras rätt genom att skriva enhetstester för varje funktion i parsern.
• Du kan testa kombinerade uttryck genom att skriva ett huvudprogram som läser in uttryck och sedan skriver ut det inlästa uttrycket. Ännu bättre är dock om du skriver automatiserade tester även för detta.
• Implementera priority()- och modifiera toString()-metoderna så att de bara sätter ut parenteser vid behov.
• Implementera klassen Symbolic. Gör bara ”enkla” implementationer av typ ”om båda operanderna i additionsmetoden är konstanter så skapa en ny konstant som summan av de två, annars skapa en ny additionsnod med samma operander”. Implementera eval-metoderna för de nodklasser som skrivits samt de andra metoder som krävs för att evaluering skall kunna utföras.
• Förbättra metoderna i klassen Symbolic så att de utför triviala förenklingar.