Cortxets ben tancats i parèntesis parcialment tancats. X15283


Statement
 

pdf   zip

html

En aquest exercici considerarem mots construits sobre (,),[,], i regles de reemplaçament sobre ells:

  • ()→
  • []→
  • (]→ ]

Fixeu-vos que les dues primeres regles reemplacen els submots () i [] pel mot buit, mentre que la tercera regla reemplaça el submot (] pel mot ], lo qual és equivalent a poder esborrar un parèntesi d’obrir sempre i quan vingui seguit d’un cortxet de tancar.

Donat un mot d’entrada w, voldren donar com a sortida el mot resultant d’anar aplicant sobre w les regles anteriors tant com sigui possible.

Nota: el sistema de regles anterior és convergent, en el sentit que sempre acaba i que s’apliquin com s’apliquin les regles, i independentment de l’ordre i la posició, el resultat final quan ja no es pot aplicar cap més regla és el mateix.

Per exemple, si tenim com a entrada ([[](])(), donarem com a sortida el mot buit, perquè a base d’aplicar les regles anteriors acabem eliminant tots els caràcters:

([
[]
(])
()
 ⇒ ([
(]
) ⇒  (
[]
) ⇒ 
()
⇒

En canvi, si tenim com a entrada ([)](, el resultat és el mateix mot ([)](, doncs no es pot aplicar cap regla.

Observació: Podeu seguir l’enfoc que considereu oportú, i podeu utilitzar qualsevol de les classes presentades al curs (string, vector, stack, queue, list, map, set) de la manera que considereu oportuna. Noteu, però, que enfocaments diferents poden donar lloc a solucions més o menys eficients, i que superin només els jocs de proves públics o tots els jocs de proves, de manera que la nota acabarà depenent d’això.

Entrada

L’entrada conté un nombre arbitrari de casos, un per línia. Cada cas consisteix en un string no buit sobre (,),[,].

Sortida

Per a cada cas, escriviu en una línia el resultat d’aplicar les regles de reemplaçament tant com sigui possible.

Observació

Avaluació sobre 10 punts:

  • Solució lenta: 5 punts.
  • solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

Public test cases

  • Input

    (]
[)
()
[]
([)]
[(])
([])
[()]
()[)(][]
(()()][()())
(((]([])][))[(]]
(([]([]))[])[()]
(][())(()()]([()())[()()))
[([]([]))[])[(]][([]([]))[])[())
(()(())(()())((()())(()())))
[[](())(()())((()())(()()]]]
[[][[]][[][]][[[][]][[][]]]]

    Output

    ]
[)


([)]
)


[)]
][)
]][))]

][)]([)[))
[)][)[)

]]

  • Input

    ((()))()
[[][[]))(([]])()[())
[[()]]()[]
[(((])))[[))
[)
[[[]]()[)())[([])]
[(())((])]([])
((()))()
[]
[]
[())[[]][][](([]]]
(((()))(])()()[]
[)
([)()[[[]][)])(][]
[][]
()
((]][)()[](]
[]((([])])
(([]][])
[][)([]][]
[((](())](([[]())])]
[][]
[[[]][]](())
([][()]()]
[[])[][)
[[)()([[[)]))())()
(())()()
(]
([()()])()
[()]
(()()]([]([])[[])]()
[((]))
([]())([][))
[[(]]([()])][)
()
[[[](]]()())
(((()))([]][([])))
([([]]()]()()())[[])
[]()
[[)(][))()

    Output

    [[))])[)

)))[[))
[)
[[))
)]



[)]]
])
[)
([)[[)])]


]][)]
])
])
[)]
](([)])]


]
[)[)
[[)([[[)])))

]


]([)]
))
([))
][)

)
][))
])[)

[[)][))
    • Information
    Author
    PRO2
    Language
    Catalan
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++