CODEWITHSUNDEEP
c++expressionbinary-tree
Wolfy
Wolfy

Reputation: 458

Evaluating expression trees in C++ using inordertraversal

This problem is given in daily coding problem #50. 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).

I first thought okay, well why don't I get a vector for the inordertraversal representation of this tree and go from there. I got a bit stuck and glanced at a solution online. I was able to understand it and reproduce it but I am not satisfied with that.

What I have so far is a inordertraversal representation of this tree in a vector: [3, +, 2, *, 4, +, 5].

I want to evaluate this from here but I am a bit stuck on the logic.

Here is the code I have thus far that does not work. Note that binary_tree_calculate2 is the function I am trying to work on.

// 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();
}

Upvotes: 0

Views: 378

Answers (1)

PaulMcKenzie
PaulMcKenzie

Reputation: 35455

One obvious error is that in binary_tree_calculate2, you are taking result and corrupting it with a division at the end:

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?
}

In short, you are missing else statements:

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;
}

Note that the assumption is that tree_node[i] is going to have a mathematical operation symbol, and for division, num is not 0.

The difference in binary_tree_calculate1 is that a return is done immediately after each calculation, thus the error doesn't exist in that function.

Upvotes: 1

Related Questions