In wiskundige uitdrukkingen worden er haakjes geplaatst om de volgorde van bewerkingen te wijzigen. Als er meerdere niveaus van haakjes nodig zijn, kunnen vergelijkingen snel onoverzichtelijk worden. Daarom gebruikt men andere soorten haakjes, of van grotere haken, om het niveau aan te duiden.
Bijvoorbeeld: \(((x+5)\cdot (2\cdot (x-3) + 4)) \cdot (x-1)\) wordt dan \(\bigg\{(x+5)\cdot \big[2\cdot (x-3) + 4\big]\bigg\} \cdot (x-1)\).
In deze oefening willen we voor alle haakjes in een gegeven uitdrukking bepalen op welk niveau ze zitten. Concreet wordt dit als volgt gedefinieerd: een paar haakjes waarbinnen zelf geen haakjes staan zit op niveau 0. Een paar haakjes waarvan het maximale niveau van all haakjes erbinnen \(k\) is, zit zelf op niveau \(k+1\).
Hiervoor implementeer je de interface SizeCalculator1 in een klasse genaamd MySizeCalculator. Deze interface heeft één methode, int[] calculateSize(boolean[] opening).
Deze neemt een array van booleans in die voorstelt welke haakjes openend zijn, bijvoorbeeld ()(()) wordt voorgesteld als [true,false,true,true,false,false].De invoer bestaat voor het gemak dus enkel uit haakjes.
De returnwaarde is een array van getallen die even lang is als de invoer en zodat op index i het niveau staat van het overeenkomstige haakje op index i van de invoer.
De bedoeling is om een \(O(n)\)-algoritme te ontwerpen.
Je kan zoals gebruikelijk je code lokaal debuggen met behulp van de SimpleTest testklasse2.
Als je beide de haakjes van begin tot eind verwerkt, dan kan je pas weten wat het niveau zal zijn van een paar haakjes wanneer je het sluitende haakje verwerkt. Je zal dan twee zaken moeten achterhalen:
Probeer de laatste stap eerst kwadratisch op te lossen. Wanneer je daar een oplossing voor hebt kan je op zoek gaan om dit te optimaliseren om een lineair algoritme te vinden.