Državno natjecanje 2013. / Osnovna škola (8. razred) - 2. zadatak

Zadan je niz sa znakovima: '?', '(', ')', '[', ']', '{', '}'.

Potrebno je u nizu zamijeniti svaki znak '?' s nekim od znakova ')', ']', '}' tako da se dobije pravilan niz.

Pravilan niz definiramo na poznati način kako slijedi:

1. (), [], {} su pravilni nizovi;
2. Ako je X pravilan niz, onda su i nizovi (X), [X], {X} pravilni;
3. Ako su X i Y pravilni nizovi, onda je i niz XY pravilan.

Npr, primjeri pravilnih nizova su: ((())), ([]), {}()[], [{}(){}], ([()]{{}}), a primjeri nepravilnih nizova su: {, ][, ([)], ([]{(}, [[()], {([])()]{}.

Rješenje će uvijek postojati i bit će jedinstveno.

ULAZNI PODATCI

U prvom retku nalazi se jedan prirodan broj N (1 ≤ N ≤ 30), duljina niza znakova.

U drugom retku nalazi se niz znakova duljine N.

IZLAZNI PODATCI

U jedinom retku treba ispisati pravilan niz znakova dobiven postupkom opisanim u zadatku.

PRIMJERI TEST PODATAKA

Ulaz

4
({?)

Izlaz

({})

Ulaz

2
[?

Izlaz

[]

Ulaz

10
{[?[]?(?[]

Izlaz

{[][]}()[]