Problem z wydajnością wyrażenia regularnego Javy

Question

Próbuję utworzyć program do tworzenia wykresów funkcji w Javie i wymaga on wprowadzenia danych użytkownika dla funkcji, która będzie wykreślana, analizowania i tworzenia wykresów. Na przykład, użytkownik może wprowadzić x^2 - y^2, cos (x + y), log (x) - sqrt (y), itp. Program wykorzystuje zarówno binarne operacje infix (+, -, itp. .) i operacje jednoargumentowe (cos, sqrt itp.).

W skrócie, aby ocenić operacje jednoargumentowe, muszę upewnić się, że dane wyrażenie jest zgodne z formatem pojedynczej operacji jednoargumentowej. Na przykład cos (x), sqrt (x + y) i log (exp (y) - x) pasują do tego formatu, ponieważ są to operacje jednoargumentowe z pewnym wyrażeniem jako operandem; jednak łańcuchy takie jak sin (x) * cos (y) i 1 + log (x) nie podążają za tym formatem. W celu sprawdzenia, zrobiłem wyrażenia regularnego w tym formacie:

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

(to tylko regex do sprawdzenia, czy dany ciąg jest nazwa predefiniowanym jednoargumentowego eksploatacji)

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

I udzielę wyjaśnienia. To wyrażenie regularne szuka nazwy jednej z operacji unarnych. Potem szuka lewego nawiasu. Następnie szuka sekwencji znaków, które nie są nawiasami, a następnie sekwencji rozpoczynającej się od lewego nawiasu, a kończącej prawym nawiasem. Ten ostatni zapobiega dopasowywaniu ciągu znaków, takiego jak "sin (x) + cos (y)".

To wyrażenie regularne zawsze daje pożądane wyniki, o ile mogę powiedzieć. Jednak przy jego użyciu powstaje jeden problem. Rozważmy tę sytuację:

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

Oczywiście, jeśli regex działa, to powinno zwrócić wartość false, co robi. To samo byłoby prawdą w tym przykładzie:

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

Nic się nie zmieniło, jeśli chodzi o wzory. Jednak sukcesywnie dodając zera do 3, dopasowanie wydaje się zajmować wykładniczo dłużej. Dla mnie 12 zer trwa około 13 sekund. Ponieważ mój program będzie rysował wiele punktów na wykresie, będzie musiał obliczać tysiące wyrażeń za każdym razem, gdy coś wykreśli, więc jest to fatalna wada.

Już znalazłem sposób, aby używać tego wyrażenia regularnego, a mój program działa całkiem nieźle, ale nadal chciałbym wiedzieć: dlaczego to wyrażenie regularne zajmuje tak dużo czasu na pracę z dużymi nakładami, i czy istnieje jakikolwiek sposób zmienić wyrażenie regularne, aby rozwiązać ten problem?

Answer 1

Można użyć tego wyrażenia regularnego

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

Oto jestem sprawdzenie czy nawiasy okrągłe są prawidłowo zrównoważony ..That powinno rozwiązać Twój problem!

Answer 2

Podejrzewam, że problem polega na tym, że Twoja wypowiedź wykonuje lot wycofywania ze względu na .* w środku wzoru. Spróbuj zastąpić go niechętnym kwantyfikatorem: .*? lub jeszcze lepiej (jeśli rozumiem logikę), z [^\\)]*.

Faktycznie, nie będzie to rade:

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

To wygląda na imię, lewy nawias dowolną liczbę znaków non-prawy nawias, a następnie prawym nawiasie. Zakłada się, że nie chcesz dopasowywać rzeczy takich jak

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

(której twój wzór również nie będzie zgodny).