DSA-programs-in-cpp/Expression_tree.cpp at master · pranavsutar/DSA-programs-in-cpp · 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;

class node {
public:
    string data;
    node* left;
    node* right;

    node(string s)
    {
        data = s;
        left = NULL;
        right = NULL;
    }
};
 int precedence(char x)
{
    cout<<"Precedence\n";
    switch(x)
    {
        case '/' : return 4;
        case '*' : return 3;
        case '+' : return 2;
        case '-' : return 2;
    }
    return 100;
}
void inorder(node* root){
//     cout << "\ninorder: " ;
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}
bool isOperator(char x){
    return (x == '+' || x==  '/' || x== '-' || x== '*' );
}

int calculate(node *root){
    cout<<"Calculate\n";
    if(!root) return 0;

    if(root->left == NULL && root->right == NULL ){
        return stoi(root->data) ;
    }
    // if(!isOperator(root->data[0]) ){
    //     return stoi(root->data) ;
    // }

    string s = root->data;
    if(s=="/") return calculate(root->left)/calculate(root->right);
    if(s=="+") return calculate(root->left)+calculate(root->right);
    if(s=="-") return calculate(root->left)-calculate(root->right);
    if(s=="*") return calculate(root->left)*calculate(root->right);

    return -1;
}

string getString(char x)
{
    string s(1, x);
    return s;
}

int chooseLeast(string s){
    cout<<"chooseLeast";
    int i, l = s.length();
    char c=s[0];
    int p = precedence(s[0]), ind =-1;
    for(i=0; i<l; i++) if(isOperator(s[i])) {
        if(precedence(s[i]) <= p){
            ind = i;
            p = precedence(s[i]);
        }
    }
    if(ind == -1) cout<< "Wrong Action" ;
    return ind;
}

node* BuildExpTree(string s){
    cout<<"BuildTree\n";

    bool b = true;
    int i ;
    for(i=0;i<s.length();i++){
	    	if(isOperator(s[i])){
			b = false; break;
		}
    }
    if(b){
        return new node(s);
    }

    int ic = chooseLeast(s);
    string c = getString(s[ic]) ;
    node* root = new node(c);
    root->left = BuildExpTree(s.substr(0,ic));
    root->right = BuildExpTree(s.substr(ic+1));
    return root;
}

int main()
{
    string s ; cin>>s;
    node* root = BuildExpTree(s);

    inorder(root);
    cout << calculate( root);
    cout << "\nEND";
    return 0;
}