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

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

,

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

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

Вариант 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#) – рефакторинг”


18 Коммент. : “Правильность расстановки скобок”

  1. А можно использовать std::stack?

    • Например так:

      bool check_integrity(const char* src)
      {                                    
      bool        ret=true;
      std::stack stk;
      char        c;
       
      while((c=*src++) && ret)
      {
        switch(c)
        {
      	  case '(':
      	  case '[':
      	  case '{':   stk.push(c);	break;
       
      	  case ')': ret=(!stk.empty() && stk.top()=='(') ? stk.pop(),true : false; break;
      	  case ']': ret=(!stk.empty() && stk.top()=='[') ? stk.pop(),true : false; break;
      	  case '}': ret=(!stk.empty() && stk.top()=='{') ? stk.pop(),true : false; break;
       
      	  default : ret=false; 
        }
      }
       
      if(!stk.empty())ret=false;
       
      return ret;
      }
      • Владислав says:

        Тоже так реализовал, только с помощью string, но так даже лучше.
        Только добавь проверку на нулевую строку и всё будет отлично.
        if (!std::strlen(str)) return false;

  2. Alehandro says:

    А такое тоже должно распознаваться “{[()]}{[()]}”? “{[(())][(())]}”?

    • Галина says:

      Это же упражнения. Вполне можете поставить себе задачу так: Да, должно.

  3. Александр says:

    Поделюсь своим решением

    bool check_integrity(char *scr)
    {
    	int size = getSize(scr);
     
    	return checkBracketsRec(scr, size);
     
    }
     
    bool checkBracketsRec(char *data, int size)
    {	
    	if(size == 0) return true;
     
    	if(isValidLeft(data[0]))
    	{
    		int index = findClosingRight(data, size);
     
    		if(index == size - 1)
    		{
    			return checkBracketsRec(data + 1, size - 2);
    		}
    		else if(index == 1)
    		{
               return checkBracketsRec(data + 2, size - 2);			
    		}
    		else if(index)
    		{
    			return checkBracketsRec(data, index + 1)
    					& checkBracketsRec(data + index + 1, size - (index + 1));
    		}
    		else
    		{
    			return false;
    		}
    	}
    	else
    	{
    	    return false;
    	}
    }
     
    bool isValidLeft(char data)
    {
    	if(data == '{' || data == '[' || data == '(') return true;
    	return false;
    }
     
    // 0 - no closing char for given dataChar
    int findClosingRight(char *dataArr, int size)
    {
    	bool found = false;
    	int index = 1;
    	int leftClosingCnt = 1;
    	int rightClosingCnt = 0;
     
    	while(index < size)
    	{
    		if(dataArr[0] == dataArr[index])
    		{
    			leftClosingCnt++;
    		}
    	    else if(dataArr[0] == getValidLeft(dataArr[index]))
    	    {
    	    	rightClosingCnt++;
    	    }
     
    	    if(leftClosingCnt == rightClosingCnt)
    	    {
    		    found = true;
    		    break;
    	    }
    	    index++;
    	}
     
    	if(!found)
    	{
    		index = 0;
    	}
    	return index;
    }
     
    char getValidLeft(char data)
    {
    	char left = 0;
    	switch(data)
    	{
    	case &#039;}&#039;:
    		left = &#039;{&#039;;
    		break;
     
    	case &#039;]&#039;:
    		left = &#039;[&#039;;
    		break;
     
    	case &#039;)&#039;:
    		left = &#039;(&#039;;
    		break;
    	}
    	return left;
    }
     
    int getSize(char *data)
    {
    	int size = 0;
     
    	while(*data++)
    	{
    		++size;
    	}
    	return size;
    }
     
    int main(int argc, char* argv[])
    {
    	bool result;
     
    	char *data = "((([])))";
    	result = check_integrity(data); // true
     
    	data = "{[}[]()((})[])]";
    	result = check_integrity(data); // false
     
    	data = "{}[]()(()[])";
    	result = check_integrity(data); // true
     
    	data = "((()())())";
    	result = check_integrity(data); // true
     
    	data = "(((()))(";
    	result = check_integrity(data); // false
     
    	data = "{[()]}{[()]}";
    	result = check_integrity(data); // true
     
    }

    Feedback приветсвуется.

  4. Студент says:
    static bool CheckIntegrity(string src)
        {
            int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0;
    
            for (int i = 0; i  c1) break; }
                else if (src[i] == ']') { c5++; if (c5 > c2) break; }
                else if (src[i] == '}') { c6++; if (c6 > c3) break; }
            }
    
            if (c1 == c4 && c2 == c5 && c3 == c6)
                return true;
            return false;
        }
    

    Полноценно работает из 3-я видами скобок.
    Предусмотрена проблема, если сперва идет закривающая скобка и у нее нету открывающей, что должна стоять перед ней где-то.

  5. Студент says:

    Извините, выше написанный код криво отправился !!!

    static bool CheckIntegrity(string src)
        {
            int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0;
     
            for (int i = 0; i  c1) break; }
                else if (src[i] == ']') { c5++; if (c5 > c2) break; }
                else if (src[i] == '}') { c6++; if (c6 > c3) break; }
            }
     
            if (c1 == c4 && c2 == c5 && c3 == c6)
                return true;
            return false;
        }

    Полноценно работает из 3-я видами скобок.
    Предусмотрена проблема, если сперва идет закривающая скобка и у нее нету открывающей, что должна стоять перед ней где-то.

  6. Студент says:

    Еще раз извините, код отправляется криво и много кода пропускает. Попробую просто код отправить
    static bool CheckIntegrity(string src)
    {
    int c1 = 0, c2 = 0, c3 = 0, c4 = 0, c5 = 0, c6 = 0;
    for (int i = 0; i c1) break; }
    else if (src[i] == ‘]’) { c5++; if (c5 > c2) break; }
    else if (src[i] == ‘}’) { c6++; if (c6 > c3) break; }
    }
    if (c1 == c4 && c2 == c5 && c3 == c6)
    return true;
    return false;
    }

  7. Студент says:

    Всё ровно глючит … настройте пожалуйста корректность отправки коду …

  8. Anonymous says:

    Решение со стеком

    public class Brace
        {
            public static bool Check(string checkString)
            {
                var braceStack = new Stack<char>();
     
                foreach (var chr in checkString)
                {
                    if (chr == '(' || chr == '{' || chr == '[')
                    {
                        braceStack.Push(chr);
                        continue;
                    }
     
                    if (chr != ')' && chr != '}' && chr != ']') continue;
     
                    char brace;
     
                    if (braceStack.Count > 0)
                        brace = braceStack.Pop();
                    else
                        return false;    
     
                    switch (brace)
                    {
                        case '(':
                            if (chr != ')') return false;
                            break;
                        case '{':
                            if (chr != '}') return false;
                            break;
                        case '[':
                            if (chr != ']') return false;
                            break;
                    }
                }
     
                return braceStack.Count == 0;
            }
        }
    }
  9. Anonymous says:

    Добрый день. Я че-то не пойму. Вроде мое решение тоже работает. Или нет?

            static bool IsCorrect(string str)
            {
                if (str == "") return true;         
                int Ind = str.IndexOf("()");
                if (Ind == -1) Ind = str.IndexOf("[]");
                if (Ind == -1) Ind = str.IndexOf("{}");
                if (Ind != -1)
                {
                    return IsCorrect(str.Remove(Ind, 2));
                }
                return false;
            }
    • Галина says:

      Да, работает. Алгоритмически решение красивое, рекурсия использована для очевидно рекурсивной структуры. Получилось компактно и очень наглядно. Но производительность… Из всяких теоретических соображений, она должна быть ниже, чем у итеративного подхода. Так и вышло. Попробуйте такой тест, чтобы это ощутить.

                  string str = "[([])([])]";
                  bool b;
                  for (int i = 0; i < 5000000; i++)
                  {
                     b = IsCorrect(str); 
          //vs Check(str) - итерационный вариант из поста выше;
                    // if (i % 10000 == 0) Console.WriteLine(i);
                  }

      Возможно, будет быстрее, если поиграться с типом StringBuilder, string, как известно, в C# не мутирует, что порождает проблемы производительности в предсказуемых местах.

  10. Евгений says:

    Вот мой вариант.

     static bool CheckIntegrity(string src)
            {
                int c = 0; // (
                int f = 0; // {
                int r = 0; // [
                char ch;
                for (int i = 0; i < src.Length; i++)
                {
                    if (c < 0 || f < 0 || r < 0) { return false; }
                    ch = src[i];
                    switch (ch)
                    {
                        case '(': { c++; break; }
                        case ')': { c--; break; }
                        case '{': { f++; break; }
                        case '}': { f--; break; }
                        case '[': { r++; break; }
                        case ']': { r--; break; }
                    }
                }
                if (c == 0 && f == 0 && r == 0) { return true; }
                return false;
            }

Оставить комментарий

Ваш адрес email не будет опубликован.


*