使用正则表达式匹配括号表达式

Question

我正在使用正则表达式开发一个数学表达式解析器，并尝试添加对括号的支持。

我的解析器工作方式如下：

function parse_expression(expression){
    Find parenthetical expressions
    Loop through parenthetical expressions, call parse_expression() on all of them
    Replace parenthetical expression with value of expression
    Find value of expression
    Return value
}

因为它是递归的，所以我需要找到最外层的括号表达式。例如，如果我正在解析字符串“(5 + (4 + (3 / 4) + (3 * 2) + 2)) + (1 + 2)”，我希望找到表达式“5 + (4 + (3 / 4) + (3 * 2) + 2)”和“1 + 2”。如何使用正则表达式实现这一点？

我现在有一个正则表达式（“\(([^\)]+)\)”），它只会返回“5 + (4 + (3 * 2”这样的结果，而不是完整的第一个表达式，并且没有得到第二个表达式。

有什么想法吗？

谢谢，

凯尔

- Kyle

Answer 1

很不幸，任意嵌套的括号语言并不是正则的，因此不能使用正则表达式进行匹配。

具体来说，正则语言是可以使用有限自动机解析的语言，它具有（集合）有限数量的状态。要匹配任意嵌套的括号集需要任意数量的状态，以计算括号在过程中的数量。

大多数“正则表达式”库（特别是Perl的）并不严格匹配正则语言，但它们仍然有这个限制。

解决您的问题最直接的方法是递归下降解析器。一种低效的方法是只需查看字符串，同时计算括号，以找到要进入的子字符串。

如果坚持要求操作被括号括起来，例如只允许(1+2)+3或1+(2+3)，而不是1+2+3，那么您的解析器也会更简单。

- Andrew Aylett

Answer 2

既然你要遍历所有内容，我认为你仍然应该这样做，但是反过来。找到最小的括号表达式子集，而不是最大的：

(\([^(]+\))

评估它们并用它们的值替换，即第一轮匹配将是(3 / 4)，(3 * 2)和(1 + 2)。将其分别替换为0.75，6和3，得到一个新字符串：

(5 + (4 + 0,75 + 6 + 2)) + 3

然后，你需要迭代这个过程，直到没有括号表达式为止，从下往上工作（就像你手动解决这种任务一样！）

除此之外，我同意所有其他人的看法，确切地说，你所要求的内容不应该（实际上也不能）使用正则表达式来完成。但是，你的问题可以通过这个涉及正则表达式的解决方案来解决。

- David Hedlund

---

这是一个聪明的解决方案。它需要大量的字符串操作，并且需要经常重新解析数字，但除此之外应该可以正常工作。 - Daniel Yankowsky

嘿，在我的测试中它是可以的，我之前没有注意到。为了性能考虑，我会考虑使用这个 (\([^()]+\))，这也可以解决那个问题。但是，无论哪种方法对你来说都可以 :) 祝你好运解决剩下的问题，我想一个可用的正则表达式可能不足以解决这个问题。 - David Hedlund

谢谢，那个正则表达式完美地解决了问题。这恰恰说明了寻求编程帮助之所以如此困难的原因：对于提问者和回答者来说，情况似乎从来都不一样。 - Kyle

嘿，这让我失眠了。如果你认为我破坏了这个任务的乐趣，那就不要读代码，但我成功地做到了：http://pastebay.com/78093 这是一个能解决很多问题的JavaScript。它可以在一个括号表达式中处理多个操作（例如(1+5/2)）。基本上唯一不能处理的事情是，如果你写 2(1+2) 它就无法工作（正确的方式应该是 推断 2*(1+2)）。 - David Hedlund

好的，实际上在阅读这篇文章后不久我就完成了我的算法。它是用Objective-C编写的，但我决定将其移植到JavaScript进行比较（http://pastebay.com/78117）。我的算法必须处理分数、小数和整数，所以它有点复杂。此外，我的算法最初并不是用JavaScript编写的，我也没有花太多时间来清理它，所以它看起来有点奇怪。我采用了更多的解析器方法，使用值和操作符栈来保存我的操作。它通过字符串替换来处理`2(1+2)`，然后再进行解析。可能还可以进行一些优化，但它似乎能够工作。 - Kyle

Answer 3

如果我没错的话，这种语言不是正则的，因此使用正则表达式做这件事情在理论上是不可能的。

- Thomas

Answer 4

你应该使用解析器(parser)。让它遍历字符串，并在每次遇到 "(" 时增加括号计数，每次遇到 ")" 时减少计数。当下一次计数为零时，你就找到了最外层括号表达式的范围。

- Kenny Winker

---

我曾考虑过这个，但我认为David Hedlund的解决方案更适合我的问题。 - Kyle

好的，我自己也更喜欢他的解决方案 :D - Kenny Winker