Java正则表达式性能问题

Question

我正在尝试在Java中制作一个函数绘图程序，它涉及获取用户输入的要绘制的函数，解析它并将其绘制出来。例如，用户可能输入x ^ 2-y ^ 2，cos（x + y），log（x）-sqrt（y）等。该程序利用中缀二元操作符（+，-等）和一元操作符（cos，sqrt等）。

简而言之，为了评估一元操作符，我必须确保给定的表达式遵循单个一元操作符的格式。例如，cos（x），sqrt（x + y）和log（exp（y）-x）都符合这种格式，因为它们是带有某些表达式作为操作数的一元操作符；但是，像sin（x）* cos（y）和1 + log（x）这样的字符串不符合此格式。为了检查，我制作了一个正则表达式来匹配这种格式：

String unaryName = "((productlog)|(zeta)|(log)|(sqrt)|(cos)|(sin)|(tan)|(sec)|(csc)|(csc)|(abs)|(arccos)|(arcsin)|(arctan)|(arcsec)|(arccsc)|(arccot)|(gamma)|(exp))";

（这只是一个正则表达式，用于检查给定的字符串是否为预定义的一元操作符名称）

String unaryOperation = unaryName + "\\(([^\\(\\)]*(\\(.*\\))*[^\\(\\)]*)+\\)"

我会给你一个解释。这个正则表达式是在寻找一元运算符的名称。之后，它查找左括号。接着，它寻找一些不是括号的字符序列，然后再寻找以左括号开始、右括号结束的序列。后者防止类似"sin(x)+cos(y)"的字符串匹配。

据我观察，无论何时使用这个正则表达式都会得到期望的结果。但是，在使用它时会遇到一个问题。考虑以下情况：

String s = "cos(3) + sin(4)";
System.out.println(s.matches(unaryOperation));

显然，如果正则表达式起作用，那么它应该返回false，而它确实是这样的。 这个例子也是一样的：

String s = "cos(3.000) + sin(4)";
System.out.println(s.matches(unaryOperation));

从模式上来说，实际上没有发生什么变化。但是，将零逐个添加到数字3后，匹配似乎需要指数级的时间才能评估。对于我来说，12个零大约需要13秒钟。由于我的程序将在图表上绘制许多点，每次绘制时都必须计算成千上万个表达式，因此这是一个致命缺陷。

我已经找到了避免使用该正则表达式的方法，我的程序工作得非常好，但我仍然想知道：为什么这个正则表达式在处理大输入时需要如此长的时间，并且是否有任何方法可以更改正则表达式以解决此问题？

- MikeB

---

你为什么要使用正则表达式来解析表达式？ - Dave Newton

Answer 1

您可以使用此正则表达式

unaryName+"\\([^)]*(\\([^()]*\\))?[^(]*\\)"
                    ------------
                         |->starting from center.

在这里，我正在检查圆括号是否平衡。那应该解决你的问题！

- Anirudha

---

在使用String.matches时，您不需要锚点。 - Ted Hopp

谢谢！我唯一的问题是你的正则表达式没有匹配cos（x）或者没有嵌套括号的任何一元操作符，但很容易解决：unaryName+"\([^)]*(\([^()]\))[^(]*\)$" - MikeB

Answer 2

我怀疑问题在于您的表达式由于模式中间的.*而进行了大量回溯。尝试用勉强量词替换它：.*?或者更好的选择（如果我理解逻辑的话）是用[^\\)]*。

实际上，这不是解决问题的方法吗：

String unaryOperation = unaryName + "\\([^\\)]*\\)";

这个程序会查找一个名称，一个左括号，任意数量的非右括号字符，然后是一个右括号。这假设您不想匹配类似以下内容的东西：

"cos(3 * (4 + x))"

（这也不符合您的模式匹配）。

- Ted Hopp

---

我已经尝试过了，但仍需要10秒。虽然有一点改进，但仍不够。编辑-也尝试了第二个建议，也没有起作用。 - MikeB

我确实希望匹配像cos(3 + (4 + x))这样的事物，并且我相信我的原始正则表达式确实可以匹配到它们。 - MikeB

@MikeB - 我承认我错了；你的原始代码确实匹配嵌套括号。但是，它也会匹配不平衡的括号（例如 "cos(3 * (4 + 5)))" 或 "cos(3 * (4 - sin(6 - 2))"）。这可能不是你想要的。（正则表达式无法用于匹配任意深度的括号，并且匹配有限深度的复杂度随深度呈指数增长。） - Ted Hopp

这不是问题，如果有任何不匹配的括号，程序会在之前就捕获它们。当程序检查表达式是否为一元操作时，您可以假设该表达式在语法上是有效的。 - MikeB