Loading...
MartinBG avatar MartinBG 4803 Точки
Best Answer

Алгоритъмът за решаване на тази задача със стек е най-общо следният:

  1. Четем следващата скоба или отиваме на т. 4, ако сме прочели всичко
  2. Ако е отваряща (, [, { - слагаме я в стека и отиваме на т. 1
  3. Ако е затваряща: ), ], }:
    - ако стека е празен -> невалиден израз ("NO")
    - вадим последната скоба от стека и гледаме дали е отваряща от правилния тип: ( за ), [ за ] и { за }. Ако не съвпада -> невалиден израз ("NO"), иначе отиваме на т. 1
  4. Проверяваме дали има нещо в стека: ако има -> невалиден израз ("NO"), ако е празен -> изразът е валиден ("YES")

 Опитай да го приложиш в решението си и пиши, ако все още не минава в Judge.

1
SvetoslavPetsev avatar SvetoslavPetsev 100 Точки

Привет,

Видях, че сте тръгнали в посока да разделяте входния стринг на две и да обхождате получената част, сравнявайки входните данни с изваден от стека символ -> т.е да търсите симетрия в израза.

Малко е подвеждащо условието и примерите в тази задача. Всъщност под "балансирани скоби", автора има предвид, на всяка отваряща скоба да има съответна затваряща от същия тип, което не значи непременно симетричен израз. Това валидира и израз като ([]{}) -> YES.

Прилагам моето решение, но се опитайте да сглобите решение на база изведения алгоритъм по- горе от колегата MartinBG

https://pastebin.com/vh57qBc4

Успех!

1
Yovor37 avatar Yovor37 1 Точки

Благодаря и на двамата, с насоките на  MartinBG изкарах 75/100, после погледнах кода на SvetoslavPetsev , и се оказа че логита ми  е като неговата с малка грешка. И така успях.

1
martin4o124 avatar martin4o124 3 Точки

Аз я направих с коренно различна логика. За жалост докарах само 75/100, ако някой може да открие защо гърмят последните 2 теста в judge, ще съм му доста благодарен!

Ето кода : https://pastebin.com/yw3LhnBc

0
04/07/2020 20:49:42
MartinBG avatar MartinBG 4803 Точки

Логиката е грешна, защото не проверява последователността на скобите.

Например за входни данни:

)(

ще върне 

YES

0
martin4o124 avatar martin4o124 3 Точки

Така е! Пробвах се да направя подобрения, тук-там някоя друга проверка, но няма да стане с тази логика колкото и код да добавям.

1
SlaviPM avatar SlaviPM 2 Точки

Здравейте! За жалост и аз успях да я докарам само до 75/100. Ако някой може да ми помогне и да ми каже къде бъркам, ще съм много благодарен! https://pastebin.com/Mw1cX6n8

п.с. Python е понеже не успях да намеря решен проблем във форума и се надявах, четейки друг код да оправя моя.

0
Savas avatar Savas 38 Точки

Задачата е хубава, но има нещо бъгаво в джъджа.

Ето едно решение, което дава 100/100 – https://pastebin.com/qFX99fuy

Решението всъщност е грешно, защото ако се подават само отварящи скоби (което би довело до небалансирана поредица) – джъджа е ОК с това.

На ред 50 от кода ми има една проверка (която на практика взех от чуждо решение) – проверката казва, че ако се подава затваряща скоба, а в стака няма нищо - значи, че поредицата от скоби е небалансирана. Тази проверка хваща, както първа подадена затварящ скоба, така и ако някъде посредата на редицата от скоби се формира балансиран сигмент т.е. всичко подадено до момента е балансирано и следва затваряща скоба (това е случая за който не се бях сетил). Без тази проверка, въпреки всичките ми проверки (които съм махнал от кода си) – нещата не се получаваха.

0
18/09/2020 05:22:57
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.