Trong bài toán này, chúng ta được đưa ra một cây biểu thức bao gồm các phép toán nhị phân như +, -, /, *. Chúng ta cần thực hiện đánh giá cây biểu thức và sau đó trả về kết quả.
Cây biểu thức là một loại cây nhị phân đặc biệt, trong đó mỗi nút bao gồm một toán tử hoặc toán hạng được phân phối dưới dạng−
- Các nút lá của cây là các giá trị mà hoạt động sẽ được thực hiện.
- Các nút không phải lá bao gồm toán tử nhị phân biểu thị hoạt động sẽ được thực hiện.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào:
Đầu ra: 1
Giải thích:
Giải mã cây biểu thức,
Exp =((5 + 9) / (2 * 7))
=(14/14)
= 1
Phương pháp tiếp cận giải pháp:
Một giải pháp đơn giản cho vấn đề là bằng cách thực hiện mỗi thao tác từ gốc, đối với các tùy chọn tối ưu, chúng tôi sẽ giải quyết cây con. Vì tất cả các phép toán đều là nhị phân nên các nút của cây có hai nút con hoặc không có nút nào.
Chúng tôi sẽ sử dụng đệ quy để giải quyết hoạt động nhị phân của mỗi nút.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra -
The evaluation of expression tree is 1