Loading...
dido1092 avatar dido1092 38 Точки

Problem 8. Balanced Parentheses / C# Advanced

Привет,

въпросната задача ми дава само 87/100 точки не намирам къде греша, ще съм благодарен за малко помощ!

https://pastebin.com/pdCzbnGF

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

Тагове:
0
C# Advanced 19/01/2020 14:02:23
willystyle avatar willystyle 2472 Точки

{}[]() това балансирани скоби ли са по условие, понеже мисля, че твоята логика не ги хваща, търсиш само симетрия отпред и отзад, но няма да хванеш май например {[]()}

Ще ти предложа по-кратко решение, само с един стек:
 

using System;
using System.Collections.Generic;

class MainClass
{
    public static void Main()
    {
        char[] parentheses = Console.ReadLine().ToCharArray();
        Dictionary<char, char> closingBrackets = new Dictionary<char, char>() { { ']', '[' }, { ')', '(' }, { '}', '{' } };
        Stack<char> stack = new Stack<char>();
        foreach (char bracket in parentheses)
        {
            if (stack.Count > 0 && closingBrackets.ContainsKey(bracket) && stack.Peek() == closingBrackets[bracket])
            {
                stack.Pop();
            }
            else
            {
                stack.Push(bracket);
            }
        }
        if (stack.Count == 0)
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }
    }
}

 

1
dido1092 avatar dido1092 38 Точки

Кодът ми също ги хваща тези условия които си показал за балансирани! Грешката ми е някъде другаде на което се надавях да разбера къде точно. Иначе благодаря Ти за краткия код, но малко трудно го разбирам. Прегледах готови решения повечето не са добре читими, поне за мен. Затова продоставих по-дълга версия но по-четима и разбираема, проблема е, че не сработва на 100/100. Бих искал помощ за това къде греша от колкото други решения.

0
willystyle avatar willystyle 2472 Точки

{{{()[]}[]}} -> YES

това е балансирано е твоето решение не ги хваща всички такива дето нямат симетрия и не се затварят веднага
ПС и с тази логика дето гледаш само отпред и още едно и отзад и още едно, просто няма как да ги хванеш.

1
19/01/2020 17:23:49
dido1092 avatar dido1092 38 Точки

Не предполагах такава комбинация, това за което гледам за текуща скоба и следваща е за да включа ПР: ({}[]), ще помисля и за такав израз, който си дал, благодаря!

1
willystyle avatar willystyle 2472 Точки

Задачата е от "Stacks and Queues" затова предполага да се реши със стек или опашка, но ми хрумна решение само със стрингове, което се оказва по-бързо, а и кода е доста кратък и надявам се четлив, какво се случва:
 

using System;

class BalancedParenthesis
{
    static void Main()
    {
        string input = Console.ReadLine();
        while (input.Contains("{}") || input.Contains("[]") || input.Contains("()"))
        {
            input = input.Replace("{}", "");
            input = input.Replace("[]", "");
            input = input.Replace("()", "");
        }
        if (input.Length == 0)
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }
    }
}

 

1
20/01/2020 11:35:09
dido1092 avatar dido1092 38 Точки

Да поздравявам те, много изчистено и практично!

0
dido1092 avatar dido1092 38 Точки

Аз пак се връщам на Стекове и Опашки, понеже ми се ще да разбера как може най-опростено да стане с тях. Написах нов код покрива последното условие което беше задал: '{{{()[]}[]}}', но отново не получавам 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");
            }

1
willystyle avatar willystyle 2472 Точки

Сега вече си на прав път и си почти готов, единствено пропускаш случая стека да е празен и скобата да е затваряща, това автоматично прави стринга небалансиран и може директно изход и печат NO, но може и да добавиш просто на реда с пуша и проверката да стане:
if (currentParenthes == '(' || currentParenthes == '{' || currentParenthes == '[' || !stack.Any())

1
dido1092 avatar dido1092 38 Точки

Сиреч израза да започне със  затваряща скоба? А аз в този случай не пълня стека, а той в крайна сметка е не балансиран!

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