Алгоритм расширения скобок в стиле BASH / CSH / ZSH - PullRequest
Новая
       16

Алгоритм расширения скобок в стиле BASH / CSH / ZSH

3 голосов
/ 03 июня 2011

Если у меня есть строка типа 

a/{b,c,d}/e

тогда я хочу быть в состоянии произвести этот вывод: 

a/b/e
a/c/e
a/d/e

Вы поняли идею. Мне нужно реализовать это на языке C. Я написал код типа «грубой силы», который был способен анализировать одну пару скобок (например: /a/{b,c,d}/e/, но если есть несколько пар скобок, например /a/{b,c}/{d,e}/f в этом случае мой метод сломается. Я хотел бы выбрать лучший подход.

Я не запрашиваю код напрямую, достаточно лишь намека на эффективный алгоритм. Я думаю, что задача разбора скобок повторяется, и мы могли бы следовать рекурсивному алгоритму?

Ответы [ 4 ]

2 голосов
/ 03 июня 2011

То, что вы показываете здесь, на самом деле не рекурсивно.Если бы вы могли вкладывать скобки, то это было бы рекурсивно.

В основном то, что у вас есть, это простая грамматика: 

thing ::= element { "/" element }*
element ::= symbol || list
list ::= "{" symbol { "," symbol }* "}"
symbol ::= [a-z]+

Это язык грамматики с манжетой.* означает «ноль или более», + означает «1 или более».Довольно часто встречается.

Итак, вам нужен простой токенизатор, который группирует ваши символы и в основном выделяет знаки препинания.

Затем простой синтаксический анализатор 

parseThing() {
    Element e = parseElement();
    while (nextToken != null) {
        Slash s = parseSlash();
        e = parseElement():
    }
}

Slash parseSlash() {
    Token t = peekNextToken();
    if (t.getText().equals("/")) {
        return new Slash();
    }
    throw "expected a '/' but got a " + t;
}

Element parseElement() {
    Token t = peekNextToken();
    if (t.isSymbol()) {
        return parseSymbol();
    }
    if (t.isOpenCurly()) {
        return parseList());
    }
    thrown "Syntax error, wanted a symbol or { and got " + t;
}

List parseList() {
    List l = new List();
    Token t = peekNextToken();
    if (t.isOpenCurly()) {
        consumeNextToken();
        Symbol s = parseSymbol();
        l.add(s);
        t = peekNextToken();
        while (t.isComma()) {
            consumeNextToken();
            s = parseSymbol();
            l.add(s);
            t = peekNextToken();
        }
        if (!t.closeCurly()) {
            throw "expected close of list, but got " + t;
        }
        consumeNextToken();
     } else {
         throw "expected start of list but got " + t;
     }
     return l;
}

Symbol parseSymbol() {
    Token t = peekNextToken();

    if(!t.isSymbol()) {
        throw "expected symbol, got " + t;
    }
    consumeNextToken();
    return new Symbol(t);
}

Thisявляется неполным и высокого уровня, но дает вам представление о том, как вы могли бы сделать это.

2 голосов
/ 03 июня 2011

Если вы работаете в любой системе Unix, Linux или OS X, для этого есть встроенная функция библиотеки. man 3 glob расскажет вам о том, как позвонить с C. Или вы можете посетить http://linux.die.net/man/3/glob, чтобы найти онлайн документацию.

Если вы хотите свернуть свой собственный, простой способ - сначала просканировать строку и построить промежуточную структуру данных, а затем рекурсивно пройтись по этой структуре данных, печатая строки. Эта структура данных может быть построена из структур со следующими полями:

  • текст: указатель на фрагмент строки
  • next_node: указатель на то, что следует за этим текстом при печати
  • sibling_node: указатель на следующий выбор, который может быть сделан вместо этого
1 голос
/ 03 июня 2011

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

Вы можете написать анализатор рекурсивного спуска, чтобы преобразовать текст в дерево.Сделайте узлы листа строк, которые содержат эту строку и соответствующую пару фигурных скобок, внутренним узлом.Каждый листовой узел может содержать более одной строки.

Например, это: 

/a/{b,c}/{d,e{f,g,h}}/i

может стать: 

(
   ["/a/"]
   {
      ( ["b"] )
      ( ["c"] )
   }
   ["/"]
   {
      ( ["d"] )
      (
         ["e"]
         {
            ( ["f"] )
            ( ["g"] )
            ( ["h"] )
         }
      )
   }
   ["i"]
)

Попробуйте рассматривать его как деревогде ["stringA", "stringB"] обозначает листовой узел, а соответствующая пара фигурных скобок представляет внутренний узел.Существует 2 типа внутреннего узла, один из которых может выбирать между одной из альтернатив (я использую {} в этом примере) и один, который объединяет все комбинации (здесь я использую ()).

Итаквышеприведенное дерево будет выглядеть так: 

(
   ["/a/"]
   {
      ["b"]
      ["c"]
   }
   ["/"]
   {
      ["d"]
      (
         ["e"]
         {
            ["f"]
            ["g"]
            ["h"]
         }
      )
   }
   ["i"]
)

, затем 

(
   ["/a/"]
   ["b", "c"]
   ["/"]
   {
      ["d"]
      (
         ["e"]
         ["f", "g", "h"]
      )
   }
   ["i"]
)

, затем 

(
   ["/a/"]
   ["b", "c"]
   ["/"]
   {
      ["d"]
      ["ef", "eg", "eh"]
   }
   ["i"]
)

, затем 

(
   ["/a/"]
   ["b", "c"]
   ["/"]
   ["d", "ef", "eg", "eh"]
   ["i"]
)

и, наконец,у вас получится один листовой узел, представляющий собой все комбинации: 

["/a/b/di", "/a/b/efi", "/a/b/egi", "/a/b/ehi",
 "/a/c/di", "/a/c/efi", "/a/c/egi", "/a/c/ehi"]

Тогда вы можете довольно просто распечатать его.

0 голосов
/ 03 июня 2011

Не знаю, насколько эффективен, но интуитивно понятный способ - использовать некоторую форму рекурсии Функция должна быть в состоянии найти первую фигурную скобку. Скажем, первая скобка содержит N альтернатив. Таким образом, функция производит N расширений и рекурсивно вызывает себя при каждом расширении. Каждая «вилка» продолжает разветвляться, пока не исчерпает каждую скобу.

Это помогает?

...