Stack-based behaviour of Regexes

Discussion in 'Microsoft VB .NET' started by Guest, Aug 2, 2004.

  1. Guest

    Guest Guest

    Can anyone help me with understanding the behaviour of a Regular Expression which is said to be like that of a stack?
    It says in the docs...

    "(?<group1-group2>) Balancing group definition. Deletes the definition of the previously defined group name2 and stores in group name1 the interval between the previously defined name2 group and the current group. If no group name2 is defined, the match backtracks. Because deleting the last definition of name2 reveals the previous definition of name2, this construct allows the stack of captures for group name2 to be used as a counter for keeping track of nested constructs such as parentheses. In this construct, name1 is optional."

    I don't understand that unfortunately. Can anyone explain that better, preferably with a simple example?

    Thanks!
     
    Guest, Aug 2, 2004
    #1
    1. Advertisements

  2. On Mon, 2 Aug 2004 05:31:05 -0700, Patty O'Dors
    <> wrote:
    in <>

    >Can anyone help me with understanding the behaviour of a Regular Expression which is said to be like that of a stack?
    >It says in the docs...
    >
    >"(?<group1-group2>) Balancing group definition. Deletes the definition of the previously defined group name2 and stores in group name1 the interval between the previously defined name2 group and the current group. If no group name2 is defined, the match backtracks. Because deleting the last definition of name2 reveals the previous definition of name2, this construct allows the stack of captures for group name2 to be used as a counter for keeping track of nested constructs such as parentheses. In this construct, name1 is optional."
    >
    >I don't understand that unfortunately. Can anyone explain that better, preferably with a simple example?
    >
    >Thanks!
    >


    This snippet doesn't have a lot of meaning when it's taken out of
    context as you've done. Provide a link to the entire document or
    at least provide more of the surrounding text if you really want
    a meaningful interpretation.

    ---
    Stefan Berglund
     
    Stefan Berglund, Aug 2, 2004
    #2
    1. Advertisements

  3. Guest

    Unforgiven Guest

    Patty O'Dors wrote:
    > Can anyone help me with understanding the behaviour of a Regular Expression which is said to be like that of a stack?
    > It says in the docs...
    >
    > "(?<group1-group2>) Balancing group definition. Deletes the definition of the previously defined group name2 and stores in group name1 the interval between the previously defined name2 group and the current group. If no group name2 is defined, the match backtracks. Because deleting the last definition of name2 reveals the previous definition of name2, this construct allows the stack of captures for group name2 to be used as a counter for keeping track of nested constructs such as parentheses. In this construct, name1 is optional."
    >
    > I don't understand that unfortunately. Can anyone explain that better, preferably with a simple example?
    >
    > Thanks!
    >
    >


    If your question is, "How do I evaluate a mathematical expression?" then
    here is probably a short enough answer to get you started.

    Mathematical engines can evaluate expressions using two stacks.

    Consider ( 7 – ( ( 5 * ( 4 + 7 ) ) + 9 ) ).

    - if a number was read, push it onto the number stack
    - if an operation was read, push it onto the character stack
    - if a left parenthesis was read, ignore it
    - if a right parenthesis was read

    * pop from number stack as second operand
    * pop from number stack as first operand.
    * pop the operation from the character stack
    * perform the operation on the two operands
    * push the result onto the number stack

    Once the expression is consumed, the character stack should be empty and
    the number stack should contain only one value: the final result.

    Of course it can get much more complicated because you would want to
    parse the expression so that if the expression that you're evaluating
    was typed in wrong, ie. mismatched parenthesis etc, then... you get the
    idea.


    HTH,

    Steve
     
    Unforgiven, Aug 2, 2004
    #3
  4. =?Utf-8?B?UGF0dHkgTydEb3Jz?=
    <> wrote in
    news::

    > Can anyone help me with understanding the behaviour of a Regular
    > Expression which is said to be like that of a stack? It says in
    > the docs...
    >
    > "(?<group1-group2>) Balancing group definition. Deletes the
    > definition of the previously defined group name2 and stores in
    > group name1 the interval between the previously defined name2
    > group and the current group. If no group name2 is defined, the
    > match backtracks. Because deleting the last definition of name2
    > reveals the previous definition of name2, this construct allows
    > the stack of captures for group name2 to be used as a counter
    > for keeping track of nested constructs such as parentheses. In
    > this construct, name1 is optional."
    >
    > I don't understand that unfortunately. Can anyone explain that
    > better, preferably with a simple example?


    Here's some code I previously posted showing how to use those regex
    constructs:

    http://groups.google.com/groups?hl=en&lr=&ie=UTF-
    8&threadm=Xns9413A56F813EDcrtimmonscrtimmonsin%40207.46.248.16&rnum=1
    &prev=/groups%3Fas_q%3Dtimmons%2520recursive%26safe%3Dimages%26ie%3DU
    TF-
    8%26as_ugroup%3D*dotnet*%26as_scoring%3Dd%26lr%3D%26num%3D100%26hl%3D
    en

    or

    http://tinyurl.com/62bm7


    --
    Hope this helps.

    Chris.
    -------------
    C.R. Timmons Consulting, Inc.
    http://www.crtimmonsinc.com/
     
    Chris R. Timmons, Aug 3, 2004
    #4
  5. > Have you been able to expand this to more than one characters? I have nexted
    > XML tags that I would like to do the same thing with. Here is my best guess
    > (it does not work). Basically the tag is <OPTIONAL> and the end tag is
    > </OPTIONAL>. These can be nested with other tags in between. The regex I have
    > shown below allows for attributes.


    Why not just use the MSXML DOM and XPath queries to find your data within the XML file? Are you just looking for <OPTIONAL> tags or
    something specific within them?
    Hope this helps,

    Mike


    - Microsoft Visual Basic MVP -
    E-Mail:
    WWW: Http://www.mvps.org/EDais/
     
    Mike D Sutton, Aug 30, 2004
    #5
  6. Guest

    Guest Guest

    I had thought of that and that will be one possible work-around. I would like
    to avoid bringing in the DOM for two reasons:

    1) I am concerned about the overhead. These are relatively short strings
    (most less than 1K) and the DOM seems overkill and costly in terms of cycles
    and memory for just these strings. Regex can be compiled and it just seems
    faster although I have not done benchmarks on it. I know there are some
    constructs in the DOM that are VERY costly. Simple things like counting
    elements were killing a web application that we had.
    2) I want to understand how to handle nested constructs using regular
    expressions. It seems to work OK for single character open and close entities
    like parenthesis but it should be extendable to entities greater than one
    character.

    I just need the start and end of a possibly nested structure. So for example

    <A> This is some text
    <OPTIONAL>This is some <OPTIONAL>optional text</OPTIONAL></OPTIONAL>
    <B>This is some B text
    <OPTIONAL>This is some more optional text </OPTIONAL>
    </A>

    For the first <OPTIONAL> tag I would like the index into the string where
    this begins and where the corresponding </OPTIONAL> tag ends (so the index
    would essentially point to the beginning of <B>). For the next <OPTIONAL> tag
    I would want the beginning and ending of that tag and content, and so forth.
    If regular expressions can be used to do nested parenthesis then can't a
    regular expression be put together to handle nested tags?

    Kevin

    "Mike D Sutton" wrote:

    > > Have you been able to expand this to more than one characters? I have nexted
    > > XML tags that I would like to do the same thing with. Here is my best guess
    > > (it does not work). Basically the tag is <OPTIONAL> and the end tag is
    > > </OPTIONAL>. These can be nested with other tags in between. The regex I have
    > > shown below allows for attributes.

    >
    > Why not just use the MSXML DOM and XPath queries to find your data within the XML file? Are you just looking for <OPTIONAL> tags or
    > something specific within them?
    > Hope this helps,
    >
    > Mike
    >
    >
    > - Microsoft Visual Basic MVP -
    > E-Mail:
    > WWW: Http://www.mvps.org/EDais/
    >
    >
    >
     
    Guest, Aug 31, 2004
    #6
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Prateek
    Replies:
    2
    Views:
    509
    Joao Santa Barbara
    Aug 14, 2003
  2. LedZep

    Stack question

    LedZep, Nov 24, 2003, in forum: Microsoft VB .NET
    Replies:
    8
    Views:
    231
    LedZep
    Nov 27, 2003
  3. ZorpiedoMan

    A stack/heap question

    ZorpiedoMan, Dec 2, 2003, in forum: Microsoft VB .NET
    Replies:
    11
    Views:
    296
    Jay B. Harlow [MVP - Outlook]
    Dec 2, 2003
  4. RA Scheltema

    increasing the stack size

    RA Scheltema, Jan 8, 2004, in forum: Microsoft VB .NET
    Replies:
    2
    Views:
    529
    RA Scheltema
    Jan 9, 2004
  5. Bob Day
    Replies:
    6
    Views:
    173
    Bob Day
    Jan 19, 2004
Loading...

Share This Page