Java - 使用正則表達式解析具有復係數的多項式

作爲計算Jordan正規形式的矩陣的個人項目的一部分，事實證明，我需要解析具有復係數的多項式，以減輕很多代碼的負擔。Java - 使用正則表達式解析具有復係數的多項式

（在柱的底部相關的代碼）

我要解析的多項式是以下形式的：

甲係數可以是實數，虛的或複雜的。
如果係數很複雜，則會用圓括號包裹起來。如果這些括號是主要係數，則不會在前面加上+或-。
如果係數是實數，虛數或複數，其實數和虛數分量爲1，那麼1將不會出現，而只會出現符號。
括號之前只有+。
變量x可能有一個權力（>2），可能有權力1，然後它看起來就像x，或根本不可能出現。
關於多項式的文本表示沒有更多規則，即冪不一定按升序\降序排列。

格式正確的多項式的一些例子：

1
-1
-2.1x
3i
x^2-1
-x^3+2x+1
(5-5i)x^2-x-1
(-1+i)x-5
-ix^3-x^2+1

..和一些不良格式的：

1x（領先不必要1）
+(+1-2i)x（括號已經領先+ ，rea L成分已經領先+）
(5.1i)x^2（不需要括號，因爲係數是虛構的）
-(i-1)（復係數已經領先-）

一些閱讀後在線（SO，Java教程，Java的API），我很快得出結論：考慮到上面提到的所有限制，正則表達式將是解析最簡單的方法。在正式的方面，這個任務的正則表達式是可能的，因爲我畫了一個NFA只接受這樣的有效表達式。

我這樣做TDD（通過JUnit 4中），並且該測試失敗：

assertEquals("Polynomial parsed incorrectly.", poly07, PolyParser.parse(exp07));

其中poly07看起來是這樣的：(5-5i)x^2-x-1。

這就是會被引發的異常：

java.lang.NumberFormatException: For input string: "5-5" 
at sun.misc.FloatingDecimal.readJavaFormatString(FloatingDecimal.java:2043) 
at sun.misc.FloatingDecimal.parseDouble(FloatingDecimal.java:110) 
at java.lang.Double.parseDouble(Double.java:538) 
at PolyParser.parse(PolyParser.java:55) 
at PolyParserTest.testParse(PolyParserTest.java:59)

我試着調試，看到正則表達式捕獲5-5i（後來剝去i）。然後它嘗試使用參數字符串5-5調用Double.parseDouble，這會導致異常。

經過所有的閱讀，我不能完全弄清楚正則表達式中所需的調整，以便整個節目的工作。此外，正則表達式不像上面提到的表示約束那樣排序，因爲我想在查看之前將係數解析爲實數，然後查看係數是否複雜;還遇到了實數（即帶有小數點）被解析爲整數的問題，所以正則表達式首先處理實數。

正則表達式：

public static final String POLYNOMIAL_REGEX = 
     "([+-])?" +      // leading plus or minus 
     "(\\()?" +      // parenthesis to denote the beginning of a complex number 
     "([+-])?(((\\d+.\\d+)|\\d+)i)?" +  // component of coefficient, imaginary 
     "(((-)?\\d+.\\d+)|\\d+)?" +  // component of coefficient, real 
     "(\\))?" +      // parenthesis to denote the end of a complex number 
     "(x)?" +      // variable 
     "(?:\\^(\\d+))?";    // power of the variable

我不打算在這裏發佈的所有相關的代碼，因爲它會弄亂的東西了。所有的代碼在GitHub，只要確保切換到分支PolyParser。

相關代碼是在文件：

PolyParser.java
Polynomial.java
Complex.java

測試單元是文件PolyParserTest.java英寸

來源

2015-09-29 asafc

正則表達式幾乎從來都不是分析問題的正確解決方案。 – Henry

我的建議：不要。如果你想要一個簡單的解析器，可以使用上下文無關的解析器，看看[PEP]（http://www.coffeeblack.org/）。或者你可以去整個豬，並使用Antlr。 – biziclop

或者，您可以嘗試[JEP]（http://www.cse.msu.edu/SENS/Software/jep-2.23/doc/website/index。html），它可以完成所有這些工作，甚至可以直接評估多項式。 – biziclop

正則表達式基本上無法解析表達式，因爲它們無法跟蹤嵌套（例如括號）。這是大多數人不知道的教訓，他們發現它很難。

但是，表達式使用自頂向下解析相當容易解析。看到我的答案如何做到這一點：https://stackoverflow.com/a/2336769/120163這個答案涵蓋了如何進行解析，並鏈接到另一個關於如何構建AST來表示表達式的答案。

第一步：寫一個語法來表示你的表情將允許。你在你的問題中有一個特別的描述，但是一個語法會迫使你準確地寫出它的合法性和不合法性。用這種語法，你可以很容易地編寫上面提出的遞歸下降解析器。

來源

2015-09-29 14:18:16

讓我們假設用戶輸入格式正確的表達式，然後我們放棄防禦性編程。這樣，就有_no嵌套括號_。我使用正則表達式及其捕獲組來充當解析器。它看起來像是一個非常多的研究和工作，從頭開始實現一個解析器，當我手頭有一個正則表達式幾乎可以像我希望的那樣工作時，只是缺少一些微調。你的想法？ – asafc

你的用戶會輸入公式時出錯。他們會期望括號，不管你喜不喜歡，你需要一個健壯的解析器。 –

Java - 使用正則表達式解析具有復係數的多項式

回答

相關問題