gpt4 book ai didi

c++ - 使用中序遍历在 C++ 中评估表达式树

转载 作者:行者123 更新时间:2023-11-28 04:15:02 25 4
gpt4 key购买 nike

此问题在日常编码问题#50 中给出。假设一个算术表达式以二叉树的形式给出。每个叶子是一个整数,每个内部节点是'+'、'-'、'*'或'/'之一。

给定这样一棵树的根,编写一个函数来计算它。

例如,给定以下树:

      *
/ \
+ +
/ \ / \
3 2 4 5

您应该返回 45,因为它是 (3 + 2) * (4 + 5)。

我首先想到的是,为什么我不为这棵树的中序遍历表示获取一个 vector ,然后从那里开始。有点卡了,网上看了一眼解决方案。我能够理解并重现它,但我对此并不满意。

到目前为止,我所拥有的是 vector 中这棵树的中序遍历表示:[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();
}

最佳答案

一个明显的错误是,在 binary_tree_calculate2 中,您正在获取 result 并在末尾用除法破坏它:

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; // <-- What is this line doing?
}

简而言之,您缺少 else 语句:

for (int i = 0; i < tree_node.size(); ++i)
{
int num = get_num(tree_node[i]);
if (tree_node[i] == "+")
result += num;
else
if (tree_node[i] == "-")
result -= num;
else
if (tree_node[i] == "*")
result *= num;
else
result /= num;
}

请注意,假设tree_node[i] 将有一个数学运算符号,并且对于除法,num 不为 0。

binary_tree_calculate1 的不同之处在于每次计算后都会立即执行return,因此该函数中不存在错误。

关于c++ - 使用中序遍历在 C++ 中评估表达式树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56862535/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com