Java regular expression performance issue

Question

I am trying to make a function graphing program in Java, and it involves taking a user's input for the function which will be graphed, parsing it, and graphing it. For example, the user might enter in x^2 - y^2, cos(x + y), log(x) - sqrt(y), etc. The program makes use of both infix binary operations (+, -, etc.) and unary operations (cos, sqrt, etc.).

In short, in order to evaluate the unary operations, I must make sure that a given expression follows the format of a single unary operation. For example, cos(x), sqrt(x + y), and log(exp(y) - x) all fit this format, since they are unary operations with some expression as their operand; however, strings such as sin(x)*cos(y) and 1 + log(x) do not follow this format. In order to check, I made a regular expression for this format:

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

(this is just a regex to check if a given string is a name for a predefined unary operation)

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

I'll give an explanation. This regex is looking for the name of one of the unary operations. After that, it looks for a left-parenthesis. After that, it looks for some sequence of characters which are not parentheses, and then some sequence which begins with a left parenthesis and ends with a right parenthesis. The latter prevents a String such as "sin(x) + cos(y)" from matching.

This regular expression always gives desired results, as far as I can tell. However, in its use, one problem arises. Consider this situation:

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

Obviously, if the regex works, this should return false, which it does. The same would be true with this example:

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

Nothing really changed, pattern-wise. However, successively adding zeroes to the 3, the match seems to take exponentially longer to evaluate. For me, 12 zeroes takes about 13 seconds. Since my program will be plotting many points on a graph, it will have to calculate thousands of expressions every time it graphs something, so this is a fatal flaw.

I've already found a way around having to use this regular expression and my program works quite nicely, but I would still like to know: why does this regular expression take so long to work for large inputs, and is there any way to change the regex to fix this issue?

Why are you parsing expressions with regular expressions?

Dave Newton
– Dave Newton

2013-01-03 03:54:31 +00:00
Commented Jan 3, 2013 at 3:54 — Dave Newton
– Dave Newton, Commented Jan 3, 2013 at 3:54

Anirudha · Accepted Answer · 2013-01-03 04:27:44Z

1

You can use this regex

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

Here I am checking whether the round brackets are properly balanced ..That should solve your problem!

edited Jan 3, 2013 at 4:27

answered Jan 3, 2013 at 4:14

Anirudha

32.9k8 gold badges71 silver badges90 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ted Hopp Over a year ago

You don't need the anchors when using String.matches.

MikeB Over a year ago

Thanks! My only qualm was that your regex didn't match cos(x), or any unary operation without nested parentheses, but it was easy to fix: unaryName+"$[^)]*(\([^()]*$)*[^(]*\)$"

Ted Hopp · Accepted Answer · 2013-01-03 03:50:35Z

0

I suspect the problem is that your expression is doing a lot of backtracking because of the .* in the middle of the pattern. Try replacing it with a reluctant quantifier: .*? or, better yet (if I understand the logic), with [^\\)]*.

Actually, wouldn't this do the trick:

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

This looks for a name, a left parenthesis, any number of non-right-parenthesis characters, and then a right parenthesis. This assumes that you don't want to match things like

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

(which your pattern also won't match).

edited Jan 3, 2013 at 3:50

answered Jan 3, 2013 at 3:42

Ted Hopp

235k48 gold badges412 silver badges533 bronze badges

4 Comments

MikeB Over a year ago

I did that, and it still takes 10 seconds. A minor improvement, but still not sufficient. EDIT- Also tried the second suggestion, didn't work either.

MikeB Over a year ago

I do want to match things like cos(3 + (4 + x)), and I do believe my original regex does match that.

Ted Hopp Over a year ago

@MikeB - I stand corrected; your original does match nested parens. However, it also matches unbalanced parens (such as "cos(3 * (4 + 5)))" or "cos(3 * (4 - sin(6 - 2))"). That's probably not what you want. (Regex can't be used to match parentheses to arbitrary depth, and the complexity of matching to bounded depth grows exponentially with the depth.)

MikeB Over a year ago

That's not an issue, if there are any mismatched parentheses then the program would have caught them beforehand. When the program is checking if the expression is a unary operation, you can assume the expression is syntactically valid.

Collectives™ on Stack Overflow

Java regular expression performance issue

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related