Geek asks and answers

BASH / CSH / ZSH Extension Algorithm

If I have a string like

a/{b,c,d}/e

then I want to be able to produce this conclusion:

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

You get the idea. I need to implement this in C. I wrote brute force code that can handle one pair of curly braces (for example: /a/{b,c,d}/e/but if there are several pairs of curly braces in this case, for example, /a/{b,c}/{d,e}/fmy method will break. I would like to make a better approach.

I do not directly request the code, a hint of an efficient algorithm would be enough. I think that the task of parsing curly braces is repeated, and can we follow a recursive algorithm?

+3
source share
4 answers

Unix, Linux OS X, . man 3 glob , C. http://linux.die.net/man/3/glob, -.

, - , , . :

  • :
  • next_node: ,
  • sibling_node: ,
+2

, , . , .

:

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);
}

, , .

+2

- , , , . .

, . , , - node. node .

, :

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

:

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

, ["stringA", "stringB"] node, node. node, ( {} ) , ( ()).

, :

(
   ["/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"]
)

, , node, :

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

.

+1

I don't know about efficiency, but an intuitive way would be to use some form of recursion. The function should be able to find the first bracket. Say the first bracket contains N alternatives. Thus, the function creates N decompositions and calls itself recursively with each extension. Each “fork” continues to fork until it exhausts each bracket.

Does it help?

0
source

More articles:


All Articles