資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究資料結構中構建表示式樹的演算法
表示式樹
表示式樹用於將要操作的值放在葉節點上，並將運算子放在葉節點將對其進行操作的內部節點上。
示例
4 + ((7 + 9) * 2) 的表示式樹如下所示
構建表示式樹的演算法
令 T 為表示式樹。
If T is not NULL:
If T->data is an operand:
return T.data
A = solve(T.left)
B = solve(T.right)
--> Calculate operator for 'T.data' on A and B, and call recursively,
return calculate(A, B, T.data)
如何構建表示式樹？
要為給定的表示式構建表示式樹，我們通常使用棧資料結構。
最初，我們遍歷給定的字尾表示式並按照如下步驟進行操作 -
- 如果我們在給定的表示式中獲取到一個運算元，則將其壓入棧中。它將成為表示式樹的根。
- 如果一個運算子在表示式中獲取到兩個值，則將其作為其子級新增到表示式樹中，並將其壓入當前節點。
- 重複步驟 1 和步驟 2，直至完成對給定表示式的遍歷。
- 現在檢查每個根節點是否僅包含運算元，並且每個子節點是否僅包含值。
更新於：23-2-2021
8K+ 瀏覽量
廣告