Finding Nested ( ) pairs
-
Hey Everyone, I'm looking for some ideas on how to find the indexes of nested parentheses () in a string. Basically the user is going to type a complex mathematical formula and i would like to know where all the nested ( and )'s are. I have considered RegEx, but i had some real trouble with the nested part and i dont want to remove that functionality) Any Ideas?
If at first you don't succeed ... post it on The Code Project and Pray.
-
Hey Everyone, I'm looking for some ideas on how to find the indexes of nested parentheses () in a string. Basically the user is going to type a complex mathematical formula and i would like to know where all the nested ( and )'s are. I have considered RegEx, but i had some real trouble with the nested part and i dont want to remove that functionality) Any Ideas?
If at first you don't succeed ... post it on The Code Project and Pray.
Have a look at Expresso[^] - it is a regex creation / testing tool. One of its pre-built expressions is:
\(
(?>
[^()]+
| \( (?<number>)
| \) (?<-number>)
)*
(?(number)(?!))
\)Which is a parentheses matcher. May be a good start for you?
No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced. This message is made of fully recyclable Zeros and Ones
-
Hey Everyone, I'm looking for some ideas on how to find the indexes of nested parentheses () in a string. Basically the user is going to type a complex mathematical formula and i would like to know where all the nested ( and )'s are. I have considered RegEx, but i had some real trouble with the nested part and i dont want to remove that functionality) Any Ideas?
If at first you don't succeed ... post it on The Code Project and Pray.
Hi, you probably want to create a parser for your expressions, not just some code about parentheses. So you first of all need a parser that understand identifiers, literals and operators, with operator precedence (identified by a value in a limited range, say add=0, sub=0, mul=1, div=1, etc up to 9). You need a little stack to hold operands, push operands as long as operator precedence is increasing, and popping operands and executing operators when precedence is decreasing or constant (and something special for right-to-left associativity as in a^b^c). Now there are two ways to extend to expressions with parentheses: 1. the easy and slightly more expensive one uses recursion: - create a method that implements the simple parser, and start scanning the input; - once you hit a left parenthesis, you know a subexpression is going to start, hence let your method call itself to parse that subexpression - once you hit a right parenthesis or end-of-input, return. 2. the other way basically implements one overall parser: - scan the expression left-to-right doing all the things your parser needs to do; - once you hit a left parenthesis, adapt the current state and increase the precedence value of all future operators causing them to get executed sooner than everything outside the parentheses. While (1) seems simpler than (2) when everything is fine, the recursive one becomes a little more complex if you want it to deal with mistakes properly: you have to unwind the recursions when invalid expressions are being fed, and you need to figure a way to generate proper error reporting, all of which is much simpler in a single overall parser. :)
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
-
Hey Everyone, I'm looking for some ideas on how to find the indexes of nested parentheses () in a string. Basically the user is going to type a complex mathematical formula and i would like to know where all the nested ( and )'s are. I have considered RegEx, but i had some real trouble with the nested part and i dont want to remove that functionality) Any Ideas?
If at first you don't succeed ... post it on The Code Project and Pray.
Are you sure you don't need to convert infix to postfix[^]?
-
Have a look at Expresso[^] - it is a regex creation / testing tool. One of its pre-built expressions is:
\(
(?>
[^()]+
| \( (?<number>)
| \) (?<-number>)
)*
(?(number)(?!))
\)Which is a parentheses matcher. May be a good start for you?
No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced. This message is made of fully recyclable Zeros and Ones
Thanks for the reply, this a start for sure. I could use something like this then just recursively go through the matches finding all the nested pairs. Thanks for the reply
If at first you don't succeed ... post it on The Code Project and Pray.
-
Hi, you probably want to create a parser for your expressions, not just some code about parentheses. So you first of all need a parser that understand identifiers, literals and operators, with operator precedence (identified by a value in a limited range, say add=0, sub=0, mul=1, div=1, etc up to 9). You need a little stack to hold operands, push operands as long as operator precedence is increasing, and popping operands and executing operators when precedence is decreasing or constant (and something special for right-to-left associativity as in a^b^c). Now there are two ways to extend to expressions with parentheses: 1. the easy and slightly more expensive one uses recursion: - create a method that implements the simple parser, and start scanning the input; - once you hit a left parenthesis, you know a subexpression is going to start, hence let your method call itself to parse that subexpression - once you hit a right parenthesis or end-of-input, return. 2. the other way basically implements one overall parser: - scan the expression left-to-right doing all the things your parser needs to do; - once you hit a left parenthesis, adapt the current state and increase the precedence value of all future operators causing them to get executed sooner than everything outside the parentheses. While (1) seems simpler than (2) when everything is fine, the recursive one becomes a little more complex if you want it to deal with mistakes properly: you have to unwind the recursions when invalid expressions are being fed, and you need to figure a way to generate proper error reporting, all of which is much simpler in a single overall parser. :)
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
Hey Luc, As per usual your answer is extremely well thought out and just all around a very good answer. However; I already have the validation and the execution of the formula figured out. The problem is that I am trying to add some visual indication of the operator precedence using a RTF textbox and some extremely simple syntax highlighting. I can find all the operators (even the ()) but the problem is that i would like to use a different colour for each pair of () in the formula. Thanks again for your input.
If at first you don't succeed ... post it on The Code Project and Pray.
-
Are you sure you don't need to convert infix to postfix[^]?
unfortunately not, nice article though. Thanks for the reply.
If at first you don't succeed ... post it on The Code Project and Pray.
-
Hey Luc, As per usual your answer is extremely well thought out and just all around a very good answer. However; I already have the validation and the execution of the formula figured out. The problem is that I am trying to add some visual indication of the operator precedence using a RTF textbox and some extremely simple syntax highlighting. I can find all the operators (even the ()) but the problem is that i would like to use a different colour for each pair of () in the formula. Thanks again for your input.
If at first you don't succeed ... post it on The Code Project and Pray.
Hi Adam, you're welcome. if all you need is locating parentheses and assigning some colors, I wouldn't use any Regex, because (1) I'm not really familiar with them and (2) I find them both powerful and cryptic, yielding hard-to-read code. So I would just search for the next string.IndexOfAny('(',')') and then check: for a '(' increment your color index and apply for a ')' apply color, then decrement color index, where color index is indexing an array of colors in round-robin fashion. Personally I don't like multiple colors for the same token, so what I usually do is choose only one color for all parentheses (or brackets or whatever comes in pairs), then use a second color for such token and the matching one when the cursor is right behind one. :)
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get. Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
