Правильность расстановки скобок (C#) – рефакторинг

Опубликовано Dec 11, 2012 в Массивы и строки, Рефакторинг и оптимизация | 3 коммент.

, , ,

Правильность расстановки скобок (C#) – рефакторинг

В предыдущем посте на эту тему уже приведено много решений.

Интересным оказалось последнее (от 11 декабря), основанное на использовании стека.

Вот его код.

public class Brace
    {
        public static bool Check(string checkString)
        {
            var braceStack = new Stack();
 
            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;
        }
    }

Общая оценка.  Идея использования структуры данных стек для этой задачи алгоритмически удачна и в целом код написан хорошо. Возникает вопрос: “Можно ли здесь что-то улучшить?” Вопрос, конечно, риторический, совершенству нет предела, но вот какие соображения могут иметь место по поводу подобных задач.

Что можно улучшить? Имеется явное  повторение кода через хардкод проверяемых символов. Хорошо, если это задачка с алгоритмом, который  вмещается на один экран. А если это промышленный код и разрабатывался какой-то длинный и сложный алгоритм с немалой стоимостью? При этом специальных символов, которые нужно расставлять в десятки мест по коду не три, а гораздо больше.  И все это нужно поддерживать для вызовов из многих мест, где возможны разные подмножества проверяемых символов на входе алгоритма. Стоит подумать, как от хардкода избавиться. Один из вариантов, например, такой.

public static bool CheckAllBraces(string checkString,
            char[] openBracesChars, char[] closeBracesChars)
        {
          var braceStack = new Stack();
 
          foreach (var chr in checkString)
          {
            if (Array.Exists(openBracesChars, element => element == chr))
            {
              braceStack.Push(chr);
              continue;
            }
 
            if (!Array.Exists(closeBracesChars, element => element == chr))
              continue;
 
            char brace;
 
            if (braceStack.Count > 0)
              brace = braceStack.Pop();
            else
              return false;
 
            if (Array.IndexOf(openBracesChars, brace) !=
                        Array.IndexOf(closeBracesChars, chr))
              return false;
          }
          return braceStack.Count == 0;
        }
    //ВЫЗОВ
     char[] openBracesChars  = {'(','[','{'};
     char[] closeBracesChars = { ')', ']', '}' };
 
     b = Brace.CheckAllBraces("((( ) ])( ))", openBracesChars, closeBracesChars);

Задача на собеседовании. Если подходить к задаче исходя из критериев собеседования, то второй вариант интереснее еще и потому, что кроме соображений, изложенных выше (они основные), в нем продемонстрировано использование некоторых более продвинутых средств, характерных именно для языка C#: знание класса Array его основных методов, а также простейший способ применения лямбда-выражений. Это как раз то, за что можно получить дополнительные баллы по владению базовым синтаксисом языка, по которому проходят собеседования.


Автор публикации:

3 Коммент. : “Правильность расстановки скобок (C#) – рефакторинг”

  1. galileo says:

    Вариант на C++.
    Если используется передача строки по значению, то необязательно явно использовать стек. Можно в качестве стека использовать саму строку, заведя переменную – указатель на вершину стека.

    В качестве дополнительного параметра в данной реализации предлагается использовать строку, в которой содержатся пары скобок, которые могут встречаться в строке. Открывающие скобки должны распологаться на четных позициях (нумерация с нуля), а сразу за ними, на нечетных позициях, должны распологаться соответствующие закрывающие скобки.

    class Brace
    {
        public:
     
        static bool Check(string checkString, string brackets)
        {
            int top = 0, pos;
            for (int i = 0; i < (int)checkString.size(); i++) {
                if ((pos = brackets.find(checkString[i])) == string::npos) return false;
                if (pos % 2 == 0) checkString[top++] = checkString[i];
                else if (!top || checkString[--top] != brackets[pos - 1]) return false;
            }
     
            return !top;
        }
    };
     
    int main() {
        Brace::Check("{(([]))[()]}", "[](){}");
        Brace::Check("()(()))", "()");
        return 0;
    }
  2. с++

     

    #pragma XAI_116

    #include
    #include
    #include

    using namespace std;

    void stack_analyze(stack&my_stack_open,stack&my_stack_close);
    void show(stack
    &my_stack_open,stack&my_stack_close);

    int main()
    {
    setlocale(LC_ALL,”RUS”);
    cout < < "Hello world!" << endl << "Введи строку для провверки"< string text; getline(cin,text);
    stackmy_stack_open; stackmy_stack_close; int i = 0;
    const string open = “({["; const string close = ")}]“;

    while(i != (text.length() + 1 ) )
    {
    if(text[i] == open[0] || text[i] == open[1] || text[i] == open[2]) my_stack_open.push(text[i]);
    if(text[i] == close[0] || text[i] == close[1] || text[i] == close[2])
    {
    if((my_stack_open.size() == 0 ) || (my_stack_open.size() < = my_stack_close.size()))
    {
    cout<<"В вашей строке ошибка"< }
    else my_stack_close.push(text[i]);
    }
    i++;
    }

    stack_analyze(my_stack_open,my_stack_close);

    return 0;
    }

    void stack_analyze(stack&my_stack_open,stack&my_stack_close)
    {
    if((my_stack_open.size()) == (my_stack_close.size())) show(my_stack_open,my_stack_close);
    else cout< <"Ваша строка содержит ошибку";
    }

    void show(stack&my_stack_open,stack&my_stack_close)
    {
    char _o;
    char _c;
    cout< <"Колво open скобок - " < cout<<"Колво close скобок - " < for(int i = 1; i <= my_stack_open.size();i++)
    {
    _o = my_stack_open.top();
    my_stack_open.pop();
    _c = my_stack_close.top();
    my_stack_close.pop();
    if(_o == '(') if(_c == ')') continue; else {cout<<"cодержит ошибку";break;}
    if(_o == '{') if(_c == '}') continue; else {cout<<"cодержит ошибку";break;}
    if(_o == '[') if(_c == ']') continue; else {cout<<"cодержит ошибку";break;}
    }

    }

    85dd9cb5d1d1fc48bd2764fd91873fa4006

    • Здравствуйте Эдуард.

      В вашем коде присутствуют все типы ошибок, сложно выделить что-то одно.

      Выборочные комментарии:
      Алгоритм реализован неправильно (не работает на некоторых входных данных). Можно было бы написать значительно более простую реализацию, основанную на одном стеке.

      > if(text[i] == close[0] || text[i] == close[1] || text[i] == close[2])
      Следует использовать стандартные функции поиска символа.

      Слишком запутанное разделение на функции.

      Очевидно, что вы только начинаете программировать на С++.

      На данном этапе, наверное, единственный уместный совет – это не останавливаться, взять хорошую книжку по с++, прочитать, решить из нее все академические задачи. Далее можете взяться за задачи с нашего сайта или задачи уровня лабораторных работ ВУЗа.

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

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


*