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 + "\\(([^\\(\\)]*(\\(.*\\))*[^\\(\\)]*)+\\)"

説明します。この正規表現は、単項演算の1つの名前を探しています。その後、左括弧を探します。その後、括弧ではない文字のシーケンスを探し、次に左括弧で始まり右括弧で終わるシーケンスを探します。後者は、「sin（x）+ cos（y）」などの文字列が一致しないようにします。

この正規表現は、私が知る限り、常に望ましい結果をもたらします。ただし、その使用には1つの問題が発生します。この状況を考えてみましょう。

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 に答える