API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 16th, 2019
105
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 13.85 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!