資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 Python 構建和評估表示式樹的程式
假設，我們得到了一個表示式樹的後序遍歷。我們需要根據給定的後序遍歷構建一個表示式樹，然後評估該表示式。我們返回表示式樹的根節點以及樹的計算結果。
因此，如果輸入如下所示：
則輸出將為 -7。
作為樹輸入給出的字尾表示式為 ['1', '2', '+', '3', '4', '+', '*']。如果對錶達式進行計算，則變為 (1 – 2) * (3 + 4)；結果等於 -7。
為了解決這個問題，我們將遵循以下步驟：
LEFT = 0 RIGHT = 1
定義一個函式 evaluate()。它將接收根節點作為引數。
如果根節點的值是數值，則
返回根節點值的整數表示形式。
left_val := evaluate(根節點的左子節點)
right_val := evaluate(根節點的右子節點)
如果根節點的值為 '+'，則
返回 left_val + right_val
否則，當根節點的值為 '-' 時，則
返回 left_val - right_val
否則，當根節點的值為 '*' 時，則
返回 left_val * right_val
否則，當根節點的值為 '/' 時，則
返回 (left_val / right_val) 的向下取整值。
定義一個函式 buildTree()。它將接收字尾表示式作為引數。
root := null
stack := 一個新的列表
當字尾表示式不為空時，執行以下操作：
curr := 從字尾表示式中刪除最後一個元素。
curr_node := 一個包含值 curr 的新節點。
如果 root 為空，則
root := curr_node
如果 stack 不為空，則
parent := 從 stack 中刪除最後一個元素。
side := parent
如果 side 與 LEFT 相同，則
parent 的左子節點 := curr_node
否則，
parent 的右子節點 := curr_node
如果 curr 不是數值，則
在 stack 的末尾插入元組 (curr_node, LEFT)。
在 stack 的末尾插入元組 (curr_node, RIGHT)。
返回 root。
讓我們看看下面的實現，以便更好地理解：
示例
LEFT = 0 RIGHT = 1 class Node(): def __init__(root, val, left = None, right = None): root.val = val root.left = left root.right = right def evaluate(root): if(root.val.isnumeric()): return int(root.val) left_val = evaluate(root.left) right_val = evaluate(root.right) return ( ( root.val == '+' and left_val + right_val ) or ( root.val == '-' and left_val - right_val ) or ( root.val == '*' and left_val * right_val ) or ( root.val == '/' and left_val // right_val ) ) def buildTree(postfix): root = None stack = [] while(postfix): curr = postfix.pop() curr_node = Node(curr) if(not root): root = curr_node if(stack): parent, side = stack.pop() if(side == LEFT): parent.left = curr_node else: parent.right = curr_node if(not curr.isnumeric()): stack.append((curr_node, LEFT)) stack.append((curr_node, RIGHT)) return root root = buildTree(['1', '2', '+', '3', '4', '+', '*']) print(evaluate(root))
輸入
['1', '2', '+', '3', '4', '+', '*']
輸出
-7
2K+ 次瀏覽
