Stack-based behaviour of Regexes

[Patty O'Dors]

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!

[Stefan Berglund]

On Mon, 2 Aug 2004 05:31:05 -0700, Patty O'Dors
<Pa********@discussions.microsoft.com> wrote:
in <72**********************************@microsoft.co m>

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

[Unforgiven]

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

[Chris R. Timmons]

=?Utf-8?B?UGF0dHkgTydEb3Jz?=
<Pa********@discussions.microsoft.com> wrote in
news:72**********************************@microsof t.com:

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%402 07.46.248.16&rnum=1
&prev=/groups%3Fas_q%3Dtimmons%2520recursive%26safe%3Dima ges%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/

[Mike D Sutton]

> 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: ED***@mvps.org
WWW: Http://www.mvps.org/EDais/

[Kevin Burton]

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: ED***@mvps.org
WWW: Http://www.mvps.org/EDais/