DS-Lab/binary_expression_tree.cpp at master · ssubramanya/DS-Lab · 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
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
struct node
{
    char data;
    node* left;
    node* right;
};
typedef node* NODE;
NODE get_node(char x)
{
    NODE n=new node;
    if(n==NULL)
        cout<<"Memory Full";
    n->data=x;
    n->left=NULL;
    n->right=NULL;
    return n;
}
//NODE set_left(NODE root,NODE x)
//{
//    if(root->left!=NULL)
//        return root;
//    root->left=x;
//    return root;
//}
//NODE set_right(NODE root,NODE x)
//{
//    if(root->right!=NULL)
//        return root;
//    root->right=x;
//    return root;
//}
stack<NODE>mstack;
NODE make_tree(char exp[])
{
    int i=0;
    NODE x=NULL;
    cout<<"check1";
    while(exp[i]!='\0')
    {
        x=get_node(exp[i]);
        if(isdigit(exp[i]))
            mstack.push(x);
        else
        {
            x->right=mstack.top();
            mstack.pop();
            x->left=mstack.top();
            mstack.pop();
            mstack.push(x);
        }
        i++;
    }
    x=mstack.top();
    mstack.pop();
    return x;
}
void inorder(NODE p)
{
    if(p!=NULL)
    {
        inorder(p->left);
        cout<<p->data<<" ";
        inorder(p->right);
    }
}
void preorder(NODE p)
{
    if(p!=NULL)
    {
        cout<<p->data<<" ";
        preorder(p->left);
        preorder(p->right);
    }
}
int OP(char symbol,double op1,double op2)
{
    switch(symbol)
    {
    case '+':
        return (op1+op2);
    case '-':
        return (op1-op2);
    case '*':
        return (op1*op2);
    case '/':
        return (op1/op2);
    case '$':
    case '^':
        return (pow(op1,op2));
    }
}
void eval(NODE root)
{
    int x;
    if(isdigit(root->left->data)&&isdigit(root->right->data))
    {
        x=OP(root->data,root->left->data-'0',root->right->data-'0');
        delete root->left;
        delete root->right;
        root->data=x;
        root->right=root->left=NULL;
    }
    else()
    {
        root=root->left;
    }
}
int main()
{
    char post[20];
    cout<<"entr postfix expre"<<endl;
    cin>>post;
    cout<<"check2";
    NODE root=make_tree(post);
    cout<<"\n\n";
    inorder(root);
    cout<<"\n\n";
    preorder(root);
    return 0;
}