3. naloga

Zaklepajski izrazi

Oklepajski izrazi so nizi, ki jih sestavljajo sami oklepaji in zaklepaji, morajo pa biti pravilno gnezdeni. Oklepaji in zaklepaji so lahko različnih oblik: okrogli ( ), oglati [ ], zaviti { } in kotni < >. ››Pravilno gnezdeni‹‹ pomeni, da mora imeti vsak oklepaj tudi pripadajoč zaklepaj enake oblike (in obratno), podniz med njima pa mora biti tudi sam zase oklepajski izraz.

Nekaj primerov oklepajskih izrazov: <<>>, [()(<>)](), {[{}()]<>}.

Nekaj primerov nizov, ki niso oklepajski izrazi: (()(, ([)], <>><<>.

Dan je nek niz s, v katerem se pojavljajo le zaklepaji različnih oblik — ) ] } > — in zvezdice *. Napiši podprogram Dopolni(s), ki vsako zvezdico v nizu s spremeni v enega od oklepajev — torej znakov ( [ { < — tako, da bo iz tega na koncu nastal pravilno gnezden oklepajski izraz. Podprogram naj tako popravljeni niz izpiše, če pa se izkaže, da ga ni mogoče ustrezno popraviti (da bi nastal oklepajski izraz), naj izpiše, da je problem nerešljiv.

Primer: iz "**]*))" lahko naredimo "([]())". Iz "***>*)" pa ne moremo narediti veljavnega oklepajskega izraza ne glede na to, kako spreminjamo zvezdice v oklepaje.

Tvoj podprogram naj bo takšne oblike:

procedure Dopolni(s: string);                 { v pascalu }
void Dopolni(char *s);                            /* v C/C++ */
void Dopolni(string s);                           // v C++
public static void Dopolni(String s);       // v javi
public static void Dopolni(string s);       // v C#
def Dopolni(s): . . .                                # v pythonu; s je tipa str