计算器

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<vector>
  5 using namespace std;
  6 char a[105];
  7 struct Node{
  8     Node *lson;
  9     Node *rson;
 10     char data[105];
 11     bool brackets = 0;
 12 };
 13 char b[105];
 14 int num;
 15 bool sign = 1;
 16 vector<char>sy[6];
 17 Node *Structure(){
 18     Node *head, *p_node, *q_node, *d_node;
 19     while(a[num] != ''){
 20         if(a[num] == ')'){
 21             num++;
 22             return head;
 23         }
 24         if(a[num] == '('){
 25             int tmp = num++;
 26             sign = 1;
 27             if(tmp){
 28                 d_node -> rson = Structure();
 29                 d_node -> rson -> brackets = 1;
 30             }
 31             else {
 32                 p_node = Structure();
 33                 sign = 1;
 34             }
 35         }
 36         int cnt = 0;
 37         while(a[num] >= '0' && a[num] <= '9' || a[num] == '.'){
 38             b[cnt++] = a[num++];
 39         }
 40         if(cnt){
 41             b[cnt] = '';
 42             p_node = (Node*)malloc(sizeof(Node));
 43             strcpy(p_node -> data, b); p_node -> lson = NULL; p_node -> rson = NULL;
 44             if(!sign){
 45                 d_node -> rson = p_node;
 46             }
 47         }
 48         else {
 49             b[cnt++] = a[num++];b[cnt] = '';
 50             if(sign){
 51                 d_node = head = (Node*)malloc(sizeof(Node));
 52                 strcpy(head -> data, b); head -> lson = p_node;
 53                 sign = 0;
 54             }
 55             else {
 56                 q_node = head;
 57                 d_node = (Node*)malloc(sizeof(Node));
 58                 strcpy(d_node -> data, b);
 59                 while(1){
 60                     bool flag = 0;
 61                     for(int i = 0; i < sy[q_node -> data[0]].size(); i++){
 62                         if(sy[q_node -> data[0]][i] == b[0]){
 63                             flag = 1;
 64                             break;
 65                         }
 66                     }
 67                     if(flag){
 68                         d_node -> lson = q_node;
 69                         if(q_node == head){
 70                             head = d_node;
 71                         }
 72                         else {
 73                             p_node -> rson = d_node;
 74                         }
 75                         break;
 76                     }
 77                     else {
 78                         if(q_node -> rson -> rson && !q_node -> rson -> brackets){
 79                             p_node = q_node;
 80                             q_node = q_node -> rson;
 81                         }
 82                         else{
 83                             d_node -> lson = q_node -> rson;
 84                             q_node -> rson = d_node;
 85                             break;
 86                         }
 87                     }
 88                 }
 89             }
 90         }
 91     }
 92     return head;
 93 }
 94 void Preorder_traversal(Node *p_node){
 95     if(p_node){
 96         printf("%s", p_node -> data);
 97         Preorder_traversal(p_node -> lson);
 98         Preorder_traversal(p_node -> rson);
 99     }
100 }
101 void Inorder_traversal(Node *p_node){
102     if(p_node){
103         Inorder_traversal(p_node -> lson);
104         printf("%s", p_node -> data);
105         Inorder_traversal(p_node -> rson);
106     }
107 }
108 void Postorder_traversal(Node *p_node){
109     if(p_node){
110         Postorder_traversal(p_node -> lson);
111         Postorder_traversal(p_node -> rson);
112         printf("%s", p_node -> data);
113     }
114 }
115 double Number(char ch[105]){
116     return atof(ch);
117 }
118 char *Charater_string(double x){
119     char ch[105];
120     sprintf(ch, "%f", x);
121     return ch;
122 }
123 char *Count(Node *p_node){
124     if(p_node -> lson -> lson){
125         Count(p_node -> lson);
126     }
127     if(p_node -> rson -> rson){
128         Count(p_node -> rson);
129     }
130     if(p_node -> lson -> lson == NULL && p_node -> rson -> rson == NULL){
131         double x = Number(p_node -> lson -> data);
132         double y = Number(p_node -> rson -> data);
133         delete(p_node -> lson -> lson);
134         delete(p_node -> lson -> rson);
135         delete(p_node -> rson -> lson);
136         delete(p_node -> lson -> rson);
137         p_node -> lson = NULL;
138         p_node -> rson = NULL;
139         switch(p_node -> data[0]){
140             case '+': strcpy(p_node -> data, Charater_string(x+y));break;
141             case '-': strcpy(p_node -> data, Charater_string(x-y));break;
142             case '*': strcpy(p_node -> data, Charater_string(x*y));break;
143             case '/': strcpy(p_node -> data, Charater_string(x/y));break;
144         }
145     }
146     return p_node -> data;
147 }
148 int main(){
149     while(~scanf("%s", a)){
150         sy['-'].push_back('+');
151         sy['-'].push_back('-');
152         sy['*'].push_back('+');
153         sy['*'].push_back('-');
154         sy['/'].push_back('+');
155         sy['/'].push_back('-');
156         sy['/'].push_back('*');
157         sy['/'].push_back('/');
158         num = 0;
159         sign = 1;
160         Node *head = Structure();
161         puts("Preorder traversal:");
162         Preorder_traversal(head);
163         puts("");
164         puts("Inorder traversal:");
165         Inorder_traversal(head);
166         puts("");
167         puts("Postorder traversal:");
168         Postorder_traversal(head);
169         puts("");
170         puts("Computed result is ");
171         printf("%s
", Count(head));
172     }
173     return 0;
174 }