From Mustard Hog, 5 Months ago, written in Text.
Embed
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5.  
  6. typedef struct LINKED_STACK_NODE_s *LINKED_STACK_NODE;
  7.  
  8.  
  9. typedef struct LINKED_STACK_NODE_s{
  10.         LINKED_STACK_NODE next;
  11.         void *data;
  12. }LINKED_STACK_NODE_t[1];
  13.  
  14. typedef struct LINKED_STACK_s{
  15.         LINKED_STACK_NODE head;
  16.         int count;
  17. }LINKED_STACK_t[1], *LINKED_STACK;
  18.  
  19.  
  20.  
  21. //push, pop, top, init, free, isempty
  22.  
  23. LINKED_STACK stack_init();
  24. void stack_free(LINKED_STACK stack);
  25. void stack_push(LINKED_STACK stack, void* data);
  26. void* stack_pop(LINKED_STACK stack);
  27. void* stack_top(LINKED_STACK stack);
  28. int is_empty(LINKED_STACK stack);
  29.  
  30. int is_empty(LINKED_STACK stack){
  31.        
  32.         if(stack->head == NULL)
  33.         {
  34.                 return 1;
  35.         }else
  36.         {
  37.                 return 0;
  38.         }
  39. }
  40.  
  41. LINKED_STACK stack_init()
  42. {
  43.         LINKED_STACK stack = (LINKED_STACK)malloc(sizeof(LINKED_STACK_t));
  44.         if(stack == NULL)
  45.         {
  46.                 printf("\nproblem with initializing stack\n\n");
  47.                 return NULL;
  48.         }
  49.         stack->head = NULL;
  50.         stack->count = 0;
  51.         return stack;
  52. }
  53.  
  54. void stack_free(LINKED_STACK stack){
  55.        
  56.         while(is_empty(stack) == 0)
  57.         {
  58.                 stack_pop(stack);
  59.         }
  60.         free(stack);
  61. }
  62. void stack_push(LINKED_STACK stack, void* data)
  63. {      
  64.         LINKED_STACK_NODE node = (LINKED_STACK_NODE)malloc(sizeof(LINKED_STACK_NODE_t));
  65.         if(node == NULL)
  66.         {
  67.                 printf("\nproblem with the creation of a node\n\n");
  68.                 return;
  69.         }
  70.         node->data = data;
  71.         node->next = stack->head;
  72.         stack->head = node;
  73.         stack->count++;
  74. }
  75.  
  76. void* stack_pop(LINKED_STACK stack)
  77. {
  78.         LINKED_STACK_NODE node;
  79.         void* data = NULL;
  80.  
  81.         if(stack->head != NULL)
  82.         {
  83.                 node = stack->head;
  84.                 data = node->data;
  85.                 stack->head = node->next;
  86.                 stack->count--;
  87.                 free(node);
  88.                
  89.         }else{
  90.                 printf("\nstack is empty:pop\n\n");
  91.         }
  92.         return data;
  93. }
  94.  
  95. void* stack_top(LINKED_STACK stack)
  96. {
  97.        
  98.         LINKED_STACK_NODE node;
  99.         void* data = NULL;
  100.  
  101.         if(stack->head != NULL)
  102.         {
  103.                 data = stack->head->data;
  104.                
  105.         }else{
  106.                 printf("\nstack is empty:top\n\n");
  107.         }
  108.         return data;
  109. }
  110.  
  111. int isOperator(char c) {
  112.         if (c == '+')
  113.                 return 1;
  114.         else if (c == '-')
  115.                 return 1;
  116.         else if (c == '*')
  117.                 return 1;
  118.         else if (c == '/')
  119.                 return 1;
  120.         else
  121.                 return 0;
  122. }
  123.  
  124. int priority(char c) {
  125.         if (c == '(')
  126.                 return 0;
  127.         else if (c == '+' || c == '-')
  128.                 return 1;
  129.         else if (c == '*' || c == '/')
  130.                 return 2;
  131.         else
  132.                 return -1;
  133. }
  134.  
  135. void evoluation(char *output, LINKED_STACK stack)
  136. {
  137.         int data1 , data2 , ans , leng = strlen(output) , i ;
  138.        
  139.         for(i=0 ; i<leng ; i++)
  140.         {
  141.                 if(isOperator(output[i]) == 1)
  142.                 {
  143.                         data1 = *(int *)stack_pop(stack);
  144.                         data2 = *(int *)stack_pop(stack);
  145.                        
  146.                         if(output[i] = '+')
  147.                         {
  148.                                 ans = data1 + data2;
  149.                                 stack_push(stack,&ans);
  150.                         }
  151.                         if(output[i] = '-')
  152.                         {
  153.                                 ans = data1 - data2;
  154.                                 stack_push(stack,&ans);
  155.                         }
  156.                         if(output[i] = '*')
  157.                         {
  158.                                 ans = data1 * data2;
  159.                                 stack_push(stack,&ans);
  160.                         }
  161.                         if(output[i] = '/')
  162.                         {
  163.                                 ans = data1 / data2;
  164.                                 stack_push(stack,&ans);
  165.                         }
  166.                 }
  167.                
  168.                 else
  169.                         stack_push(stack,output[i]);
  170.         }
  171.         printf("answer is %d", ans);
  172. }
  173.  
  174. char* infixToPosfix(LINKED_STACK stack, char* str) {
  175.         int len = strlen(str);
  176.         int i, j = 0;
  177.         char *output = (char*) malloc(sizeof(char) * len);
  178.         for (i = 0; i < len; ++i) {
  179.  
  180.                 if (str[i] == '(') {
  181.                         stack_push(stack, &str[i]);
  182.                 } else if (isOperator(str[i]) == 1) {
  183.  
  184.                         while ((is_empty(stack)==0) && (priority(str[i]) <= priority(*(char*) stack_top(stack)))) {
  185.                                 char* poped = (char*) stack_pop(stack);
  186.                                 output[j] = *poped;
  187.                                 j++;
  188.                         }
  189.  
  190.                         stack_push(stack, &str[i]);
  191.                 } else if (str[i] == ')') {
  192.                         char *poped;
  193.                         while (*(poped = (char*) stack_pop(stack)) != '(') {
  194.  
  195.                                 output[j] = *poped;
  196.                                 j++;
  197.                         }
  198.                 } else {
  199.                         output[j] = str[i];
  200.                         j++;
  201.                 }
  202.  
  203.         }
  204.         while (is_empty(stack)==0)
  205.         {
  206.                 char* poped = (char*) stack_pop(stack);
  207.                 output[j] = *poped;
  208.                 j++;
  209.         }
  210.         evoluation(output,stack);
  211.         return output;
  212. }
  213. int main()
  214. {
  215.         char *str = "6+4(3+2*5)-5";
  216.         LINKED_STACK s = stack_init();
  217.        
  218.        
  219.         infixToPosfix(s,str);
  220.        
  221.        
  222.        
  223.        
  224.        
  225.  
  226. }