PC Review


Reply
Thread Tools Rate Thread

Stack-based behaviour of Regexes

 
 
=?Utf-8?B?UGF0dHkgTydEb3Jz?=
Guest
Posts: n/a
 
      2nd Aug 2004
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!


 
Reply With Quote
 
 
 
 
Stefan Berglund
Guest
Posts: n/a
 
      2nd Aug 2004
On Mon, 2 Aug 2004 05:31:05 -0700, Patty O'Dors
<(E-Mail Removed)> wrote:
in <(E-Mail Removed)>

>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
 
Reply With Quote
 
 
 
 
Unforgiven
Guest
Posts: n/a
 
      2nd Aug 2004
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
 
Reply With Quote
 
Chris R. Timmons
Guest
Posts: n/a
 
      3rd Aug 2004
=?Utf-8?B?UGF0dHkgTydEb3Jz?=
<(E-Mail Removed)> wrote in
news:(E-Mail Removed):

> 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/
 
Reply With Quote
 
Mike D Sutton
Guest
Posts: n/a
 
      30th Aug 2004
> 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: (E-Mail Removed)
WWW: Http://www.mvps.org/EDais/


 
Reply With Quote
 
=?Utf-8?B?S2V2aW4gQnVydG9u?=
Guest
Posts: n/a
 
      31st Aug 2004
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: (E-Mail Removed)
> WWW: Http://www.mvps.org/EDais/
>
>
>

 
Reply With Quote
 
 
 
Reply

Thread Tools
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
regexes with balancing group definitions Arnshea Microsoft C# .NET 1 6th Oct 2007 08:29 PM
Stack-based behaviour of Regexes =?Utf-8?B?UGF0dHkgTydEb3Jz?= Microsoft C# .NET 5 31st Aug 2004 05:07 AM
Regexes =?Utf-8?B?UGF0dHkgTydEb3Jz?= Microsoft C# .NET 1 25th Aug 2004 12:58 PM
stack based behaviour of regexes =?Utf-8?B?UGF0dHkgTydEb3Jz?= Microsoft C# .NET 0 24th Aug 2004 09:47 AM
stack based behaviour of regexes =?Utf-8?B?UGF0dHkgTydEb3Jz?= Microsoft Dot NET Framework 0 24th Aug 2004 09:47 AM


Features
 

Advertising
 

Newsgroups
 


All times are GMT +1. The time now is 11:32 PM.