SHARE
TWEET

Untitled

a guest Jun 16th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include <string.h>
  4.  
  5. struct dllNode {
  6.     int data;
  7.     struct dllNode* next;
  8.     struct dllNode* prev;
  9. };
  10.  
  11. struct dll {
  12.     struct dllNode* first;
  13.     struct dllNode* last;
  14. };
  15.  
  16. struct minmaxdll {
  17.     struct dllNode *minValue;
  18.     struct dllNode *maxValue;
  19. };
  20.  
  21. struct node {
  22.     char payload;
  23.     struct node *next;
  24. };
  25.  
  26. struct stack {
  27.     struct node* root;
  28. };
  29.  
  30. dllNode* newDoublyLinkedListNode(int data) {
  31.  
  32.     dllNode *node = (dllNode*)calloc(1, sizeof(dllNode));
  33.     node->data = data;
  34.     node->prev = NULL;
  35.     node->next = NULL;
  36.     return node;
  37. }
  38.  
  39. dll * emptyDoublyLinkedList() {
  40.     dll *list = (dll*)calloc(1, sizeof(dll));
  41.     list->first = NULL;
  42.     list->last = NULL;
  43.     return list;
  44. }
  45.  
  46. void pushToStart(dll *list, int data) {
  47.  
  48.     if (list->first == NULL) {
  49.         dllNode *newNode = newDoublyLinkedListNode(data);
  50.  
  51.         list->first = newNode;
  52.         list->last = newNode;
  53.     }
  54.     else {
  55.         dllNode* node = list->first;
  56.         dllNode *newNode = newDoublyLinkedListNode(data);
  57.  
  58.         newNode->next = node;
  59.         if (node->prev == NULL) {
  60.             list->first = newNode;
  61.         }
  62.         else {
  63.             newNode->prev = node->prev;
  64.             node->prev->next = newNode;
  65.         }
  66.  
  67.         node->prev = newNode;
  68.     }
  69. }
  70.  
  71. void pushToEnd(dll* list, int data) {
  72.     if (list->last == NULL) {
  73.         dllNode *newNode = newDoublyLinkedListNode(data);
  74.         list->first = newNode;
  75.         list->last = newNode;
  76.     }
  77.     else {
  78.         dllNode* node = list->last;
  79.         dllNode *newNode = newDoublyLinkedListNode(data);
  80.         newNode->prev = node;
  81.         if (node->next == NULL) {
  82.             list->last = newNode;
  83.         }
  84.         else {
  85.             newNode->next = node->next;
  86.             node->next->prev = newNode;
  87.         }
  88.         node->next = newNode;
  89.     }
  90. }
  91.  
  92. void dllNodePrint(dllNode *node) {
  93.     printf("%d\n", node->data);
  94.     if (node->next != NULL) {
  95.         dllNodePrint(node->next);
  96.     }
  97. }
  98.  
  99. void dllPrint(dll *list) {
  100.     puts("\n");
  101.     if (list->first != NULL) {
  102.         dllNodePrint(list->first);
  103.     }
  104. }
  105.  
  106. void dllNodeRemove(dllNode *node) {
  107.     if (node->next != NULL) {
  108.         dllNodeRemove(node->next);
  109.     }
  110.     free(node);
  111. }
  112.  
  113. void dllRemoveAll(dll* list) {
  114.     if (list->first != NULL) {
  115.         dllNodeRemove(list->first);
  116.     }
  117.  
  118.     list->first = NULL;
  119.     list->last = NULL;
  120. }
  121.  
  122. int dllSize(dll *list) {
  123.  
  124.     int size = 0;
  125.     dllNode *node = list->first;
  126.     while (node != NULL) {
  127.         size++;
  128.         node = node->next;
  129.     }
  130.     return size;
  131. }
  132.  
  133. bool dllIsEmpty(dll *list) {
  134.  
  135.     if (list->first == NULL && list->last == NULL) {
  136.         return true;
  137.     }
  138.     return false;
  139. }
  140.  
  141. bool deleteFirst(dll *list) {
  142.     if (list->first == NULL) {
  143.         return false;
  144.     }
  145.     if (list->first->next == NULL) {
  146.         list->first = NULL;
  147.         list->last = NULL;
  148.         free(list->first);
  149.         return true;
  150.     }
  151.     list->first = list->first->next;
  152.     list->first->prev = NULL;
  153.  
  154.     return true;
  155. }
  156.  
  157. bool deleteLast(dll *list) {
  158.     if (list->last == NULL) {
  159.         return false;
  160.     }
  161.     if (list->last->prev == NULL) {
  162.         list->first = NULL;
  163.         list->last = NULL;
  164.         return true;
  165.     }
  166.     list->last = list->last->prev;
  167.     list->last->next = NULL;
  168.  
  169.     return true;
  170. }
  171.  
  172. bool dllFind(dll *list, int value) {
  173.  
  174.     if (list->first == NULL) {
  175.         return false;
  176.     }
  177.     dllNode *node = list->first;
  178.  
  179.     while (node != NULL) {
  180.         if (node->data == value) {
  181.             return true;
  182.         }
  183.         node = node->next;
  184.     }
  185.     return false;
  186. }
  187.  
  188. minmaxdll * newMinMaxHolder(dllNode *min, dllNode *max) {
  189.  
  190.     minmaxdll *holder = (minmaxdll*)calloc(1, sizeof(minmaxdll));
  191.     holder->maxValue = max;
  192.     holder->minValue = min;
  193.     return holder;
  194. }
  195.  
  196. minmaxdll * findMinMax(dll *list) {
  197.     if (list->first == NULL) {
  198.         return NULL;
  199.     }
  200.     dllNode *min = list->first;
  201.     dllNode *max = list->first;
  202.  
  203.     dllNode *node = list->first;
  204.  
  205.     while (node != NULL) {
  206.         if (node->data > max->data) {
  207.             max = node;
  208.         }
  209.         if (node->data < min->data) {
  210.             min = node;
  211.         }
  212.         node = node->next;
  213.     }
  214.  
  215.     return newMinMaxHolder(min, max);
  216. }
  217.  
  218. bool dllRemoveWith(dll *list, int value) {
  219.     dllNode *node = list->first;
  220.     while (node != NULL) {
  221.         if (node->data == value) {
  222.             if (node == list->last && node == list->first) {
  223.                 list->last = list->first = NULL;
  224.                 return true;
  225.             }
  226.             if (node->prev != NULL) {
  227.                 node->prev->next = node->next;
  228.                 if (node == list->last)
  229.                     list->last = node->prev;
  230.             }
  231.             if (node->next != NULL) {
  232.                 node->next->prev = node->prev;
  233.                 if (node == list->first)
  234.                     list->first = node->next;
  235.             }
  236.             return true;
  237.         }
  238.         node = node->next;
  239.     }
  240.     return false;
  241. }
  242.  
  243. bool dllRemoveAllWith(dll *list, int value) {
  244.     bool flag = false;
  245.     dllNode *node = list->first;
  246.     while (node != NULL) {
  247.         if (node->data == value) {
  248.             if (node == list->last && node == list->first) {
  249.                 list->last = list->first = NULL;
  250.                 flag = true;
  251.             }
  252.             if (node->prev != NULL) {
  253.                 node->prev->next = node->next;
  254.                 if (node == list->last)
  255.                     list->last = node->prev;
  256.             }
  257.             if (node->next != NULL) {
  258.                 node->next->prev = node->prev;
  259.                 if (node == list->first)
  260.                     list->first = node->next;
  261.             }
  262.             flag = true;
  263.         }
  264.         node = node->next;
  265.     }
  266.     return flag;
  267. }
  268.  
  269. bool dllReplaceAll(dll *list, int value, int newValue) {
  270.     dllNode *node = list->first;
  271.     bool flag = false;
  272.     while (node != NULL) {
  273.         if (node->data == value) {
  274.             node->data = newValue;
  275.             flag = true;
  276.         }
  277.         node = node->next;
  278.     }
  279.     return flag;
  280. }
  281.  
  282. bool dllIsSymmetric(dll *list) {
  283.  
  284.     dllNode *first = list->first;
  285.     dllNode *second = list->last;
  286.  
  287.     if (first->data != second->data) {
  288.         return false;
  289.     }
  290.     while (first != NULL && second != NULL && first != second && first->next != second) {
  291.         if (first->data != second->data){
  292.             return false;
  293.         }
  294.  
  295.         first = first->next;
  296.         second = second->prev;
  297.     }
  298.     return true;
  299. }
  300.  
  301. int enterInt() {
  302.  
  303.     int number = 0;
  304.     do {
  305.         fflush(stdin);
  306.     } while (!scanf("%d", &number));
  307.  
  308.     return number;
  309. }
  310.  
  311. node * newNode(char value) {
  312.     node *n = (node*)calloc(1, sizeof(node));
  313.     if (n != NULL) {
  314.         n->next = NULL;
  315.         n->payload = value;
  316.     }
  317.     return n;
  318. }
  319.  
  320. stack * newStack() {
  321.     stack *s = (stack*)calloc(1, sizeof(stack));
  322.     if (s != NULL) {
  323.         s->root = NULL;
  324.     }
  325.     return s;
  326. }
  327.  
  328. void stackPush(stack *stack, char payload) {
  329.     if (stack == NULL) return;
  330.  
  331.     if (stack->root == NULL) {
  332.         stack->root = newNode(payload);
  333.     }
  334.     else {
  335.         node *n = newNode(payload);
  336.         if (n == NULL) return;
  337.  
  338.         n->next = stack->root;
  339.         stack->root = n;
  340.     }
  341. }
  342.  
  343. char stackPop(stack *stack, int *failFlag) {
  344.     if (stack == NULL || stack->root == NULL) {
  345.         if (failFlag != NULL) failFlag[0] = 1;
  346.         return 0;
  347.     }
  348.  
  349.     char ret = stack->root->payload;
  350.     stack->root = stack->root->next;
  351.  
  352.     return  ret;
  353. }
  354.  
  355. char stackPeek(stack *stack, int *failFlag) {
  356.     if (stack == NULL || stack->root == NULL) {
  357.         if (failFlag != NULL) failFlag[0] = 1;
  358.         return 0;
  359.     }
  360.  
  361.     return stack->root->payload;
  362. }
  363.  
  364. int isValid(char c) {
  365.     return  (c >= 97 && c <= 122) || // [a-z]
  366.         (c >= 65 && c <= 90) || // [A-Z]
  367.         (c >= 40 && c <= 43) || //[ ( ) + * ]
  368.         c == 94 || // ^
  369.         c == 45 || // -
  370.         c == 61 || // =
  371.         c == 47;   // /
  372. }
  373.  
  374. int priority(char ch) {
  375.     switch (ch) {
  376.     case '^':
  377.         return 4;
  378.     case '*': case'/':
  379.         return 3;
  380.     case '+': case '-':
  381.         return 2;
  382.     case '(':
  383.         return 1;
  384.     default:
  385.         return 0;
  386.     }
  387. }
  388.  
  389.  
  390. char * enterInfix(char *message) {
  391.     int index = 0;
  392.     char *infix = (char*)calloc(1, sizeof(char));
  393.  
  394.     if (infix == NULL) return NULL;
  395.  
  396.     printf("%s", message);
  397.  
  398.     char c;
  399.     while ((c = getchar()) != -1) {
  400.         if (c == '\n') {
  401.             infix[index] = '\0';
  402.             break;
  403.         }
  404.         else if (isValid(c)) {
  405.             infix[index++] = c;
  406.         }
  407.         else {
  408.             printf("Invalid symbol found on index %d - '%c'\n", index, c);
  409.             return NULL;
  410.         }
  411.     }
  412.  
  413.     if (index == 0 || infix[index - 1] != '=') {
  414.         return NULL;
  415.     }
  416.  
  417.     for (int i = 1; i < index; i++) {
  418.         if (infix[i] == infix[i - 1])  {
  419.             return NULL;
  420.         }
  421.     }
  422.  
  423.     return infix;
  424. }
  425.  
  426. char* infixToPostfix(char* infix, int length) {
  427.     stack *stack = newStack();
  428.  
  429.     char* pnString = (char*)calloc(length + 1, sizeof(char));
  430.     int index = 0;
  431.     int pnIndex = 0;
  432.     int errorFlag = 0;
  433.     if (pnString == NULL) {
  434.         return NULL;
  435.     }
  436.  
  437.     while (infix[index] != '=') {
  438.         char c = infix[index];
  439.         if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
  440.             pnString[pnIndex] = infix[index];
  441.             pnIndex++;
  442.         }
  443.         else {
  444.             if (infix[index] == ')') {
  445.                 if (stack->root == NULL) {
  446.                     return NULL;
  447.                 }
  448.                 errorFlag = 0;
  449.                 while (stackPeek(stack, &errorFlag) != '(' && !errorFlag) {
  450.                     pnString[pnIndex++] = stackPop(stack, NULL);
  451.                 }
  452.                 stackPop(stack, NULL);
  453.             }
  454.             else {
  455.                 if (infix[index] == '(') {
  456.                     stackPush(stack, infix[index]);
  457.                     length -= 2;
  458.                 }
  459.                 else {
  460.                     if (infix[index] == '^' ||
  461.                         infix[index] == '+' ||
  462.                         infix[index] == '-' ||
  463.                         infix[index] == '*' ||
  464.                         infix[index] == '/') {
  465.                         if (stack->root == NULL) {
  466.                             stackPush(stack, infix[index]);
  467.                         }
  468.                         else {
  469.                             if (stack->root != NULL && (priority(stackPeek(stack, NULL)) >= priority(infix[index]))) {
  470.                                 pnString[pnIndex++] = stackPop(stack, NULL);
  471.                                 stackPush(stack, infix[index]);
  472.                             }
  473.                             else {
  474.                                 stackPush(stack, infix[index]);
  475.                             }
  476.                         }
  477.                     }
  478.                 }
  479.             }
  480.         }
  481.         index++;
  482.     }
  483.  
  484.     while (stack->root != NULL) {
  485.         if (stackPeek(stack, NULL) == '(') {
  486.             return NULL;
  487.         }
  488.         pnString[pnIndex++] = stackPop(stack, NULL);
  489.     }
  490.     pnString[pnIndex++] = '=';
  491.     pnString[pnIndex] = '\0';
  492.     return pnString;
  493. }
  494.  
  495. void printForm(char* postfix) {
  496.     int i = 0;
  497.     printf("Postfix form: \n");
  498.     while (postfix[i] != '\0') {
  499.         printf("%c", postfix[i]);
  500.         i++;
  501.     }
  502.     printf("\n");
  503. }
  504.  
  505. int main() {
  506.     printf("Enter part of program\n1 - Work with a doubly linked list\n2 - Polish notation \n");
  507.     char choice;
  508.     fflush(stdin);
  509.     scanf("%c", &choice);
  510.     fflush(stdin);
  511.     while (true){
  512.         if (choice == '1') {
  513.             dll* list = emptyDoublyLinkedList();
  514.             while (true) {
  515.                 printf("\n\n\nMenu: \n");
  516.                 printf("1 - Add to start\n2 - Add to end\n3 - Print all elements\n4 - Remove all elements\n5 - List size\n6 - Is list empty?\n7 - Remove first\n8 - Remove last\n");
  517.                 printf("9 - Find\n10 - Find max and min values\n11 - Remove by value\n12 - Remove all by value\n13 - Edit\n14 - Is list symmetric\n15 - Exit the program\nyour choice: ");
  518.  
  519.                 int option = enterInt();
  520.  
  521.                 switch (option) {
  522.                 case 1: {
  523.                             printf("Enter the number you want add to list\n");
  524.                             int number = enterInt();
  525.                             pushToStart(list, number);
  526.                             break;
  527.                 }
  528.                 case 2: {
  529.                             printf("Enter the number you want add to list\n");
  530.                             int number = enterInt();
  531.                             pushToEnd(list, number);
  532.                             break;
  533.                 }
  534.                 case 3: {
  535.                             if (dllIsEmpty(list)) {
  536.                                 printf("List is empty\n");
  537.                                 break;
  538.                             }
  539.                             dllPrint(list);
  540.                             break;
  541.                 }
  542.                 case 4: {
  543.                             if (dllIsEmpty(list)) {
  544.                                 printf("List is empty\n");
  545.                                 break;
  546.                             }
  547.                             dllRemoveAll(list);
  548.                             printf("Completed successfully\n");
  549.                             break;
  550.                 }
  551.                 case 5: {
  552.                             if (dllIsEmpty(list)) {
  553.                                 printf("List is empty\n");
  554.                                 break;
  555.                             }
  556.                             printf("List size: %d\n", dllSize(list));
  557.                             break;
  558.                 }
  559.                 case 6: {
  560.                             if (dllIsEmpty(list)) {
  561.                                 printf("List is empty\n");
  562.                             }
  563.                             else {
  564.                                 printf("List isn't empty\n");
  565.                             }
  566.                             break;
  567.                 }
  568.                 case 7: {
  569.                             if (dllIsEmpty(list)) {
  570.                                 printf("List is empty\n");
  571.                                 break;
  572.                             }
  573.                             if (deleteFirst(list)) {
  574.                                 printf("Deleted successfully\n");
  575.                             }
  576.                             else {
  577.                                 printf("List is empty\n");
  578.                             }
  579.                             break;
  580.                 }
  581.                 case 8: {
  582.                             if (dllIsEmpty(list)) {
  583.                                 printf("List is empty\n");
  584.                                 break;
  585.                             }
  586.                             if (deleteLast(list)) {
  587.                                 printf("Deleted successfully\n");
  588.                             }
  589.                             else {
  590.                                 printf("List is empty\n");
  591.                             }
  592.                             break;
  593.                 }
  594.                 case 9: {
  595.                             if (dllIsEmpty(list)) {
  596.                                 printf("List is empty\n");
  597.                                 break;
  598.                             }
  599.                             int value = enterInt();
  600.                             if (dllFind(list, value)){
  601.                                 printf("Value was found\n");
  602.                             }
  603.                             else{
  604.                                 printf("Search unsuccessful\n");
  605.                             }
  606.                             break;
  607.                 }
  608.                 case 10: {
  609.                              if (dllIsEmpty(list)) {
  610.                                  printf("List is empty\n");
  611.                                  break;
  612.                              }
  613.                              minmaxdll *minmax = findMinMax(list);
  614.                              if (minmax == NULL) {
  615.                                  printf("Search has failed. Please, check list\n");
  616.                                  break;
  617.                              }
  618.                              printf("Max: %d\nMin: %d\n", minmax->maxValue->data, minmax->minValue->data);
  619.                              break;
  620.                 }
  621.                 case 11: {
  622.                              if (dllIsEmpty(list)) {
  623.                                  printf("List is empty\n");
  624.                                  break;
  625.                              }
  626.                              int value = enterInt();
  627.                              if (dllRemoveWith(list, value)){
  628.                                  printf("Remove successfully done\n");
  629.                                  break;
  630.                              }
  631.                 }
  632.                 case 12: {
  633.                              if (dllIsEmpty(list)) {
  634.                                  printf("List is empty\n");
  635.                                  break;
  636.                              }
  637.                              int value = enterInt();
  638.                              if (dllRemoveAllWith(list, value)){
  639.                                  printf("Remove successfully done\n");
  640.                                  break;
  641.                              }
  642.                 }
  643.                 case 13: {
  644.                              if (dllIsEmpty(list)) {
  645.                                  printf("List is empty\n");
  646.                                  break;
  647.                              }
  648.                              int value = enterInt();
  649.                              int newValue = enterInt();
  650.                              if (dllReplaceAll(list, value, newValue)){
  651.                                  printf("Replace successfully done\n");
  652.                                  break;
  653.                              }
  654.                              break;
  655.                 }
  656.                 case 14: {
  657.                              if (dllIsEmpty(list)) {
  658.                                  printf("List is empty\n");
  659.                                  break;
  660.                              }
  661.                              if (dllIsSymmetric(list)) {
  662.                                  printf("List is symmetric\n");
  663.                                  break;
  664.                              }
  665.                              else{
  666.                                  printf("List isn't symmetric\n");
  667.                                  break;
  668.                              }
  669.                 }
  670.                 case 15: {
  671.                              return 0;
  672.                 }
  673.                 }
  674.             }
  675.         }
  676.         else if (choice == '2') {
  677.             char* classicExpression = enterInfix("Enter infix form: ");
  678.             if (classicExpression == NULL) {
  679.                 printf("Invalid input\n");
  680.                 return 0;
  681.             }
  682.             int length = strlen(classicExpression);
  683.             printForm(infixToPostfix(classicExpression, length));
  684.         }
  685.     }
  686.  
  687.     return 0;
  688. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top