如何確定數學表達式的評估順序？

給出一個數學表達式，我想知道哪些是可以同時評估的部分。例如，給定下面的表達式，如何確定數學表達式的評估順序？

(a + b) * c - (d + e)/f

(a + b)和(d + e)能，因爲它們是彼此獨立的同時進行評價。

有沒有用於此目的的算法？或者甚至有任何實現此功能的庫？

來源

2012-04-29 enzom83

我不清楚你的意思是「彼此獨立」。你是否說他們是獨立的，因爲他們沒有共同的變數？似乎即使在（a + e）中的第二個表達式中出現，仍然可以並行評估（a + b）和（a + e），否？因爲在評估過程中所有變量都是隻讀的？你的問題聽起來類似於對我更有意義的聲音，那就是：你如何確保你不會多次評估同一個子表達式。爲此，請參閱備忘錄。 – 2012-04-29 09:03:57

「獨立」，因爲它們可以同時進行評估......通常，如果我必須評估一個表達式，我會按順序執行，所以我首先評估'（a + b）'，然後我會乘'（a + b）'的結果等等。但是，您可以進行並行評估。 – enzom83 2012-04-29 09:19:07

所以，對，如果你的表達式在一棵樹中（見下面的Ido.Co的圖片），你只是表示你不想在評估一個子節點的同時評估一個父節點。但是那不是你想要做的東西，對吧？因爲無論如何您都必須評估子節點，作爲評估父節點的一部分。 – 2012-04-29 09:39:46

This是一個簡短的步驟手冊，用於創建數學解析器。解析表達式後，您持有表示解析表達式的樹，您可以對其進行迭代，並且在每次迭代中，樹的每對樹葉都將表示一個獨立表達式（可以同時進行評估）。 [在每次迭代替換其結果所計算的表達式]

Building Expression Evaluator with Expression Trees in C#

enter image description here

來源

2012-04-29 09:21:44

評價的順序取決於兩個因素：

優先：在每種語言通常有指示每個操作符的優先級
關聯性一個表：當表達涉及幾個具有相同優先級的操作員，操作員關聯性管理操作的執行順序。

如果可能會有一些優化涉及表達式的部分同時評價，我認爲可以只在JVM/CLR水平，而不是與圖書館做...

來源

2012-04-29 09:06:43 aleroot

我相信你應該使用Reversed Polish Notation。
閱讀下面的更多細節：

This is用C++編寫，其將正常符號來逆轉波蘭表示法的功能。有人可能會幫助您將其轉換爲C＃：

來源

2012-04-29 09:08:31

確定，所以讓我們看看例如作爲樹：

  - 
    (*   /) 
(c +)  (+ f) 
    (a b) (d e)

（括號配對屬於節點同一父母的兩個孩子）

如果很簡單，就可以獲得該樹，例如使用調車場算法THM。

現在請注意，爲了評估一個節點，你只需要這個節點的子節點（但是遞歸的）。正如你注意到的，因此(a + b)和(d + e)不依賴於彼此。另外(c * (a + b))不依賴於(d + e)或((d + e)/f)，並且((d + e)/f)不依賴於(a + b)。

一般而言，取一個節點n，任何既不是祖先的後裔，也可以同時進行評估。如果您正在制定計劃，則必須添加「如果現在可以評估該節點」 - 顯然，在評估其後代之前無法評估節點。

我不確定你指的是什麼「這個目的」。你想要計算什麼？

來源

2012-04-29 09:33:53 harold

「這個目的」：找到一個獨立的部分表達。可以在不同的主機/處理器上同時評估每個部分。 – enzom83 2012-04-29 09:40:01

如何確定數學表達式的評估順序？

回答

相關問題