SHARE
TWEET

Untitled

a guest Jan 21st, 2020 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. struct elem * root;
  5. struct elem {
  6.     int balance,v;
  7.     char k[1000];
  8.     struct elem * parent;
  9.     struct elem * left;
  10.     struct elem * right;
  11. };
  12. struct elem * Init(char * k,int balance,int v) {
  13.     struct elem * a = (struct elem*)malloc(sizeof(struct elem));
  14.     strcpy(a->k,k);
  15.     a->parent = NULL;
  16.     a->left = NULL;
  17.     a->right = NULL;
  18.     a->v = v;
  19.     a->balance = balance;
  20.     return a;
  21. }
  22. void Replace(struct elem * x,struct elem * y) {
  23.     if (x == root) {
  24.         root = y;
  25.         y->parent = NULL;
  26.     }
  27.     else {
  28.         struct elem * parent = x->parent;
  29.         if (y != NULL) y->parent = parent;
  30.         if (parent->left == x) parent->left = y;
  31.         else parent->right = y;
  32.     }
  33. }
  34. struct elem *  Search(char * k) {
  35.     struct elem * el = root;
  36.     while((el != NULL) && (strcmp(el->k,k) != 0)) {
  37.         if (strcmp(k,el->k) < 0) el = el->left;
  38.         else el = el->right;
  39.     }
  40.     return el;
  41. }
  42. struct elem * RotateLeft(struct elem * x) {
  43.     struct elem * y = x->right;
  44.     Replace(x,y);
  45.     struct elem * b = y->left;
  46.     if (b != NULL) {
  47.         b->parent = x;
  48.     }
  49.     x->right = b;
  50.     x->parent = y;
  51.     y->left = x;
  52.     --x->balance;
  53.     if (y->balance > 0) x->balance -= y->balance;
  54.     --y->balance;
  55.     if (x->balance < 0) y->balance += x->balance;
  56. }
  57. struct elem * RotateRight(struct elem * x) {
  58.     struct elem * y = x->left;
  59.     Replace(x,y);
  60.     struct elem * b = y->right;
  61.     if (b != NULL) {
  62.         b->parent = x;
  63.     }
  64.     x->left = b;
  65.     x->parent = y;
  66.     y->right = x;
  67.     ++x->balance;
  68.     if (y->balance < 0) x->balance -= y->balance;
  69.     ++y->balance;
  70.     if (x->balance > 0) y->balance += x->balance;
  71. }
  72. struct elem * Insert(int v,char * k) {
  73.     struct elem * elem = Init(k,0,v);
  74.     if (root == NULL) {
  75.         root = elem;
  76.         return 1;
  77.     }
  78.     struct elem * lm = root;
  79.     for(;;) {
  80.         if (strcmp(k,lm->k) == 0) {
  81.             free(elem);
  82.             return 0;
  83.         }
  84.         if (strcmp(k,lm->k) < 0) {
  85.             if (lm->left == NULL) {
  86.                 lm->left = elem;
  87.                 elem->parent = lm;
  88.                 break;
  89.             }
  90.             else lm = lm->left;
  91.         }
  92.         else {
  93.             if (lm->right == NULL) {
  94.                 lm->right = elem;
  95.                 elem->parent = lm;
  96.                 break;
  97.             }
  98.             else lm = lm->right;
  99.         }
  100.     }
  101.     return 1;
  102. }
  103. struct elem * InsertAVL(int v,char * k) {
  104.     struct elem * a;
  105.     int t = Insert(v,k);
  106.     if (t == 0) {
  107.         return 0;
  108.     }
  109.     else {
  110.        a = Search(k);
  111.     }
  112.     for(;;) {
  113.         struct elem * x = a->parent;
  114.         if (!x) return 1;
  115.         if (a == x->left) {
  116.             --x->balance;
  117.             if (x->balance == 0) break;
  118.             if (x->balance == -2) {
  119.                 if (a->balance == 1) {
  120.                     RotateLeft(a);
  121.                 }
  122.                 RotateRight(x);
  123.                 break;
  124.             }
  125.         }
  126.         else {
  127.             ++x->balance;
  128.             if (x->balance == 0) break;
  129.             if (x->balance == 2) {
  130.                 if (a->balance == -1) {
  131.                     RotateRight(a);
  132.                 }
  133.                 RotateLeft(x);
  134.                 break;
  135.             }
  136.         }
  137.         a = x;
  138.     }
  139.     return 1;
  140. }
  141. void freeleks(struct elem * a) {
  142.     if (a != NULL) {
  143.         freeleks(a->left);
  144.         freeleks(a->right);
  145.         free(a);
  146.     }
  147. }
  148. int main()
  149. {
  150.     root = NULL;
  151.     char str[20] ;
  152.     int flag = 0,ident = 0,v = 0,k,n,smbl;
  153.     scanf("%d" , &n);
  154.     smbl = getchar();
  155.     smbl = getchar();
  156.     for(int i = 0;i < n;) {
  157.         if (smbl == ' ') {
  158.             smbl = getchar();
  159.             i++;
  160.         }
  161.         else {
  162.             switch(smbl) {
  163.                 case '+':
  164.                     flag = 1;
  165.                     printf("SPEC 0\n");
  166.                     i++;
  167.                     break;
  168.                 case '-':
  169.                     flag = 1;
  170.                     printf("SPEC 1\n");
  171.                     i++;
  172.                     break;
  173.                 case '*':
  174.                     flag = 1;
  175.                     printf("SPEC 2\n");
  176.                     i++;
  177.                     break;
  178.                 case '/':
  179.                     flag = 1;
  180.                     printf("SPEC 3\n");
  181.                     i++;
  182.                     break;
  183.                 case '(':
  184.                     flag = 1;
  185.                     printf("SPEC 4\n");
  186.                     i++;
  187.                     break;
  188.                 case ')':
  189.                     flag = 1;
  190.                     printf("SPEC 5\n");
  191.                     i++;
  192.                     break;
  193.             }
  194.             if (flag == 1) {
  195.                 smbl = getchar();
  196.                 flag = 0;
  197.                 continue;
  198.             }
  199.             else {
  200.                 if ((smbl >= 48) && (smbl <= 57)) {
  201.                     printf("CONST ");
  202.                     while((smbl >= 48) && (smbl <= 57) && (i < n)) {
  203.                         printf("%c" , smbl);
  204.                         smbl = getchar();
  205.                         i++;
  206.                     }
  207.                     printf("\n");
  208.                 }
  209.                 else {
  210.                     while((i < n) && (((smbl >= 48) && (smbl <= 57)) || ((smbl >= 65) && (smbl <= 90)) || ((smbl >= 97) && (smbl <= 122)))) {
  211.                         str[ident] = smbl;
  212.                         smbl = getchar();
  213.                         i++;
  214.                         ident++;
  215.                     }
  216.                     if (ident > 0) {
  217.                         str[ident] = '\0';
  218.                         k = InsertAVL(v,str);
  219.                         if (k == 0) {
  220.                            printf("IDENT %d\n" , (Search(str))->v);
  221.                         }
  222.                         else {
  223.                             printf("IDENT %d\n" , (Search(str))->v);
  224.                             v++;
  225.                         }
  226.                         ident = 0;
  227.                     }
  228.                 }
  229.             }
  230.         }
  231.     }
  232.     freeleks(root);
  233.     return 0;
  234. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top