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

Question

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

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

例如，给定以下树：

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

你应该 return 45，因为它是 (3 + 2) * (4 + 5)。

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

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

Answer 1

一个明显的错误是，在 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++ 中评估表达式树

Evaluating expression trees in C++ using inordertraversal

c++

binary-tree

expression