Правильность расстановки скобок

Опубликовано Aug 29, 2011 в Массивы и строки | 19 коммент.

,

Правильность расстановки скобок

Разработайте функцию проверки правильности расстановки скобок в строке.

Вариант 1. Строка содержит один тип скобок.
Пример: “((( )( ))( ))”, результат – true;
“)(((()))”, результат – false.

Вариант 2. Строка содержит три типа скобок.
Пример: “{}[]()(()[])” результат – true;
Пример: “(}{)”, результат – false.

C++                                        C#
bool check_integrity(const char* src)      static bool CheckIntegrity(string src)
{                                          {
  // ваше решение                          // ваше решение
}                                          }

Критерии оценки FulcrumWeb:

Нужно продемонстрировать умение придумать и реализовать простой алгоритм

Ожидаемые вопросы:

  1. Можно ли разработать один общий метод на оба варианта, добавив в сигнатуру второй параметр для передачи типа скобок?
  2. C++: Можно ли использовать std::string?
  3. C#: Можно ли использовать класс Regex?

Оценка результатов:

Первый вопрос можно задать и основывать решение на его положительном ответе. Но при этом нужно понимать, что нужно создать метод-обертку для получения ответа варианта 2. Кроме того, нужно понимать, что в этом случае понадобится три прохода по строке, вместо одного.

От юниора ожидается любое работающее решение.

От более опытных кандидатов возможны вопросы либо про std::string, либо про Regex. Ограничивать использование этих средств мы не станем, но проверим, что претендент видит решение, основанное на классическом для конкретного языка представлении строк.

Решений уже приведено много. Полезные замечания по их поводу сделаны на одном из удачных вариантов и опубликованы в следующем посте на эту тему “Правильность расстановки скобок (C#) – рефакторинг”