Module: Correct Bracket Sequence (RSP)


Problem

2 /6


Omega lambda calculus

Theory Click to read/hide

Regular bracket sequences consist of opening and closing brackets of one or more types, with each opening bracket having a closing bracket, and (in the case of multiple types) their types do not overlap. 
Correct SP: 
( ( ) ) ( ) ( ) 
{ } [ ( ) ] ( ) 
{ [ ( { } ) ] } 
Invalid SP: 
) ) ( ( ) ) ( ( 
{ [ ( ] ) } 
( ( ] } 
 
To check if a bracket sequence of brackets is of the same type, just check the balance. 
That is, we start a variable equal to zero (balance). Then we run through the string (if you don't know how to do this - RUN, STUPID!), increasing the balance when it meets the opening bracket and decreasing it when it meets the closing one. If at any stage the balance becomes negative or at the end it is not equal to zero, then the sequence is wrong. 

Problem

Omega lambda calculus - an innovative development of "British Scientists, Inc" in the realm of formal logic. Any expression of the omega-lambda calculus consists of parentheses and terms (a term can be any sequence of Latin letters). 
Izzy reduction is one of the operations on such expressions. When it is executed, it is checked whether the bracket sequence in the expression is correct. The terms are ignored. If the sequence is correct, it becomes the term gg, if not, it becomes the term wp. 
An omega-lambda expression of no more than 107 characters is used as input. You need to display the result of its izzy reduction.
 

 

Examples
# Input Output
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!