Эта проблема описана в ежедневной задаче № 50.Предположим, что арифметическое выражение задано в виде двоичного дерева.Каждый лист является целым числом, а каждый внутренний узел является одним из '+', '-', '∗' или '/' .
. Учитывая корень такого дерева, напишите функцию для его оценки.
Например, с учетом следующего дерева:
*
/ \
+ +
/ \ / \
3 2 4 5
Вы должны вернуть 45, как есть (3 + 2) * (4 + 5).
Iсначала подумал, хорошо, почему бы мне не получить вектор для неупорядоченного представления этого дерева и перейти оттуда.Я немного застрял и посмотрел на решение онлайн.Я был в состоянии понять это и воспроизвести это, но я не удовлетворен этим.
То, что я пока имею, является представлением этого дерева в неупорядоченном порядке в векторе: [3, +, 2, *, 4,+, 5].
Я хочу оценить это отсюда, но я немного застрял в логике.
Вот код, который у меня до сих пор не работает.Обратите внимание, что binary_tree_calculate2 - это функция, над которой я пытаюсь работать.
// Daily coding problem #50
// This problem was asked by Microsoft.
// Suppose an arithmetic expression is given as a binary tree. Each leaf is an integer and each internal node is one of
// '+', '−', '∗', or '/'.
// Given the root to such a tree, write a function to evaluate it.
// For example, given the following tree :
// *
// / \
// + +
// / \ / \
// 3 2 4 5
// You should return 45, as it is (3 + 2) * (4 + 5).
#include <cctype>
#include <iostream>
#include <cstring>
#include <utility>
#include <vector>
#include <string>
struct TreeNode
{
std::string val;
std::unique_ptr<TreeNode> left = nullptr;
std::unique_ptr<TreeNode> right = nullptr;
TreeNode(std::string x, std::unique_ptr<TreeNode> &&p = nullptr, std::unique_ptr<TreeNode> &&q = nullptr) :
val(x),
left(std::move(p)),
right(std::move(q)){}
};
int get_num(std::string c)
{
return std::stoi(c);
}
auto inordertraversal(std::unique_ptr<TreeNode>& root)
{
std::vector<std::string> res;
if (!root)
return res;
auto left = inordertraversal(root->left);
auto right = inordertraversal(root->right);
res.insert(res.end(), left.begin(), left.end());
res.push_back(root->val);
res.insert(res.end(), right.begin(), right.end());
}
int binary_tree_calculate1(std::unique_ptr<TreeNode>& root)
{
if (!root)
return 0;
if (!root->left && !root->right)
return get_num(root->val);
int l = binary_tree_calculate1(root->left);
int r = binary_tree_calculate1(root->right);
if (root->val == "+")
return l + r;
if (root->val == "-")
return l - r;
if (root->val == "*")
return l * r;
return l/r;
}
int binary_tree_calculate2(std::unique_ptr<TreeNode>& root)
{
auto tree_node = inordertraversal(root);
int result = 0;
for (int i = 0; i < tree_node.size(); ++i)
{
int num = get_num(tree_node[i]);
if (tree_node[i] == "+")
result += num;
if (tree_node[i] == "-")
result -= num;
if (tree_node[i] == "*")
result *= num;
result /= num;
}
return result;
}
int main()
{
std::unique_ptr<TreeNode> root = std::make_unique<TreeNode>("*");
root->left = std::make_unique<TreeNode>("+");
root->left->left = std::make_unique<TreeNode>("3");
root->left->right = std::make_unique<TreeNode>("2");
root->right = std::make_unique<TreeNode>("+");
root->right->right = std::make_unique<TreeNode>("5");
root->right->left = std::make_unique<TreeNode>("4");
std::cout << binary_tree_calculate1(root) << "\n";
std::cout << binary_tree_calculate2(root) << "\n";
std::cin.get();
}