leetcode/expression_tree.cpp at master · Mayank-Parasar/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//
// Created by Mayank Parasar on 2020-01-20.
//

/*
 * Given a simple expression tree, consisting of basic binary operators i.e., + , – ,* and / and some integers,
 * evaluate the expression tree.
 *
    *
   / \
  +    +
 / \  / \
3  2  4  5
 * */

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct node {
    string info;

    node* left;
    node* right;

    node(string val) : info(val), left(nullptr), right(nullptr)
    {}
};

int eval(node* node_) {

    if(node_ != nullptr) {
        if(node_->info != "+" && node_->info != "-" &&
            node_->info != "*" && node_->info != "/") {
            return stoi(node_->info);
        }

        else {
            int A, B;
            if(node_->left != nullptr)
                A = eval(node_->left);
            if(node_->right != nullptr)
                B = eval(node_->right);


            if(node_->info == "+")
                return (A+B);
            else if(node_->info == "-")
                return (A-B);
            else if(node_->info == "*")
                return(A*B);
            else if(node_->info == "/")
                return (A/B);

        }
    }
}

int main() {

    node* node1 = new node("*");
    node* node2 = new node("+");
    node* node3 = new node("+");
    node* node4 = new node("3");
    node* node5 = new node("2");
    node* node6 = new node("4");
    node* node7 = new node("5");

    // connect them:
    node1->left = node2;
    node1->right = node3;

    node2->left = node4;
    node2->right = node5;

    node3->left = node6;
    node3->right = node7;


    cout << eval(node1);

    return 0;
}