Професионална програма
Loading...
+ Нов въпрос
Svilen12 avatar Svilen12 3 Точки

Проблем задача Java Advanced

Здравейте, стигам до 87/100 точки на задачата Balanced Parentheses, пробвах няколко решения, но не знам къде точно е проблема, бих се радвал ако някой ми каже.

Това е линка към задачата->https://judge.softuni.bg/Contests/Compete/Index/1442#5

и решението->https://pastebin.com/Q3GnR0mN

 

 

 

 

Тагове:
0
Java Advanced
MartinBG avatar MartinBG 3751 Точки

Задачата е обсъждана многократно тук и за да не се повтарям, ето няколко от отговорите ми:

 

  • линк

    Класическото решение на този проблем е с използването на стек, но може да се реши и с опашка. 

  • линк

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

    Най-простият (и това автоматично го прави най-добър) алгоритъм за решаването на този проблем) е с използването на един стек.

    Четем скобите една по една:

    - ако е отваряща, т.е. ( { [, я добавяме в стека

    - ако е затваряща, т.е. ) } ], проверяваме в стека:

        ---- ако е празен => невалиден израз

        ---- ако скобата е от друг тип => невалиден израз

        ---- ако скобата е отваряща от правилния тип, продължаваме (след като сме я извадили от стека)

    - като свършат всички входни данни, проверяваме дали стека е празен:

        ---- ако не е празен => невалиден израз

        ---- празен стек - всички скоби са формирали валидни двойки, т.е. изразът е валиден

 

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

()(()) 

 

Опитайте да пререшите задачата само с един стек и според горните насоки,

0
Svilen12 avatar Svilen12 3 Точки

Благодаря за отговора, с насоките успях да я реша, мисля че спазих всички условия и извън judge, оставям си решението, ако някой има нужда от него->https://pastebin.com/wEe611x6

1