Generally, OOP( Object Oriented Progarmming) have three important elements:

  • Abstraction of data
  • Inheritance
  • Dynamic Binding

Now, there is a demo for how to build an arithmetic expression-tree.

images

We want to build a node-tree like the tree in that picture to print a correct arithmetic expression.

Here you could see the relationship between the classes we used in our demo.

images

You know that the three classes Int_node, Unary_node and Binary_node are all inherit from the base class Expr_node.

Let’s look at the simple unary arithmetic expression (-5). In this expression, there is only one operand - and one integer 5. In expression ( 3 + 4), there are two integer and one operand.

We could find that there are only three different expression in representation of arithmetic expression. They are:

  • Integer Expression
  • Unary Expression
  • Binary Expression

So, we find the common attributes on the three different types of expression and use a base-class Expr_node to represent this attribute.

If you have background in class handle, you may notice that class Expr is the handle for Expr_node.

We don’t need real objects of class Expr_node. What we need is the classes which inherit from that base-class. The meaning of the base-class is to provide the public interface.

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
    Programmer  :   EOF
    Date        :   2015.05.19
    File        :   exp_node.cpp
    E-mail      :   jasonleaster@gmail.com
 */
#include <iostream>
#include <string>
using namespace std;
/*
   This @Expr_node is the base-class.
 */
class Expr_node
{
    friend ostream& operator << (ostream&, const Expr_node&);
    friend class Expr;
    int use;// @use is a counter to avoid copying objects.
    //protected:
    public:
        Expr_node(): use(1) { }
        virtual void print(ostream&) const = 0;
        virtual ~Expr_node() { }
};
class Expr
{
    friend ostream& operator<<(ostream&, const Expr&);
    Expr_node* p;
    public:
        Expr():p(NULL){}
        Expr(int);
        Expr(const string&, Expr);
        Expr(const string&, Expr, Expr);
        Expr(const Expr& t) { p = t.p; ++p->use; };
        Expr& operator=(const Expr&);
        ~Expr() { if(--p->use == 0) delete p;}
};
ostream&
operator<<(ostream& o, const Expr_node& e)
{
    e.print(o);
    return o;
}
Expr&
Expr::operator=(const Expr& rhs)
{
    rhs.p->use++;
    if(--p->use == 0)
    {
        delete p;
    }
    p = rhs.p;
    return *this;
}
ostream&
operator<<(ostream& o, const Expr& t)
{
    t.p->print(o);
    return o;
}
class Int_node: public Expr_node
{
    friend class Expr;
    int n;
    Int_node(int k): n(k) { }
    void print(ostream& o) const { o << n;}
};
class Unary_node: public Expr_node
{
    friend class Expr;
    string op;
    Expr opnd;
    Unary_node(const string& a, Expr b):
        op(a), opnd(b) { }
    void print(ostream& o) const
    {
        o << "(" << op << opnd << ")";
    }
};
class Binary_node: public Expr_node
{
    friend class Expr;
    string op;
    Expr left;
    Expr right;
    Binary_node(const string& a, Expr b, Expr c):
        op(a), left(b), right(c) { }
    void print(ostream& o) const
    {
        o << "(" << left << op << right << ")";
    }
};
Expr::Expr(int n)
{
    p = new Int_node(n);
}
Expr::Expr(const string& op, Expr t)
{
    p = new Unary_node(op, t);
}
Expr::Expr(const string& op, Expr left, Expr right)
{
    p = new Binary_node(op, left, right);
}
int main()
{
    Expr t = Expr("*", Expr("-", 5), Expr("+", 3, 4));
    cout << t << endl;
    t = Expr("*", t, t);
    cout << t << endl;
    return 0;
}

You could run this program and will get the output like this one.

images

More Opeartion

We could evaluate the expression and add more types of node.

Here is the implementation. That’s cool!

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
/*
    Programmer  :   EOF
    Date        :   2015.05.19
    File        :   8.5.cpp
    E-mail      :   jasonleaster@gmail.com
 */
#include <iostream>
#include <string>
using namespace std;
/*
   This @Expr_node is the base-class.
 */
class Expr_node
{
    friend ostream& operator << (ostream&, const Expr_node&);
    friend class Expr;
    int use;// @use is a counter to avoid copying objects.
    protected:
        Expr_node(): use(1) { }
        virtual void print(ostream&) const = 0;
        virtual ~Expr_node() { }
        virtual int eval() const = 0;
};
class Expr
{
    friend ostream& operator<<(ostream&, const Expr&);
    Expr_node* p;
    public:
        Expr():p(NULL){}
        Expr(int);
        Expr(const string&, Expr);
        Expr(const string&, Expr, Expr);
        Expr(const string&, Expr, Expr, Expr);
        Expr(const Expr& t) { p = t.p; ++p->use; };
        Expr& operator=(const Expr&);
        ~Expr() { if(--p->use == 0) delete p;}
        int eval() const {return p->eval();}
};
ostream&
operator<<(ostream& o, const Expr_node& e)
{
    e.print(o);
    return o;
}
Expr&
Expr::operator=(const Expr& rhs)
{
    rhs.p->use++;
    if(--p->use == 0)
    {
        delete p;
    }
    p = rhs.p;
    return *this;
}
ostream&
operator<<(ostream& o, const Expr& t)
{
    o << (*t.p);
    return o;
}
class Int_node: public Expr_node
{
    friend class Expr;
    int n;
    Int_node(int k): n(k) { }
    void print(ostream& o) const { o << n;}
    int eval() const { return n;}
};
class Unary_node: public Expr_node
{
    friend class Expr;
    string op;
    Expr opnd;
    Unary_node(const string& a, Expr b):
        op(a), opnd(b) { }
    void print(ostream& o) const
    {
        o << "(" << op << opnd << ")";
    }
    int eval() const
    {
        if(op == "-")
        {
            return -opnd.eval();
        }
        throw "error, bad op" + op + "int UnaryNode";
    }
};
class Binary_node: public Expr_node
{
    friend class Expr;
    string op;
    Expr left;
    Expr right;
    Binary_node(const string& a, Expr b, Expr c):
        op(a), left(b), right(c) { }
    void print(ostream& o) const
    {
        o << "(" << left << op << right << ")";
    }
    int eval() const
    {
        int op1 = left.eval();
        int op2 = right.eval();
        if(op == "-") return op1 - op2;
        if(op == "+") return op1 + op2;
        if(op == "*") return op1 * op2;
        if(op == "/") return op1 / op2;
        if(op == "/" && op2 != 0) return op1/ op2;
        throw "error, bad op" + op + "int BinaryNode";
    }
};
class Ternary_node:public Expr_node
{
    friend class Expr;
    string op;
    Expr left;
    Expr middle;
    Expr right;
    Ternary_node(const string& a, Expr b, Expr c, Expr d):
        op(a), left(b), middle(c), right(d) { }
    void print(ostream& o) const;
    int eval() const;
};
void Ternary_node::print(ostream& o) const
{
    o << "(" << left << " ? " << middle << ":" << right << ")";
}
int Ternary_node::eval() const
{
    if(left.eval())
    {
        return middle.eval();
    }
    else
    {
        return right.eval();
    }
}
Expr::Expr(int n)
{
    p = new Int_node(n);
}
Expr::Expr(const string& op, Expr t)
{
    p = new Unary_node(op, t);
}
Expr::Expr(const string& op, Expr left, Expr right)
{
    p = new Binary_node(op, left, right);
}
Expr::Expr(const string& op, Expr left, Expr middle, Expr right)
{
    p = new Ternary_node(op, left, middle, right);
}
int main()
{
    Expr t = Expr("*", Expr("-", 5), Expr("+", 3, 4));
    cout << t << " = " << t.eval() << endl;
    t = Expr("*", t, t);
    cout << t << " = " << t.eval() << endl;
    t = Expr("?",Expr(1),Expr(2),Expr(3));
    cout << t << " = " << t.eval() << endl;
    return 0;
}

images

Photo by Zhouyin in ShangHai, China

images