08. Balanced Parenthesis
Здравейте, колеги, имам нужда от помощ за тази задача.
https://softuni.bg/trainings/resources/officedocument/37032/exercise-problem-descriptions-csharp-advanced-january-2019/2243
В judge изакарвам 87/100
Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.
Best Answer
Алгоритъмът за решаване на тази задача със стек е най-общо следният:
- Четем следващата скоба или отиваме на т. 4, ако сме прочели всичко
- Ако е отваряща (, [, { - слагаме я в стека и отиваме на т. 1
- Ако е затваряща: ), ], }:
- ако стека е празен -> невалиден израз ("NO")
- вадим последната скоба от стека и гледаме дали е отваряща от правилния тип: ( за ), [ за ] и { за }. Ако не съвпада -> невалиден израз ("NO"), иначе отиваме на т. 1 - Проверяваме дали има нещо в стека: ако има -> невалиден израз ("NO"), ако е празен -> изразът е валиден ("YES")
Опитай да го приложиш в решението си и пиши, ако все още не минава в Judge.
Привет,
Видях, че сте тръгнали в посока да разделяте входния стринг на две и да обхождате получената част, сравнявайки входните данни с изваден от стека символ -> т.е да търсите симетрия в израза.
Малко е подвеждащо условието и примерите в тази задача. Всъщност под "балансирани скоби", автора има предвид, на всяка отваряща скоба да има съответна затваряща от същия тип, което не значи непременно симетричен израз. Това валидира и израз като ([]{}) -> YES.
Прилагам моето решение, но се опитайте да сглобите решение на база изведения алгоритъм по- горе от колегата MartinBG
Успех!
Благодаря и на двамата, с насоките на MartinBG изкарах 75/100, после погледнах кода на SvetoslavPetsev , и се оказа че логита ми е като неговата с малка грешка. И така успях.
Аз я направих с коренно различна логика. За жалост докарах само 75/100, ако някой може да открие защо гърмят последните 2 теста в judge, ще съм му доста благодарен!
Ето кода : https://pastebin.com/yw3LhnBc
Логиката е грешна, защото не проверява последователността на скобите.
Например за входни данни:
)(
ще върне
YES
Така е! Пробвах се да направя подобрения, тук-там някоя друга проверка, но няма да стане с тази логика колкото и код да добавям.
thank you very much. One of the most interesting articles I found in your website.
https://pcverses.com/category/games/
Здравейте! За жалост и аз успях да я докарам само до 75/100. Ако някой може да ми помогне и да ми каже къде бъркам, ще съм много благодарен! https://pastebin.com/Mw1cX6n8
п.с. Python е понеже не успях да намеря решен проблем във форума и се надявах, четейки друг код да оправя моя.
Задачата е хубава, но има нещо бъгаво в джъджа.
Ето едно решение, което дава 100/100 – https://pastebin.com/qFX99fuy
Решението всъщност е грешно, защото ако се подават само отварящи скоби (което би довело до небалансирана поредица) – джъджа е ОК с това.
На ред 50 от кода ми има една проверка (която на практика взех от чуждо решение) – проверката казва, че ако се подава затваряща скоба, а в стака няма нищо - значи, че поредицата от скоби е небалансирана. Тази проверка хваща, както първа подадена затварящ скоба, така и ако някъде посредата на редицата от скоби се формира балансиран сигмент т.е. всичко подадено до момента е балансирано и следва затваряща скоба (това е случая за който не се бях сетил). Без тази проверка, въпреки всичките ми проверки (които съм махнал от кода си) – нещата не се получаваха.