将括号表达式与正则表达式匹配

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.

Answer 2

既然你通过这一切迭代,我说你还是应该做,但去周围的其他方式.找到最大的paranthetical表达式子集,而不是最大的子集:

(\([^(]+\))

评估它们,并用它们的值替换它们,即,第一次,匹配将是(3 / 4),(3 * 2)和(1 + 2).将这些替换为0,75,6并3分别给出一个新字符串:

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

然后你迭代它,直到没有更多的括号表达式,自下而上而不是自上而下(就像你手动解决这样的任务!)

除此之外,我同意所有其他人正是你所要求的不应(事实上也不能)用正则表达式来完成.但是这个问题可以通过这个涉及正则表达式的解决方案来解决.