控制平衡括号
假设我们有一个包含不同括号的字符串(在这个上下文中用括号表示我是指(
, [
和{
),字符串也可以包含其他内容,如{[balanced(parenthesis)]}
但其余的内容将在很大程度上被忽略是否可以使用正则表达式来控制所有不同的括号:
- “关闭” ,即每个“开放”括号与“结束”括号匹配,并且
- 在字符串中的正确位置?
事实certificate,这个问题已由Kobi在他的博客文章中解决。 为了简单地平衡不同类型的括号,解决方案非常简单和优雅,而不是像这个问题中的答案一样疯狂, 这个问题具有更复杂的语法。
让我引用下面博文的重要部分:
[…]谁说我必须把我匹配的东西推到堆栈? 如果想将任意字符串推入堆栈怎么办? 当我看到一个开放的支架时,我真的想要一个结束支架 – 但我怎么能这样呢?
诀窍是使用前瞻:找到我想要推送的角色的下一个匹配项,然后推送它:
{(?=.*?(
})) 接下来,当我想匹配一个右大括号时,我已经在堆栈中拥有正确的一个。 使用这种方法,这里是一个匹配令牌的正则表达式,匹配3个不同类型的平衡括号:
( [^(){}\[\]]+ | \( (?=[^)]* (?
\) ) ) | \[ (?=[^\]]* (? \] ) ) | \{ (?=[^}]* (? \} ) ) | \k (?<-Stack>) )+? (?(Stack) (?!)) 当然,这种方法确实有局限性 – 您可能找不到想要推送的角色(这可能是一件好事 – 它可以让您提前失败)。 如果你想平衡比常量字符串更复杂的东西,它也会变得更加棘手,但那是另一个主题。
使用下面的正则表达式可以做到这一点,尽管有点难看。
这是匹配的正则表达式而不是validation正则表达式,但您可以通过在开头和结尾添加锚点来添加锚点以将其转换为validation。
(?: (?>[^(){}\[\]]+) | (? (?=(?\())(?)(?)\(| (?=(?\{))(?)(?)\{| (?=(? \[))(?)(?)\[ ) | (?: (?<-open> (?!\k)\} | (?!\k)\) | (?!\k)\] ) (?<-mr>)(?<-mc>)(?<-ms>) ) )+(?(open)(?!))
由于我们无法读取顶层堆栈,因此我们必须通过3个捕获组mr
, mc
和ms
来模拟它。 mr
, mc
, ms
和open
中的项目数始终相同。 当堆栈open
不为空时,3个捕获组中只有一个包含相应的开放括号,另外2个捕获空字符串。 非空字符串捕获组始终是堆栈顶部的括号类型。
这允许我们通过声明相应的捕获组不能匹配来匹配相应的右括号,例如(?!\k
。 我们知道该组不能为空(因为它必须首先通过检查(?<-open>)
)。 只剩下2个案例:
- 如果堆栈顶部是空字符串,则反向引用将始终匹配,并且断言始终失败。
- 如果堆栈顶部包含相应的左括号,则反向引用将失败,并且断言成功,我们继续匹配结束括号。
不,您刚才描述的语言不是常规语言,因此正则表达式不适合解决该问题。 您需要使用比正则表达式更强大的lexing /解析工具。
如果您要做的只是匹配括号,请尝试以下代码:
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(); 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; } }
您需要做的就是调用ValidateString()
方法,并将要传递的字符串传递给它。 它将测试不匹配的括号(3种不同的类型, []
, ()
, {}
)并测试以确保括号在正确的位置关闭(从我的3个测试字符串中可以看到)。 如果有效则返回true
,否则返回false
。
它的工作原理是该函数首先创建一个Stack
对象。 它遍历字符串中的每个字符。 如果找到一个开括号,它会将该支架推到堆栈,并将该支架的计数器增加1。 如果它找到一个右括号,它会从堆栈弹出开始括号,如果它们匹配,它会减少我们的括号计数器。
迭代完每个字符后,它会测试每个不同类型支架的计数器,如果所有三个都是0
,那么我们就知道它的平衡/匹配正确了!
小提琴