6

我正在尝试用 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 秒。由于我的程序将在图表上绘制许多点，因此每次绘制图形时都必须计算数千个表达式，所以这是一个致命的缺陷。

我已经找到了一种不必使用这个正则表达式的方法，并且我的程序运行得很好，但我仍然想知道：为什么这个正则表达式需要这么长时间才能处理大量输入，有什么方法可以改变正则表达式来解决这个问题？

4

2 回答 2

1

你可以使用这个正则表达式

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

在这里，我正在检查圆括号是否正确平衡..那应该可以解决您的问题！

于 2013-01-03T04:14:46.110 回答
0

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

实际上，这不是诀窍吗：

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

这会查找名称、左括号、任意数量的非右括号字符，然后是右括号。这假设您不想匹配类似的东西

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

（您的模式也不匹配）。

于 2013-01-03T03:42:31.827 回答