objective-c - 将括号表达式与正则表达式匹配

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"，它没有得到完整的第一个表达式并且它一秒钟也没有。

有什么想法吗？

谢谢，

凯尔

Answer 1

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

具体来说，常规语言是一种可以使用有限自动机解析的语言，它具有(集合)有限数量的状态。要匹配任意嵌套的一组括号，需要任意数量的状态，以便在括号经过时对其进行计数。

大多数“正则表达式”库(尤其是 perl 的)并不严格匹配正则语言，但它们仍然有此限制。

解决问题的最直接方法是递归下降解析器。一种低效的方法是只查看字符串，边走边数括号，以找出要下降到哪些子字符串。

如果您坚持将操作放在括号中，您还会发现您的解析器更简单，例如只允许 (1+2)+3 或 1+(2+3) 而不是 1+2+3。