473,320 Members | 2,164 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Stack-based behaviour of Regexes

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 16 '05 #1
5 1404
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 16 '05 #2
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 16 '05 #3
=?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 16 '05 #4
> 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 16 '05 #5
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 16 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

15
by: Andrew | last post by:
Last night I was reading about implementing my own stack. The example given pushes items on and off the stack at the start and end of each procedure (ie. in a std module). What's not so clear is...
14
by: Kevin Grigorenko | last post by:
Hello, I couldn't find an obvious answer to this in the FAQ. My basic question, is: Is there any difference in allocating on the heap versus the stack? If heap or stack implementation is not...
8
by: Ben | last post by:
Hi all, I implemented a stack in C++ in 2 different ways and I'd like to know which approach is better than the other.. and if there is any difference between the two? I'd also like to know if...
2
by: news.tkdsoftware.com | last post by:
Aside from comp.compilers, is there any other forum, newsgroup or medium where I can post questions concerning the development of a byte code compiler & virtual stack machine? --
4
by: anonymous | last post by:
Thanks your reply. The article I read is from www.hakin9.org/en/attachments/stackoverflow_en.pdf. And you're right. I don't know it very clearly. And that's why I want to understand it; for it's...
8
by: LedZep | last post by:
What up everyone, I have to write a program that uses a stack to determine whether a string is a palindrome (a string that is spelled identically backward and forward). The program has to...
4
by: alisaee | last post by:
plz check what i have made wrong what is requierd her is to creat class queue and class stack and run the push,pop operation . #include<iostream.h> #include<conio.h> #include<stdio.h> class...
1
by: alfie27 | last post by:
I currently have a working program that is a stack that stores integers. Now i have to convert it to store strings instead of integers. I have been working on this for hours and just keep getting...
11
by: tom | last post by:
Hi! Im new to Python and doing exercise found from internet. It is supposed to evaluate expression given with postfix operator using Stack() class. class Stack: def __init__(self): self.items...
9
by: Tarique | last post by:
Hello all.I am trying to implement a stack which can store either integer or float values. The code is given below: #include<stdio.h> #include<stdlib.h> #include<string.h> #define...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.