C: Oefening op prioriteitsregels van expressie

[Verwijderd]

Hoi,

Na 1 dag C'en (cfr. http://gathering.tweakers.net/forum/list_messages/371128/1?limit=100/) heb ik een kleine vraag over een oefening die we moeten maken.

Het is de bedoeling dat we het volgende eenvoudiger schrijven:

code:

b = [ [ ( ( (!a) && (d < e) ) || ( ((d*e)+f) <= 10 ) ) ] == c ]

Zo heb ik het opgelost, maar ik wil even controle of het juist is

[b] Stap 1: [/b]
· de haakjes rond !a mogen weg, want dit is zinloos.
· de haakjes rond d*e mogen ook weg, eveneens zinloos.

nieuw resultaat:

code:

b = [ [ ( ( !a && (d < e) ) || ( (d*e+f) <= 10 ) ) ] == c ]

[b] Stap 2: [/b]
· de haakjes rond d*e+f mogen weg, want dat is een rekenkundige uitdrukking, en die heeft altijd voorrang op de <= (relationeel)
· links mogen de haakjes rond d < e ook weg, want < heeft eveneens atlijd voorrang op &&

nieuw resultaat:

code:

b = [ [ ( ( !a && d < e ) || ( d*e+f <= 10 ) ) ] == c ]

[b] Stap 3: [/b]
· nu staan er 2 keer haakjes, dus ofwel [ ofwel ( en ] ofwel ) mag weg links en rechts weg (ik doe [ ] weg)
· <= heeft voorrang op || , dus de haakjes rond d*e+f <= 10 mogen weg

nieuw resultaat:

code:

b = [ ( ( !a && d < e ) || d*e+f <= 10 ) == c ]

[b] Stap 4: [/b]
· de haakjes rond .. && .. moeten blijven staan, omdat || geen voorrang heeft op &&, dus moeten we dit expliciet aanduiden dmv. haakjes
· de vierkante haakjes zijn zinloos: weg
· de overige 2 ronde haakjes zijn ook zinloos want == heeft voorrang op ||

[b] eindresultaat: [/b]

code:

b = ( !a && d < e ) || d*e+f <= 10 == c

Hopelijk is het duidelijk voor jullie Bedankt

[.oisyn]

uhm ja okee en wat is nou de bedoeling van dit topic

[Klippy]

Op zondag 06 januari 2002 16:58 schreef OiSyN het volgende:
uhm ja okee en wat is nou de bedoeling van dit topic

ik wil even controle of het juist is

Ik ga eens ff kijken of ik wat fout zie, ben ook niet zo ged, maar oke ik zal proberen

Edit: Snap 't niet zo, sorry Boek met prioriteitsregels ligt boven, geen zin om te halen En dat met die [] haken snap ik helemaal niet
Kan beter iemand anders vragen denk ik

[Verwijderd]

Op zondag 06 januari 2002 17:00 schreef LiquidSilver het volgende:

[..]


[..]




Ik ga eens ff kijken of ik wat fout zie, ben ook niet zo ged, maar oke ik zal proberen

Edit: Snap 't niet zo, sorry Boek met prioriteitsregels ligt boven, geen zin om te halen En dat met die [] haken snap ik helemaal niet
Kan beter iemand anders vragen denk ik

Ok, toch bedankt om te proberen Ik snap er ook niet alles van, daarom dat ik het aan jullie vraag

[.oisyn]

Op zondag 06 januari 2002 17:00 wees LiquidSilver OiSyN op een stukje tekst

oh sowwy, mijn fout, overheen gelezen... hij had het ook zo verdacht opgesteld daar zo in het midden

er moeten er trouwens volgens mij nog haakjes om vanaf het begin tot voor de ==

zo dus: b = (( !a && d < e ) || d*e+f <= 10) == c

aangezien de == VOOR de || gaat, en de || moet hier eerst geevalueerd worden

en de haakjes om de linkerkant en rechterkant van && mogen ook weg, aangezien && VOOR de || wordt geevalueerd

dus: b = ( !a && d < e || d*e+f <= 10) == c

[mbravenboer]

Voor jou misschien niet erg nuttig, maar wellicht toch leuk om te horen: dit kan je uitermate leuk met herschrijf-regels doen. In feite ben je namelijk een programma-transformatie aan het implementeren. Het wordt pas echt leuk als je dus ook een programma-transformatie-taal neemt, maar wellicht dat het ook in een imperatieve taal leuk te implementeren valt.

Het idee is als volgt: eerst haal je gewoon alle haakjes weg, want haakjes zijn natuurlijk helemaal niet relevant in een abstract-syntax-tree. De boom zelf geeft namelijk al aan hoe de expressie bedoelt is. Het is dus in feite alleen een pretty-print probleem. Hoe kan je dat mooi oplossen?

Maak eerst een lijstje van de prioriteiten van alle operatoren.

Nu ga je de boom pretty-printen vanuit de wortel. Je houdt in elke knoop bij wat de prioriteit van die knoop is. Zodra de kinderen aan de beurt zijn, weet je dus de prioriteit van de 'parent'.
1. Als de prioriteit van de parent hoger is dan je eigen prioriteit moet je haakjes om je eigen expressie zetten.
2. Als de prioriteit van de parent gelijk is aan je eigen prioriteit zijn (in principe...) geen haakjes nodig.
3. Als de prioriteit van de parent lager is, zijn haakjes ook niet nodig.

Voorbeeldje:
prioriteit * = 2
prioriteit + = 1

Neem de expressie 6 * (4 + 5).
De abstract sytax tree hiervoor is:

code:

*
|- 6
|- +
   |- 4
   |- 5

Als je * gaat pretty printen zet je de 'huidige prioriteit' op 2. Als je in de + aankomt zie je dat jouw prioriteit lager is dan de huidige prioriteit -> je print een haakje.

Neem nu de expressie 6 * 4 + 5.
De abstract sytax tree hiervoor is:

code:

+
|- *
|  |- 6
|  |- 4
|  
|- 5

Als je + gaat pretty-printen zet je de huidige prioriteit op 1. Als je in de * komt, zie je dat jouw prioriteit hoger is dan de huidige prioriteit en hoef je dus geen haakjes te printen .

Je hebt nu een simpel, duidelijk en uitbreidbaar algoritme, waarvan je zelf kunt inzien (en bewijzen) dat het correct is. Geen stappen nodig en een nette scheiding van problemen .

[Verwijderd]

Op zondag 06 januari 2002 17:13 schreef OiSyN het volgende:

[..]

oh sowwy, mijn fout, overheen gelezen... hij had het ook zo verdacht opgesteld daar zo in het midden

er moeten er trouwens volgens mij nog haakjes om vanaf het begin tot voor de ==

zo dus: b = (( !a && d < e ) || d*e+f <= 10) == c

aangezien de == VOOR de || gaat, en de || moet hier eerst geevalueerd worden

en de haakjes om de linkerkant en rechterkant van && mogen ook weg, aangezien && VOOR de || wordt geevalueerd

dus: b = ( !a && d < e || d*e+f <= 10) == c

Dat laatste snap ik niet goed. && heeft inderdaad een grotere prioriteit dan ||.
Dus stel je hebt zoals hierboven (jan && miet) || piet. Jij zegt nu dat dat gelijk is aan jan && miet || piet. Maar is het nu niet zo omdat && hier het eerst wordt geëvalueerd, dat hij heel de linkderkant en heel de rechterkant neemt, en dus: (jan) && (miet || piet).

Het is me even niet duidelijk Maar bedankt!

[Verwijderd]

Op zondag 06 januari 2002 17:22 schreef mbravenboer het volgende:
..een mega lange tekst ..

Wuuw.. toch even herlezen hoor.. ga het tegelijk afprinten, lijkt me ERG handig Cool! bedankt

[.oisyn]

Op zondag 06 januari 2002 17:22 schreef mbravenboer transformatie geblaat

oh god, dat moest er ook nog bijkomen

anyway, misschien wel leuk: hier heb je je boom

code:

=
|
+- b
+- ==
   |
   +- ||
   |  |
   |  +- &&
   |  |  |
   |  |  +- !
   |  |  |  |
   |  |  |  +- a
   |  |  |
   |  |  +- <
   |  |     |
   |  |     +- d
   |  |     +- e
   |  |
   |  +- <=
   |     |
   |     +- +
   |     |  |
   |     |  +- *
   |     |  |  |
   |     |  |  +- d
   |     |  |  +- e
   |     |  |
   |     |  +- f
   |     |
   |     +- 10
   |
   +- c

[mbravenboer]

DiEana: lijkt me ERG handig Cool! bedankt

Graag gedaan . Ik hoop dat je eruit komt en dat het allemaal klopt, want het is altijd lastig met die prioriteiten: hoger, lager, geen haak, wel een haak . Voordat je het weet ga je de mist in .

[845]

Even over die && en die ||, ze hebben dezelfde prioriteit. Maar voor de werking leest de compiler van links naar rechts, welke die als eerst tegenkomt heeft dus voorrang.

(jan && miet) || piet

is hetzelfde dan (als)

jan && miet || piet

[Verwijderd]

Op zondag 06 januari 2002 17:43 schreef 845 het volgende:
Even over die && en die ||, ze hebben dezelfde prioriteit. Maar voor de werking leest de compiler van links naar rechts, welke die als eerst tegenkomt heeft dus voorrang.

(jan && miet) || piet

is hetzelfde dan (als)

jan && miet || piet

ja, en dat snap ik nu net niet. Ik snap niet waarom jan && miet || piet niet hetzelfde is als jan && (miet || piet) , omdat && hier op alles voorrang heeft, dus pakt de compiler de hele linkerkant en de hele rechterkant? En dus neemt hij de || er ook mee?

[.oisyn]

Op zondag 06 januari 2002 17:34 schreef DiEana het volgende:

[..]

Dat laatste snap ik niet goed. && heeft inderdaad een grotere prioriteit dan ||.
Dus stel je hebt zoals hierboven (jan && miet) || piet. Jij zegt nu dat dat gelijk is aan jan && miet || piet. Maar is het nu niet zo omdat && hier het eerst wordt geëvalueerd, dat hij heel de linkderkant en heel de rechterkant neemt, en dus: (jan) && (miet || piet).

Het is me even niet duidelijk Maar bedankt!

nee daar maak je een serieuze denkfout
als je doet a * b + c dan zou volgens jouw redenering dat hetzelfde moeten zijn als (a) * (b + c), maar natuurlijk moet het zijn (a * b) + (c)

je neemt dus ook niet de hele rechterkant en linkerkant, maar het deel wat ernaast staat. Het idee is voor het geval zonder haakjes, dat je steeds op zoek gaat naar de operator met de hoogste prioriteit, dat bereken je, en dan ga je weer verder

neem nou dit:

14 + 35 * 3 / 1 + 65 - 23

de * heeft hier de hoogste prioriteit, dus je berekent eerst 35 * 3, dat is 105. Dan krijg je 14 + 105 / 1 + 65 - 23
dan heeft / de hoogste prioriteit, 105 / 1 = 105, dus je krijgt 14 + 105 + 65 - 23
dan de +, 14 + 105 = 119 dus je krijgt 119 + 65 - 23
enz.

kan natuurlijk ook andersom, dus zoals jij het wilt: de hele linker en rechterkant nemen, maar dan moet je gaan zoeken naar de operator met de laagste prioriteit

[.oisyn]

Op zondag 06 januari 2002 17:43 schreef 845 het volgende:
Even over die && en die ||, ze hebben dezelfde prioriteit. Maar voor de werking leest de compiler van links naar rechts, welke die als eerst tegenkomt heeft dus voorrang.

nee dat is niet zo, && heeft een hogere prioriteit dan ||!

http://www.cppreference.com/operator_precedence.html

[Verwijderd]

Op zondag 06 januari 2002 17:45 schreef OiSyN het volgende:

[..]

..uitleg..

INDERDAAD.. zo zie je maar hoe je dingen kan uitleggen ahv. andere voorbeelden Ik wou dus constant de hele rechterkant en de hele linkerkant nemen, maar je moet idd. enkel nemen wat ernaast staat.

Beetje dom van mij eigenlijk

Bedankt voor je tijd joh!

[.oisyn]

Op zondag 06 januari 2002 17:48 schreef DiEana het volgende:
Bedankt voor je tijd joh!

no problem

ik zit op een lan en we gaan over 10 minuten opruimen, dusseeeh...

[Verwijderd]

Op zondag 06 januari 2002 17:49 schreef OiSyN het volgende:

[..]

no problem

ik zit op een lan en we gaan over 10 minuten opruimen, dusseeeh...

Toch nog 10 minuten lanplezier dan