基數定義的數字的正常形式？

Question

我正在寫一個小型計算機代數系統，允許基本的算術運算和部首。所以表達式是二叉樹，其內節點是運算符+ - */^，葉子是有理數。現在我想，像其他CAS做，簡化表達，因此，例如它是

(5+sqrt(2)+sqrt(8))/(1+sqrt(2)) = 1 + sqrt(8) 

如果你開始用左手側，這一點並不明顯，你可以把它改寫成RHS。那麼其他CAS如何做呢？是否有這些表達的正常形式，這樣每個表達式都可以唯一地以正常形式書寫？有沒有一種確定性算法，將任何表達式重寫爲正常形式？

Answer 1

我不知道CAS是如何製作的，但我認爲簡化過程可以通過狀態空間搜索完成。你可以有一套規則，如何將一個表達轉錄成另一個表達。這些規則的應用是搜索圖中的邊，節點是表達式樹。然後，您可以搜索此圖來查找儘可能小的樹（或足夠小的樹，或者可能沒有規則不能進一步應用的樹）。

一個更簡單的任務可能是一個區分程序，它實際上只應用沒有（幾乎）需要實際執行任何搜索的規則。它可以很容易地寫在prolog（儘管我從來沒有這樣做過，只有我們的大學prolog老師告訴我們）。