驗證字符串中的多項式

Question

我正在嘗試使多項式運算符（總和，休息，乘法和兩個或多個多項式的除法）。代碼必須使用Java並使用鏈接列表。

我在想如何計算器或如何驗證多項式是否有效。我想從String構造一個多項式，但我不知道是否有另一個類可以緩解事情。

這是一項家庭作業，所以我並沒有要求完整的代碼，只是指出了一個好方向。

有兩個類，一個用於節點（名爲Monomio）和一個用於列表（名爲Polinomio，是單項式的總和）。節點類有

Monomio siguienteMonomio; // The next monomial 
int exponente; // I don't know how to say this in English, maybe power 
int coeficiente; // The coefficient 
// A bunch of methods, to sum, multiply etc. 

和列表類有

Monomio primerMonomio; //First Monomial 
Monomio ultimoMonomio; //Last Monomial 
// A bunch of methods, like organize the polynomial by the power, multiply, sum, etc. 

現在我需要這樣一個構造函數。

public Polinomio(String polinomio){ 
    enter code here 
} 

用戶應該進入這樣的：

10倍^ 2 - 7倍+ 9

所以構造使三個節點的列表：

//First node 
int coeficiente = 10; 
int exponente = 2; 
Monomio siguienteMonomio = //secondNode 

//Second node 
int coeficiente = -7; 
int exponente = 1; 
Monomio siguienteMonomio = //thirdNode 

//Third node 
int coeficiente = 9; 
int exponente = 0; 
Monomio siguienteMonomio = null; 

那麼，如何做到這一點的任何想法？我可以簡單地跟蹤特定字符（+ -^x）。但那樣會很漫長，也許還有更好的辦法。

Answer 1

一般來說，這是使用parsers解決 - 有許多庫允許這樣做，看看here。由於這不是一個複雜的解析問題，並且是一項作業，所以您可能會全部手動編寫 - 因此，recursive descent parsers（也稱爲自頂向下解析器）是最簡單的。也看看類似的StackOverflow question。

你提到的 - 按字符分割，在這種情況下工作得很好。一般來說，你想要考慮優先級。你首先評估^，然後*和/，然後+和 - 。遞歸下降解析器自上而下地工作，所以你首先將事情分成最後一個 - 即分開+和 - 然後分開*和/最後分開^。

在你的榜樣，你開始：

10x^2 - 7x + 9 

因此首先通過+和分離獲得三個節點 - ：

T1 = 10x^2 
T2 = -7x 
T3 = +9 

這給你一個多項式條款訂立，屬形式+/- N *的x^K：

10x^2 = +10 * x^2 
-7x = -7 * x^1 
+9  = +9 * x^0 

因此，對於上述各你的：

• 看看它的+或 - 在字符串的開頭
• 看看是否有一個「x」中的術語
  • 如果沒有，那麼你有X^0的情況下，所以你只要一些
  • 如果是，那麼你看看是否有一個^
    • 如果沒有，那麼它的X^1例
    • 如果是的話，那麼它的X-1K-情況下

你提到了驗證。即你想放棄無效的投入，如：

1 + 2x^ 
-- 1 + 4^ 
x^2^3 + x 

多做一些工作，你可以使用regular expressions及其Java implementation這項工作。如果你使用上面提到的自上而下的解析器，你會在每個級別上執行此操作。類似：

• 拆分由+表達成由術語分裂和 -

• 檢查每個術語具有以下形式：+/-（N中，nx或NX^K）

  • 您可以使用正則表達式像這樣（注意 - 我沒有測試）：

    「（？\\ + | - ）（[1-9] [0-9] ）（X（\^[1-9] [0-9]）？）？「

  基本上說：

  • 可選的加號或減號（？\\ + | - ），
  • 也許與非零數字開頭的一組數字： （[1-9] [0-9] *）?,
  • 也許x：（x ...）?,

  • 也許^數字：（\\^[1-9] [0-9 ] *）？

    如果您從未使用過它們，請查看上述文檔。注意「\\」在Java字符串中用於轉義「\」字符。

使用正則表達式組，你甚至可以輕鬆地捕獲的各個部分。您可以使用正則表達式測試器（例如this）來幫助您。

一個好主意是在處理之前刪除空格 - 事實上，這可能是必要的。請注意，如果您需要處理負數係數和/或括號，則這會變得更復雜一些，而傾向於真正的解析器。

希望這會有所幫助。