Problem 8. Balanced Parentheses / C# Advanced
Привет,
въпросната задача ми дава само 87/100 точки не намирам къде греша, ще съм благодарен за малко помощ!
https://judge.softuni.bg/Contests/Compete/Index/1447#7
УСЛОВИЕ:
Given a sequence consisting of parentheses, determine whether the expression is balanced. A sequence of parentheses is balanced if every open parenthesis can be paired uniquely with a closed parenthesis that occurs after the former. Also, the interval between them must be balanced. You will be given three types of parentheses: (, {, and [.
{[()]} - This is a balanced parenthesis.
{[(])} - This is not a balanced parenthesis.
Input
- Each input consists of a single line, the sequence of parentheses.
Output
- For each test case, print on a new line "YES" if the parentheses are balanced.
Otherwise, print "NO". Do not print the quotes.
Constraints
- 1 ≤ lens ≤ 1000, where lens is the length of the sequence.
- Each character of the sequence will be one of {, }, (, ), [, ].
Examples
Input |
Output |
{[()]} |
YES |
{[(])} |
NO |
{{[[(())]]}} |
YES |
Кодът ми също ги хваща тези условия които си показал за балансирани! Грешката ми е някъде другаде на което се надавях да разбера къде точно. Иначе благодаря Ти за краткия код, но малко трудно го разбирам. Прегледах готови решения повечето не са добре читими, поне за мен. Затова продоставих по-дълга версия но по-четима и разбираема, проблема е, че не сработва на 100/100. Бих искал помощ за това къде греша от колкото други решения.
{{{()[]}[]}} -> YES
това е балансирано е твоето решение не ги хваща всички такива дето нямат симетрия и не се затварят веднага
ПС и с тази логика дето гледаш само отпред и още едно и отзад и още едно, просто няма как да ги хванеш.
Не предполагах такава комбинация, това за което гледам за текуща скоба и следваща е за да включа ПР: ({}[]), ще помисля и за такав израз, който си дал, благодаря!
Задачата е от "Stacks and Queues" затова предполага да се реши със стек или опашка, но ми хрумна решение само със стрингове, което се оказва по-бързо, а и кода е доста кратък и надявам се четлив, какво се случва:
Да поздравявам те, много изчистено и практично!
Аз пак се връщам на Стекове и Опашки, понеже ми се ще да разбера как може най-опростено да стане с тях. Написах нов код покрива последното условие което беше задал: '{{{()[]}[]}}', но отново не получавам 100/100 а 75/100.
char[] parenthes = Console.ReadLine().ToCharArray();
Stack<char> stack = new Stack<char>();
for (int i = 0; i < parenthes.Length; i++)
{
char currentParenthes = parenthes[i];
if (currentParenthes == '(' || currentParenthes == '{' || currentParenthes == '[')
{
stack.Push(currentParenthes);
}
else if (stack.Any() && (currentParenthes == ')' && stack.Peek() == '('))
{
stack.Pop();
}
else if (stack.Any() && (currentParenthes == '}' && stack.Peek() == '{'))
{
stack.Pop();
}
else if (stack.Any() && (currentParenthes == ']' && stack.Peek() == '['))
{
stack.Pop();
}
}
if (stack.Count == 0)
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
Сега вече си на прав път и си почти готов, единствено пропускаш случая стека да е празен и скобата да е затваряща, това автоматично прави стринга небалансиран и може директно изход и печат NO, но може и да добавиш просто на реда с пуша и проверката да стане:
if (currentParenthes == '(' || currentParenthes == '{' || currentParenthes == '[' || !stack.Any())
Сиреч израза да започне със затваряща скоба? А аз в този случай не пълня стека, а той в крайна сметка е не балансиран!