OO_JAVA_表達式求導_第一彈

---------------------------------------------------表達式提取部分

詞法分析

? 首先，每一個表達式內部都存在不可分割的字符組，比如一個不止一位的數字，或是一個sin三角函數，這樣不能分離的字符組我稱之為詞法單元，依照其定義，可以將第三次作業的表達式分割成如下詞法單元：

SPACE：即空格和TAB字符的組合

純數字：即純粹由0-9字符集組成

運算符：-、+、*、^，這些都是運算符

三角函數：sin或cos內部不可存在空格

左括號：(

右括號：)

? 將一串字符解析成詞法單元列表的形式，就已經是一層處理了，這一步就可以排查出一些錯誤，直接拋出異常，然后我們得到了一個由詞法單元組成的列表，現在就是采用遞歸遞降的方法線性解析這個列表并生成表達樹了。

語法分析

仔細閱讀指導書，可以歸納出如下定義：

Num = [-|+]純數字

Factor = Num | x [^ Num] | sin ( Factor) [^ Num] | cos ( Factor) [^ Num] | (Expr)

Item = [-|+]Factor (*Factor)*

Expr = [-|+]Item ([-|+]Item)*

** 其中[]表示其中的字符存在或不存在皆可；()*表示可選重復0至任意次；| 表示或 **

除Num單元內部，其它語法單元內部可以任意插入SPACE

寫作分析函數的原則有兩條：

采用分層次的設計思路，從歸納的語法定義就可以看出，需要寫一個處理Expr的函數，一個處理Item的函數……需要子結構時調用相應函數即可。

只處理本層次需要處理的字符，遇到非法字符，返回上層調用或者拋出異常；

當然，有人會說，這樣只是寫一堆遞歸函數(o(╯□╰)o，我就是這么寫的)，沒有實行面對對象，其實，遞歸遞降也是可以面對對象的。

模式匹配

首先需要一個Parser接口，實現如下(不一定)函數(為清晰起見，寫的很簡單)

public interface Parser {

public Atom toAtom();

public Integer getIndex();

public void addParser(Parser parser);

}

分別是一個轉換函數，一個獲取新遍歷下標的函數，一個添加子Parser的函數。

根據不同層級Parser的需要，完成相應函數的重寫(Override)即可，舉個栗子：

public class ExprParser implements Parser {

ArrayList itemList;

// Integer endIndex; //

private ExprParser() {

itemList = new ArrayList<>();

}

@Override

public Atom toAtom() {

Atom root = new Atom(Atom.Type.PLUS, BigInteger.ZERO);

for (Parser parser:itemList) {

root.addChild(parser.toAtom());

}

return root;

}

@Override

public Integer getIndex() {

return endIndex;

}

public static Parser newParser(String string) {

Parser parser = new ExprParser();

for (int i = 0; i < string.length();) {

if (string.charAt(i) == '-' || string.charAt(i) == '+' ||

string.charAt(i) != ' ' && string.charAt(i) != '\t') {

Parser itemParser = ItemParser.newParser(string.substring(i));

parser.addParser(itemParser);

i = itemParser.getIndex();

} else {

i += 1;

}

}

return parser;

}

@Override

public void addParser(Parser parser) {

itemList.add(parser);

}

}

依舊格式簡易，但是只是為了說明怎么重寫這樣的函數，Atom即最后生成的表達樹的節點類或者接口，隨個人意。

另外沒有顯式拋出異常，真正寫時需要在返回parser時檢查item List是否為空，若為空，則顯式拋出異常，進行異常處理。

現在說明一下，這個newParser工廠函數為什么這么寫，為了清楚起見，我把Expr的定義重新拉過來：

Expr = [-|+]Item ([-|+]Item)*

這個語法定義告訴我們Expr線性掃描，檢查是否有減號或是加號，然后需要獲取一個Item，這時調用ItemParser的工廠函數即可，格式異常由不同層級的Parser實現類的工廠函數負責拋出，只要語法分析合理，這樣寫作是簡單無誤的。

以此類推，相信讀懂了上述抽象的思維方式，寫出Item和Factor的Parser對你易如反掌！

OO_JAVA_表達式求導_第二彈

------------------------------------------------表達樹的構建

總體來說，按照設計模式上可以分為兩類：本次實驗還是建議第二種方式(雖然我用了第一種，，::>_<::>

extends 繼承，采取一個父類實現所需方法子類重寫方法，但是為了統一填充到ArrayList或者HashMap中，必須采取子類cast回父類的方式，這樣子類不能有自己的屬性，否則無法cast；

implements 實現，采取定義共通的接口，所有節點類重寫接口中的方法，如求導方法、化簡方法、toString方法。

在第三次作業中，我采用了繼承的方案實現樹形結構節點的構造，Atom父類實現了非常多的函數，現在的視角來看，是很不合理的，因為Atom負擔了所有子類的函數，臃腫累贅，層次是分明了，只有父類Atom和子類各種Atom，但是在工程管理和邏輯架構設計上，還是有所問題的。

下面是我的Atom類圖關系，其它類都繼承自Atom很復雜把。

OO_JAVA_表達式求導_第三彈

-----------------------------如何將函數式思維帶入化簡函數

要實現化簡合并，最好先完成兩個準備工作(一個可選)

expand：展開(可選)，有時會遇見123*(x+123)這樣的情況，*與+沒有按照優先級組合，而是需要根據乘法分配率展開這樣的項；

flat Map：平鋪，在處理字符串生成表達樹以及求導表達樹返回新表達樹的過程中，會產生很多如1*(1*(1*x))連乘項或連加項嵌套的結果，平鋪可以將之展開成為1*1*1*x的形式，利于下一步的分類和合并。

首先從宏觀的角度抽象地理解化簡，是怎么一回事，一共兩步

classification：分類，將能化簡的規整在一起，不能化簡的單獨存放，最終結果是一個List>，每一個List存放的是可以合并的同類項；

merge：合并，對不同的可合并List進行合并處理，再新建一個父對象，將合并結果依次填回父對象的子節點中，返回父對象。

現在簡單說明一下Java8引入的Stream API和lambda表達式(實際上是Functional Interface)

舉個栗子，現在我們有一串數字在列表origin中，我們要對他們都平個方，生成一個新列表，正常做法如下：

List after = new ArrayList<>();

for (Integer integer: origin) {

after.add(integer * integer);

}

但是有了Stream API和lambda表達式，就可以這么寫：

List after = origin.stream().map(e -> e * e).collect(toList());

Stream流的主要功能有filter(篩選)，map(映射)，flatMap(平鋪映射)，collect(收集返回列表或Map或其它)。

需要填充函數接口的參數的來源有兩種：

方法引用，比如Integer::add，就是對Integer的加法方法的一個引用，內秉其實是函數接口

lambda表達式，基本形式為(參數列表)->返回值 或 (參數列表)->{語句; return 返回值;}組成。

現在問題來了，為什么要這么寫呢？什么時候要寫成哪一種形式呢？

這兩種寫法的主要區別在于邏輯的分離性與可控性：前者循環方式，循環流程完全由你掌控，可操作性極大，同時腦力負擔也大一些；后者將循環體隱藏在Stream API的內部，你不需要在控制循環的方方面面，可以一層層地分離邏輯，減輕腦力負擔，高效清晰地編寫代碼。

在循環體內部流程非常簡單時，比如上述栗子，你選擇哪一種都沒有什么問題，無非是代碼行數和內部執行效率的區別，但是，在具化到我要講的classification過程時，也就是可以盡量分離循環體內部操作時，選擇Stream API可以清晰地簡單地生成新列表，下面就對此說明一下吧。

Classification可以分為四步：

實現一個函數(滿足Predicate接口定義)，也就是一個泛化意義上的相等函數，用來判斷兩項能否合并；

根據先前實現的接口，采用Stream的filter過濾器API，對每個元素，過濾出與之相等(可合并)的元素組成列表；

依照先前產生的列表，統統插入到Map中，為保證key的唯一，采用每一個列表的toString方法結果作為key；

將上述生成的Map的values取出，返回一個列表的列表，實現classification的功能。

上述過程就是一個邏輯不斷分離的過程，對應到相加項和相乘項，唯一不同的就是Predicate接口，也是這么思維的意義所在。

這里把后三步的合并加法與合并乘法共通的代碼貼出來：

public List filter(Atom atom, Predicate predicate) {

return this.children.stream()

.filter(predicate)

.collect(Collectors.toList());

}

public ArrayList> classify(Predicate predicate) {

Map> map = new HashMap<>();

for (Atom atom : children) {

ArrayList list = (ArrayList) this.filter(atom, predicate);

map.put(list.toString(), list);

}

return new ArrayList<>(map.values());

}

與上述思維類似，Merge也可分步進行：

先merge所有子節點重新填充到新root節點中；

使用classification，獲取新root節點分類后的子節點列表的列表；

創建新root節點，迭代前一步獲取的列表，使用合并同類項函數(同類項列表=>合并后的項)，將節點依次插入新的root節點中，返回。

繼續拆分，上述第三步采用Stream的思路還可以拆分：

產生Stream>流；

map映射List到Atom，這里交由另一個函數接口負責；

filter篩選需要添加至最終列表的項，這里依然可以分離出去交由另一個函數接口負責；

最后collect函數收集流中的元素，返回List，若為空，返回特定值。

這里舉個例子就把合并相加項的filter調用的函數接口寫一下吧：

Predicate addPredicate = e -> !(

e.getType().equals(Atom.Type.CONSTANT) && e.getValue().equals(BigInteger.ZERO)

);

上述函數接口表明，如果元素e是一個常數0了話，返回false否則返回true。

綜上所述，如果你理解了分離邏輯的操作后，寫出清晰簡潔的代碼應該是易如反掌把！

總結

以上是生活随笔為你收集整理的java求导数_OO_JAVA_表达式求导的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。