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 <fstream>
#include <string>
using namespace std;
struct Node
{
public:
string op;
Node*right;
Node*left;
};
int pos=0,count=0;
Node* root=new Node();
string s1, s2;
bool IsOperation(char c)
{
return c=='+'||c=='-'||c=='*'||c=='/';
}
Node* BT(string s, Node* &t)
{
count++;
int length=s.size();
Node* left = new Node();
Node* right = new Node();
int plus = s.find("+");
if(plus!=-1)
{
t->op="+";
t->left=left;
s1=s.substr(0,plus);
BT(s1,left);
s2=s.substr(plus+1);
t->right=right;
BT(s2,right);
}
else
{
int minus = s.find('-');
if(minus!=-1)
{
t->op="-";
t->left=left;
BT(s.substr(0,minus),left);
t->right=right;
BT(s.substr(minus+1),right);
}
else
{
int multy = s.find('*');
if(multy!=-1)
{
t->op="*";
t->left=left;
BT(s.substr(0,multy),left);
t->right=right;
BT(s.substr(multy+1),right);
}
else
{
int divide = s.find('/');
if(divide!=-1)
{
t->op="/";
t->left=left;
BT(s.substr(0,divide),left);
t->right=right;
BT(s.substr(divide+1),right);
}
else
{
t->op=s;
t->right=NULL;
t->left=NULL;
}
}
}
}
return t;
}
int Calculate(Node* &t)
{
if(t->op=="+")
return Calculate(t->left)+Calculate(t->right);
if(t->op=="-")
return Calculate(t->left)-Calculate(t->right);
if(t->op=="*")
return Calculate(t->left)*Calculate(t->right);
if(t->op=="/")
return Calculate(t->left)/Calculate(t->right);
return atoi(t->op.c_str());
}
void PrintBT(Node*t,int h)
{
if (t==NULL) return;
if(t->left!=NULL)
PrintBT(t->left,h+1);
for(int i=0;i<h;i++)
cout<<" ";
cout<< t->op <<endl;
if(t->right!=NULL)
PrintBT(t->right,h+1);
}
void main()
{
setlocale(LC_ALL,"russian");
string str = "2+3*8/2-1";
cout<<str<< endl;
BT(str,root);
int h=0;
PrintBT(root,h);
cout<<"____________________________________________"<< endl << "Ответ:";
cout<<Calculate(root)<<endl;
system("pause");
} |
