By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,524 Members | 1,593 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,524 IT Pros & Developers. It's quick & easy.

Stack-based behaviour of Regexes

P: n/a
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!
Nov 20 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
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
Nov 20 '05 #2

P: n/a
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
Nov 20 '05 #3

P: n/a
=?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/
Nov 20 '05 #4

P: n/a
> 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/
Nov 21 '05 #5

P: n/a
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/

Nov 21 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.