0

Daily Challenge #26

Witaj! Kolejny dzień, kolejne zadanie.

  • Zadanie numer: #26
  • Autor: Facebook
  • Trudność: 1/5
  • Główny problem: parsowanie tekstu
Wpis ten należy do cyklu Daily Challenge. Od poniedziałku do piątku, codziennie, o 7:30 publikuję rozwiązanie jednego zadania. Zadania rozwiązywane w ramach tego cyklu są zadaniami przeznaczonymi na rozmowy kwalifikacyjne. Są treściwe, krótkie i wymagają jakichś konkretnych umiejętności. Przedstawione problemy realizuję właśnie w ten sposób. Nie wymyślam najlepszego algorytmu, nie optymalizuję kodu do granic możliwości, tylko implementuję pierwszą myśl. Robię to dla zabawy i chęci sprawdzenia swoich możliwości. Zaimplementowane rozwiązanie nie jest z reguły tłumaczone, jeżeli masz pytania możesz je zadawać w komentarzach. Wszystkie zadania udostępniane są subskrybentom Daily Coding Problem. Moje implementacje (również tego zadania) dostępne są na GitHubie.

Treść

Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string “([])[]({})”, you should return true.
Given the string “([)]” or “((()”, you should return false.

Implementacja: testy

[TestMethod]
public void DailyChallenge26()
{
    DailyChallenge26 daily = new DailyChallenge26();
    Assert.IsTrue(daily.Proceed("([])[]({})"));
    Assert.IsFalse(daily.Proceed("((()"));
    Assert.IsFalse(daily.Proceed("([)]"));
}

Implementacja: algorytm

private class OpenClose
{
    public char Open;
    public char Close;
}
 
private List<OpenClose> _openClose = new List<OpenClose>()
{
    new OpenClose{Open = '{', Close = '}'},
    new OpenClose{Open = '[', Close = ']'},
    new OpenClose{Open = '(', Close = ')'},
};
 
public bool Proceed(string text)
{
    Stack<char> queue = new Stack<char>();
    foreach(var ch in text)
    {
        OpenClose open = _openClose.FirstOrDefault(x => x.Open == ch);
        OpenClose close = _openClose.FirstOrDefault(x => x.Close == ch);
        if (open == null && close == null)
        {
            return false;
        }
        if (open != null)
        {
            queue.Push(open.Open);
        }
        else
        {
            if (queue.Any() == false)
            {
                return false;
            }
            char poped = queue.Pop();
            if (poped != close.Open)
            {
                return false;
            }
        }
    }
    return queue.Any() == false;
}

Mission Completed

Słabizna tym razem, oklepany schemat, wystarczy dobrze posługiwać się stosem. Nie ma co się rozwodzić  nad tematem.

Jeżeli Ty chciałbyś podesłać jakieś ciekawe zadanie, to nie krępuj się proszę i ślij na p.bogdanski@devmight.pl. Pamiętaj, że zadanie powinno nadawać się na rozmowę kwalifikacyjną, więc nie może to być problem, którego rozwiązanie zajmuje kilka godzin. Dzięki!

Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.