Assuming we have a string containing different parentheses (by parentheses in this context I mean (, [, and { ) the string could also contain other content like so {[balanced(parenthesis)]} but the rest of the content will largely be ignored. Would it be possible to use regular expression to control that all different parenthesis are:
It is possible to do this with the regex below, albeit a bit ugly.
This is a matching regex rather than a validation regex, but you can add anchor to turn it into a validation one by adding anchors at the beginning and the end.
(?:
(?>[^(){}\[\]]+)
|
(?<open>
(?=(?<mr>\())(?<mc>)(?<ms>)\(|
(?=(?<mc>\{))(?<mr>)(?<ms>)\{|
(?=(?<ms>\[))(?<mc>)(?<mr>)\[
)
|
(?:
(?<-open>
(?!\k<mc>)\}
|
(?!\k<mr>)\)
|
(?!\k<ms>)\]
)
(?<-mr>)(?<-mc>)(?<-ms>)
)
)+(?(open)(?!))
Since we can't read the top stack, we would have to emulate it by the 3 capturing groups mr, mc and ms. The number of items in mr, mc, ms and open are always the same. When the stack open is not empty, only one out of the 3 capturing groups contains the corresponding opening bracket, the other 2 capture an empty string. The non-empty string capturing group is always the type of the bracket at the top of the stack.
This allows us to match the corresponding closing bracket by asserting that the corresponding captured group can't be matched, e.g. (?!\k<mc>)\}. We know that the group can't be empty (since it has to pass the check on (?<-open>) first). There are only 2 cases left:
It turns out this problem has been solved by Kobi in this blog post of his. For simply balancing different types of brackets, the solution is quite simple and elegant, and not as crazy as the answers in this question, which has a more complex grammar.
Let me quote the essential part of the blog post below:
[...] who says I must push what I matched to the stack? What if wanted to push an arbitrary string to the stack? When I see an open bracket I really want to push a closing bracket – but how can I?
The trick is to use a look-ahead: find the next occurrence of the character I want to push, and push it:
{(?=.*?(<Stack>}))Next, when I want to match a closing brace, I already have the right one in stack. Using this approach, here’s a regex that matches tokens with matching balanced parentheses of 3 different typed:
( [^(){}\[\]]+ | \( (?=[^)]* (?<Stack> \) ) ) | \[ (?=[^\]]* (?<Stack> \] ) ) | \{ (?=[^}]* (?<Stack> \} ) ) | \k<Stack> (?<-Stack>) )+? (?(Stack) (?!))Of course, this approach does have limitations – you may not find the character you’d like to push (which might be a good thing – it allows you to fail early). It also gets much trickier if you want to balance something more complicated than constant strings, but that’s another subject.
No, the language you have just described the requirements of is not a regular language, and as such Regular Expressions are not suitable to solving that problem. You will need to use a more robust lexing/parsing tool than just regexes.
If all you are trying to do is match parenthesis, try this code out:
public class Program
{
public static void Main()
{
string testString1 = "{[balanced(parenthesis)]}";
string testString2 = "(test)[wrong bracket type)";
string testString3 = "(test)[Mismatched]((sdff)";
bool isValid1 = ValidateString(testString1);
bool isValid2 = ValidateString(testString2);
bool isValid3 = ValidateString(testString3);
if (isValid1)
Console.WriteLine("TestString1 is balanced correctly!");
else Console.WriteLine("TestString1 is NOT balanced properly!");
if (isValid2)
Console.WriteLine("TestString2 is balanced correctly!");
else Console.WriteLine("TestString2 is NOT balanced properly!");
if (isValid3)
Console.WriteLine("TestString3 is balanced correctly!");
else Console.WriteLine("TestString3 is NOT balanced properly!");
}
public static bool ValidateString(string testString)
{
int p1 = 0;
int p2 = 0;
int p3 = 0;
var lastOpener = new Stack<char>();
foreach (char c in testString)
{
if (c == '(') {
p1++;
lastOpener.Push(c);
}
if (c == '[') {
p2++;
lastOpener.Push(c);
}
if (c == '{') {
p3++;
lastOpener.Push(c);
}
try {
if (c == ')' && lastOpener.Pop() == '(')
p1--;
if (c == ']' && lastOpener.Pop() == '[')
p2--;
if (c == '}' && lastOpener.Pop() == '{')
p3--;
} catch { return false; }
}
if (p1 != 0 || p2 != 0 || p3 != 0)
return false;
return true;
}
}
All you need to do is call the ValidateString() method, passing it the string you want to test. It will test for mismatched brackets (3 different kinds, [], (), {}) and test to make sure the brackets are closed in the right spot (as you can see from my 3 test strings). It will return true if its valid, or false otherwise.
How it works is the function first creates a Stack object. It iterates through each character in the string. If it finds an opening bracket, it pushes that bracket to the stack and increments the counter for that bracket by one. If it finds a closing bracket, it pops the opening bracket from the stack and if they match, it decrements our bracket counter.
After iterating through each character, it tests the counter of each different type of bracket and if all three are 0, then we know its balance/matched properly!
