用於將表達式轉換爲二叉樹的算法

我有一個任務，其中有一個公式，比如說x+(y*z)，我必須將其轉換爲二叉樹。我在網上查找過，並且看過infix和postfix等關鍵字，它們將幫助將正則表達式轉換爲可以進一步輕鬆轉換爲二叉樹的形式。用於將表達式轉換爲二叉樹的算法

我唯一的問題是，我從來沒有學過這個infix或postfix方法，那麼有沒有其他的方式來轉換它，或者是唯一的方法？我試過搜尋，但這些是我得到的唯一結果。

這對我來說很難解決，而不使用在線資源。

來源

2017-02-24 Veesha Dawg

看看[調度場算法]的詳細描述（https://en.wikipedia.org/ wiki/Shunting-yard_algorithm） - 它是關於將中綴（例如'x +（y * z）'）轉換爲後綴（例如'xyz * +'）。 –

中綴和後綴（和前綴）是表示二元運算符的方式。正則表達式只有一元運算符，如Kleene星和'+'。你正在處理正則表達式還是算術表達式？ –

它們是具有變量的表達式。例如，-x，（x + y），（x *（x + y）） –

Infix和Postfix本身不是方法本身，而是表示同一個公式的方法。 x+(y*z)已經是中號表示法（因爲運算符是在一側的方程式）。其他兩個符號是前綴（或波蘭符號），其中操作符在操作數之前（因此x+(y*z)是+ x * y z）和後綴（或反轉波蘭符號），其中操作符在操作數之後（因此x+(y*z)是y x * x +）。因爲它可以通過一個棧可以輕鬆實現後綴符號是非常有用的（所以要計算y x * x +你把y和x在棧上，那麼我們看到*從棧中彈出x和y並提出x*y回到文件堆中，然後我們把x入堆棧，然後我們看到+從棧中彈出z*y和x並提出x+(z*y)放回堆棧和繁榮有你的計算）

您可以從中間符號通過Shunting-yard algorithm轉換爲後綴（維基百科解釋它更好比我能）

因此，您可以通過二叉樹很容易地表示後綴表示法中的方程式，因爲您會經歷方程式，將操作數添加到堆棧中作爲樹葉，並且當您到達操作員時，會彈出堆棧中的前兩個節點並創建以操作員爲父節點的新節點和操作數由於其子節點而彈出。然後將這棵樹推回棧上。重複，直到達到等式的末尾。

來源

2017-02-24 15:04:05

有許多解析庫可用於這類工作。

例如，使用pyparsing：

from pyparsing import * 

def rearrange(tks): 
    T=tks[0] 
    T[0],T[1] = T[1],T[0] 
    return tks 

expr = Forward() 
arithOp = Word("+-*/", max=1) 
terminal = (Word(alphas, alphanums) 
      | Word(nums) 
      | Suppress("(") + expr + Suppress(")")) 
expr << Group(terminal + arithOp + terminal).setParseAction(rearrange) 

parseTree = expr.parseString("x+(y*z)") 
print parseTree

將打印：

[['+', 'x', ['*', 'y', 'z']]]

來源

2017-02-24 15:09:06

用於將表達式轉換爲二叉樹的算法

回答

相關問題