CS Challenge 6, Expression Simplification

Mange elever på STX og HTX har allerede stiftet bekendskab med Ligningsløseren, der laver perfekte besvarelser til opgaver om polynomielle ligninger.

I denne Challenge kigger vi på en central del af dette program, der kan simplificere regneudtryk. Fx kan udtrykket:

(x-1)(x-2)(x-3)+x(x+3)
simplificeres til denne ækvivalente udgave:
x^3-5x^2+14x-6
En væsentlig del af simplifikationen foregår ved hjælp af et rewriting system, hvor regneudtrykket omskrives skridt for skridt ved hjælp af et antal regler. Fx er der en regel, der siger at man kan samle konstanter i visse udtryk:

(c2-E)-c1 → [c2-c1]-E

I sådanne regler angiver "E" et generelt udtryk, "c" en talkonstant, "x" variablen x, "X" et produkt af variablen x, og "C" et konstant udtryk (uden forekomster af variablen x). Et udtryk af formen "[...]" angiver en udregning. Andre eksempler på regler er:

E+0 → E
-E1/-E2 → E1/E2
-X*c → X*[-c]

I alt benyttes der 95 regler for at simplificere udtryk, og de kan næsten alle ses i metoden:

public Exp simplify()
i klassen Exp i Exp.java. Hele koden ligger i Simplifier.zip.

Hver regel prøver at bringe udtrykket tættere på en normalform. Det vil sige, at samlingen af regler alt i alt realiserer et valg af, hvordan udtrykket skal ende med at se ud.


Spørgsmål A

Beskriv kort, hvad den ønskede normalform for regneudtrykkene er (efter simplify/multiply, men inden linearize).
Et regneudtryk repræsenteres som et objekt af klassen Exp. Fx kan udtrykket:
2+x
skrives i Java som:
new Exp('+',new Exp(2),new Exp())

Spørgsmål B

Angiv disse regneudtryk som Java udtryk af typen Exp:
x+5-2
x*x-2*x+7
x*x*(7-x)/5

I programmet Exp.java er der 4 abstrakte regler, hvor den tilsvarende kode ikke er implementeret (MISSING CODE).

Spørgsmål C

Tilføj den manglende kode for de 4 regler.

Spørgsmål D

Fjern en delmængde af reglerne og find et regneudtryk, der herefter ikke kan simplificeres helt i bund (til sin normalform). I denne sammenhæng ser vi på udtrykket inden kaldet af linearize (benyt toString() metoden i Exp til at udskrive udtrykket).

En triviel løsning er naturligvis at fjerne alle regler, så en bedre løsning finder en minimal delmængde. Faktisk gør den iterative anvendelse af simplify og multiply værktøjet overraskende robust mod "angreb".


BlueJ version: SimplifierBlueJ.zip.
Du deltager i vores Challenge ved senest den 6. december at sende en e-mail til mis@cs.au.dk med subject Challenge 6 og svarene på spørgsmål A, B og D (i plain text) samt et attachment med svaret på spørgsmål C i form af en ny udgave af klassen Exp.java.