Професионална програма
Loading...
+ Нов въпрос
MartinBG avatar MartinBG 2783 Точки
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 2783 Точки

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

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

)(

ще върне 

YES

0
martin4o124 avatar martin4o124 3 Точки

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

1