資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++表示式樹的求值
在這個問題中，我們得到一個由諸如+，-，/，*之類的二元運算組成的表示式樹。我們需要對錶達式樹進行求值，然後返回結果。
表示式樹是一種特殊的二叉樹，其中每個節點要麼包含一個運算子，要麼包含一個運算元，它們分佈如下：
- 樹的葉子節點是將要對其執行運算的值。
- 非葉子節點包含表示要執行的運算的二元運算子。
讓我們舉個例子來理解這個問題：
輸入：
輸出：1
解釋：
解碼錶達式樹：
表示式 = ( (5+9) / (2*7) )
= ( 14 / 14 )
= 1
解決方案
解決這個問題的一個簡單方法是從根節點開始執行每個運算，對於運算元，我們將解決子樹。由於所有運算都是二元的，因此樹的節點要麼有兩個子節點，要麼沒有子節點。
我們將使用遞迴來解決每個節點的二元運算。
程式說明了我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
class node {
public:
string value;
node *left = NULL, *right = NULL;
node(string x)
{
value = x;
}
};
int solveExpressionTree(node* root) {
if (!root)
return 0;
if (!root->left && !root->right)
return stoi(root->value);
int leftSubTreeSol = solveExpressionTree(root->left);
int rightSubTreeSol = solveExpressionTree(root->right);
if (root->value == "+")
return leftSubTreeSol + rightSubTreeSol;
if (root->value == "-")
return leftSubTreeSol - rightSubTreeSol;
if (root->value == "*")
return leftSubTreeSol * rightSubTreeSol;
if (root -> value == "/")
return leftSubTreeSol / rightSubTreeSol;
return -1;
}
int main()
{
node *root = new node("/");
root->left = new node("+");
root->left->left = new node("9");
root->left->right = new node("5");
root->right = new node("*");
root->right->left = new node("2");
root->right->right = new node("7");
cout<<"The evaluation of expression tree is "<<solveExpressionTree(root);
return 0;
}輸出：
The evaluation of expression tree is 1
更新於：2021年1月22日
968 次瀏覽
廣告