Module: Korrekte Klammern-Sequenz (PSP)


Problem

2 /6


Omega-Lambda-Kalkül

Theory Click to read/hide

Die richtigen Klammern bestehen aus Öffnungs- und Schließbügeln eines oder mehrerer Typen, wobei jede Öffnungsbügel geschlossen sind und (bei mehreren Typen) ihre Typen nicht überlappt sind.
Korrekt SP:
(
- Ja.
[ {}
Falsche SPs:
) (
(
(Seufzt)
Um zu überprüfen, ob die Klammerfolge eines Typs ausreicht, um die Waage zu überprüfen.
Also machen wir eine Variable gleich Null. Dann laufen wir entlang der Linie (wenn Sie es nicht tun können - BEGIETE, GLOCKS!) durch die Erhöhung der Balance, wenn die Öffnungswinkel erfüllt sind, und durch die Verringerung, beim Schließen. Ist die Waage in jedem Stadium negativ oder am Ende ist sie nicht Null, dann ist die Sequenz falsch.

Problem

Omega-Lambda-Kalkül ist eine innovative Entwicklung von "British Scientists, Inc" im Bereich der formalen Logik. Jeder Ausdruck von Omega-Lambda-Kalkül besteht aus Klammern und Thermen (ein Thermom kann eine beliebige Folge von Buchstaben des lateinischen Alphabets sein). 
Izzy-Reduktion ist eine der Operationen für solche Ausdrücke. Bei der Ausführung wird überprüft, ob die Klammern-Sequenz im Ausdruck korrekt ist. Die Thermen werden dabei ignoriert. Wenn die Sequenz korrekt ist, wird sie in eine gg -Term umgewandelt, wenn nicht, in eine wp -Term. 
Ein Omega-Lambda-Ausdruck, der maximal 107Zeichen lang ist, wird an den Eingang geliefert. Wir müssen das Ergebnis seiner Izzy-Reduktion ableiten.
 

 

Beispiele
№ Eingabe Ausgabe
1 a(b(xx)f(g(x))m(y)) gg

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!