1

Тема: задача Matching Brackets codeabbey

Ось сама задача - https://www.codeabbey.com/index/task_vi … g-brackets
Мій розв'язок

out = []
for w in range(int(input())):
    k = 1
    x = []
    inp = list("".join(x for x in input() if x in ("{}[]()<>")))
    for i in inp:
        if i == "(":
            x.append(")")
        elif i == "[":
            x.append("]")
        elif i == "{":
            x.append("}")
        elif i == "<":
            x.append(">")
        elif len(x) == 0:
            k -= 1
        elif i == x[len(x) - 1]:
            x.pop(len(x) - 1)
        else:
            k -= 1
    if len(x) != 0:
        out.append("0")
    elif k == 1: 
        out.append("1")
    else:
        out.append("0")
        
print(" ".join(out))

В компіляторі все працює, а на codeabbey просто не вираховує відповідь (тобто в полі де має обрахуватися результат безкінечно виводить крапки, ніби вираховує).
Допоможіть будь ласка вирішити проблему.

2 Востаннє редагувалося /KIT\ (07.06.2019 19:43:08)

Re: задача Matching Brackets codeabbey

brackets = {
    "(":")",
    "<":">",
    "{":"}",
    "[":"]",
    ")":"(",
    ">":"<",
    "}":"{",
    "]":"["
}
result = []
for _ in range(int(input())):
    stack = []
    string = filter(brackets.__contains__,input())
    for char in string:
        if len(stack) and stack[-1]==brackets[char]:
            stack.pop()
        else:
            stack.append(char)
    result.append(0 if len(stack) else 1)
print(*result)

Try it online!
UPD: Код правильний
UPD 2: There could be different approaches to this task, but most effective is to use the stack data structure (for example Python lists could work as stack with .append() and .pop() methods). Цей код якраз стек і використовує.

Подякували: Eff1c, koala, leofun013

3

Re: задача Matching Brackets codeabbey

s='''<{ }(({*} )<a>-[< (x)[<^>y]>%]<x>)[< >+]<v[ ]>>
[a]<*[{z}{b}-]>[w]<<-( {x})>{b(z)} [<e><+>^]>(<x{e}(e)>)[e]{v}
[t](({g}(z)[f]g)[u](y)[z )<e>(c)<g(/)>(c)
{[^]{b{( )%}}}((<v(g)>c<g>)+[{<x>[/]<^>*<{v{/}}z>}e[b]{e}{ }](v))
</{t{*[a]}}<->><<<b>t{d}>{g}>{<v>x}{d}(%<{z(t<x>){g}}%><*>)
[[{d}/]]([v]e[/(/)])[((h[t])b) ]< h>{(x[v]) }+>
(f)<g><[{[(%)+]{b}{[h[y]]e}y}a](a)>( ){ }[[+]/]
({x})(<<w>g<y>{ }>h(/)[<x>b[d]])[ ][ [v]]
<x><d>[%{ }[/]]{ }{t (a<[z](a)(^)u{*{*}}{y<d>}>(w))[v](v)()
{<<z><+{ }>->{%}[[*]{(f)a(f)}v{{h}h}][{g[v]}<%>z[x]][+][{a}w]}
(c){[g[*]][ ]%{^}}<<z<(<c>(/)[w] )h[ (g)]>>(h)>
<><(*)><[a]<g><t>e>{w}/( )]^(e)>(a)(g[c](^)(/))[(y)-]<^( <->)[
>(y(*(<f>w)<->)<b<%>[<d>)](f{(u<g>)^})[f]
<[t]< >( <^{(^)<w>f<g><{{ {x}<<e>{/} >}e}[-] >}>(z))>
{}(u){<^>{u z(b{e})}{t{h[x]<(e)(*)^>}(v)}
<[f]->{d}]{^(x)}(+)<<w(b)>b<{[b(e}+>>-<w>)[e]( )[^]{}
( )[t]([u][w]z{ })< (*)<a>>{{[-{v} {y}e}}
{[y]v[+]}<c{h}(c)> <*>< ><d(w)>(^)[+](f)}( {b(a)})'''

def OC(si):
    b_round='()'
    b_square='[]'
    b_curly='{}'
    b_angle='<>'
    stack=[1]
    brackets=b_round+b_square+b_curly+b_angle
    for i in si:
        if i in brackets[1::2] and len(stack)!=0: # close 
            #print('try close' , i, end='' )
            prev=stack.pop()
            if prev!=brackets[brackets.index(i)-1]:
                #print ("   not closed!")
                break
        elif i in brackets[0::2]: # open
            #print('open', i, end='')
            stack.append(i)
    if stack!=[1]:
        print( 0, end=' ' )
    else:
        print(1, end=' ')
    
for si in s.split('\n'):
    OC(si)
    

колись давно я це рішав так

Подякували: Eff1c1

4

Re: задача Matching Brackets codeabbey

Дякую.
Але можете будь ласка чому мій розв'язок не працює?

5

Re: задача Matching Brackets codeabbey

Спробуйте додати до відповіді пробіл

6

Re: задача Matching Brackets codeabbey

koala написав:

Спробуйте додати до відповіді пробіл

Так там я і дав значення пробілу в join
Проблема в тому, що взагалі відповідь не обчислюється

7

Re: задача Matching Brackets codeabbey

Проблема на сайті. Спробуйте "запустити" цей код будь-якою іншою мовою - матимете той самий результат.
Раджу відкрити тему про це на тамтешньому форумі, може, хтось помітить.

Ну і пара порад по коду:

for w in range(int(input())):

не помилка, звісно, але трохи краще вводити данні змінну перед тим, як використовувати їх. Просто для порядку. Ось так:

test_number = int(input())
for _ in range(test_number):

І використовуйте змінну _ для непотрібних значень, це загальна практика в Python.

inp = list("".join(x for x in input() if x in ("{}[]()<>")))
for i in inp:

У вас є стрічка input(). Ви її перебираєте по символу і лишаєте тільки дужки, після чого об'єднуєте в стрічку лише для того, щоб перетворити на список, по якому пройдетеся циклом. Нащо знову збирати в стрічку? Одразу збираємо в список:

inp = [x for x in input() if x in "{}[]()<>"]
for i in inp:

Але стоп, список нам потрібен не для маніпуляцій з ним (додати-викинути-змінити), а для... циклу. Тобто списку не треба, можна загнати генераторний вираз в наступний цикл:

for i in (x for x in input() if x in "{}[]()<>"):

І це ще не все. У нас цикл по даних, згенерованих іншим циклом. Але нащо нам той інший цикл, якщо все вже є в першому?

for i in input():
    if i in "{}[]()<>":

Ми програли один відступ, зате код став значно зрозумілішим. Але хіба програли? Хіба далі ми в коді не перевіряємо значення i?

inp = input() #так, краще додати змінну для порядку
for i in inp:
        if i == "(":
            x.append(")")
        elif i == "[":
            x.append("]")
        elif i == "{":
            x.append("}")
        elif i == "<":
            x.append(">")
        elif x in "}])>":
            if len(x) == 0:
                k -= 1
            elif i == x[len(x) - 1]:
                x.pop(len(x) - 1)
            else:
                k -= 1

Бачите - це ваш код, але cпрощений.
Далі я б порадив придивитися до коду Кота - всі ці ваші if i == "(":x.append(")") чудово стискаються в один рядок, якщо скористатися dict-ом, а всі варіанти з out.append чудово стискаються його методом в інший рядок.

Подякували: Eff1c1

8

Re: задача Matching Brackets codeabbey

Дякую)

koala написав:

Раджу відкрити тему про це на тамтешньому форумі, може, хтось помітить.

Мабуть що не буду. Часу не вистачає, та і англійську я не дуже добре знаю.

koala написав:

І це ще не все. У нас цикл по даних, згенерованих іншим циклом. Але нащо нам той інший цикл, якщо все вже є в першому?

for i in input():
    if i in "{}[]()<>":

Ось на цьому моменті не зрозумів  *SCRATCH*

koala написав:

Ми програли один відступ, зате код став значно зрозумілішим. Але хіба програли? Хіба далі ми в коді не перевіряємо значення i?

І на цьому теж.


koala написав:
inp = input() #так, краще додати змінну для порядку
for i in inp:
        if i == "(":
            x.append(")")
        elif i == "[":
            x.append("]")
        elif i == "{":
            x.append("}")
        elif i == "<":
            x.append(">")
        elif x in "}])>":
            if len(x) == 0:
                k -= 1
            elif i == x[len(x) - 1]:
                x.pop(len(x) - 1)
            else:
                k -= 1

Тобто не потрібно залишати всі ті дужки і вирізати всі інші символи?

koala написав:

Далі я б порадив придивитися до коду Кота

Я просто не все там розумію
Наприклад цей рядок

string = filter(brackets.__contains__,input())

Поясніть будь ласка що це за "brackets.__contains__" в значенні фільтра?

koala написав:

чудово стискаються в один рядок, якщо скористатися dict-ом

Можете розказати детальніше?

9 Востаннє редагувалося /KIT\ (17.06.2019 22:25:49)

Re: задача Matching Brackets codeabbey

>Поясніть будь ласка що це за "brackets.__contains__" в значенні фільтра?
object.__contains__(argument) - перевіряє, чи є argument в object. Повертає True або False
Наприклад:

"abcd".__contains__("a") == True
"abcd".__contains__("1") == False

В випадку з словником, __contains__ перевіряє лише ключі.
Про filter читайте тут

Подякували: Eff1c1

10

Re: задача Matching Brackets codeabbey

Eff1c написав:

Тобто не потрібно залишати всі ті дужки і вирізати всі інші символи?

Потрібно. І ми це робимо, але дивіться уважно - де:

if i == ...
elif ...
elif ...
elif ...
   if ...
   elif
   else
<- ось тут мав би бути else до першого ланцюжка if-elif-elif-... Але його немає. 
Тобто символи, що не потрапили в попередні if-elif, ви викидаємо прямо в циклі, ігноруючи їх
Eff1c написав:

Поясніть будь ласка що це за "brackets.__contains__" в значенні фільтра?

__contains__ - магічна функція, що викликається при застосуванні оператора in. Зрозуміліше це можна записати так:

string = (x for x in input() if x in brackets)

Тобто це той самий фільтр, що й у вас.

Про dict. У вас є конструкція

if x==значення_1:
   дія зі значення_2
elif x==значення_3:
   дія зі значення_4
elif x==значення_5:
   дія зі значення_6
...

Причому дії однакові, різне лише значення.
Видно, що це, насправді, одна дія, але зі складним параметром:

дія зі(значення_2 if x==значення_1 else значення_4 if x==значення_3 else значення_6 if x==значення_5 ...)

А як по одному значенню отримати інше? Оце ж і робить dict!

d = {значення_1:значення_2, значення_3:значення_4, значення_5:значення_6}
дія з d[x]
Подякували: ReAl, Eff1c2

11

Re: задача Matching Brackets codeabbey

koala написав:

Причому дії однакові, різне лише значення.
Видно, що це, насправді, одна дія, але зі складним параметром:

дія зі(значення_2 if x==значення_1 else значення_4 if x==значення_3 else значення_6 if x==значення_5 ...)

А як по одному значенню отримати інше? Оце ж і робить dict!

d = {значення_1:значення_2, значення_3:значення_4, значення_5:значення_6}
дія з d[x]

Та ще й робить так, що
• легше читати
• легше модифікувати
  • причому навіть в run-time
• швидше працює

Подякували: Eff1c1

12 Востаннє редагувалося koala (18.06.2019 15:00:09)

Re: задача Matching Brackets codeabbey

Трохи переробив код пана Кота:

BRACKETS = {"(":")","{":"}","[":"]","<":">"}
result = []
number_tests = int(input())
for _ in range(number_tests):
    stack = []
    string = input()
    for char in string:
        if char in BRACKETS: #in перевіряє в ключах - тобто якщо char є дужкою, що відкривається
            stack.append(BRACKETS[char]) #тоді кладемо в стек дужку, на яку ми чекаємо
        elif char in BRACKETS.values(): #тепер перевіряємо у значеннях
            if stack and stack[-1]==char: #не треба перевіряти довжину, bool(list) перевіряє наявність елементів
              stack.pop()
            else:
              result.append(0)
              break #одразу виходимо
    else: #for-else спрацьовує лише якщо не було break
      result.append(int(not stack)) #скорочене перетворення
print(*result)
Подякували: /KIT\, Eff1c2

13

Re: задача Matching Brackets codeabbey

Альтернативний варіант мого коду з стрічкою замість словника

brackets = "<({[]})>"
result = []
for _ in range(int(input())):
    stack = []
    string = filter(brackets.__contains__,input())
    for char in string:
        if stack and stack[-1]==brackets[~brackets.index(char)]:
            stack.pop()
        else:
            stack.append(char)
    result.append(0 if stack else 1)
print(*result)
Подякували: Eff1c1

14

Re: задача Matching Brackets codeabbey

koala написав:

Трохи переробив код пана Кота:

BRACKETS = {"(":")","{":"}","[":"]","{":"}"}
result = []
number_tests = int(input())
for _ in range(number_tests):
    stack = []
    string = input()
    for char in string:
        if char in BRACKETS: #in перевіряє в ключах - тобто якщо char є дужкою, що відкривається
            stack.append(BRACKETS[char]) #тоді кладемо в стек дужку, на яку ми чекаємо
        elif char in BRACKETS.values(): #тепер перевіряємо у значеннях
            if stack and stack[-1]==char: #не треба перевіряти довжину, bool(list) перевіряє наявність елементів
              stack.pop()
            else:
              result.append(0)
              break #одразу виходимо
    else: #for-else спрацьовує лише якщо не було break
      result.append(int(not stack)) #скорочене перетворення
print(*result)

У вас помилка в першому рядку:

BRACKETS = {"(":")","{":"}","[":"]","<":">"}
Подякували: koala, Eff1c2

15

Re: задача Matching Brackets codeabbey

Дякую, пофіксив.