From Big Parrot, 1 Week 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 evaluate_Postfix(char *output, LINKED_STACK stack)
  136. {
  137.         int op1 , op2 , result , len = strlen(output) , i ,value;
  138.        
  139.         for(i=0 ; i<len ; i++)
  140.         {
  141.                 if(isOperator(output[i]) == 1)
  142.                 {
  143.                         op1 = *(int *)stack_pop(stack);
  144.                         op2 = *(int *)stack_pop(stack);
  145.                        
  146.                         switch (output[i])
  147.                                 {
  148.                                         case '+': result=op1+op2; stack_push(stack,&result); break;
  149.                                         case '-': result=op1-op2; stack_push(stack,&result); break;
  150.                                         case '*': result=op1*op2; stack_push(stack,&result); break;
  151.                                         case '/': result=op1/op2; stack_push(stack,&result); break;
  152.                                 }                                                
  153.                 }
  154.                 else
  155.                         stack_push(stack,&output[i]);
  156.         }
  157.         result = *(int *)stack_pop(stack);
  158.                 printf("Answer is %d", result);
  159. }
  160.  
  161. char* infixToPosfix(LINKED_STACK stack, char* str) {
  162.         int len = strlen(str);
  163.         int i, j = 0;
  164.         char *output = (char*) malloc(sizeof(char) * len);
  165.         for (i = 0; i < len; ++i) {
  166.  
  167.                 if (str[i] == '(') {
  168.                         stack_push(stack, &str[i]);
  169.                 } else if (isOperator(str[i]) == 1) {
  170.  
  171.                         while ((is_empty(stack)==0) && (priority(str[i]) <= priority(*(char*) stack_top(stack)))) {
  172.                                 char* poped = (char*) stack_pop(stack);
  173.                                 output[j] = *poped;
  174.                                 j++;
  175.                         }
  176.  
  177.                         stack_push(stack, &str[i]);
  178.                 } else if (str[i] == ')') {
  179.                         char *poped;
  180.                         while (*(poped = (char*) stack_pop(stack)) != '(') {
  181.                                
  182.                                 output[j] = *poped;
  183.                                 j++;
  184.                         }
  185.                 } else {
  186.                         output[j] = str[i];
  187.                         j++;
  188.                 }
  189.  
  190.         }
  191.         while (is_empty(stack)==0)
  192.         {
  193.                 char* poped = (char*) stack_pop(stack);
  194.                 output[j] = *poped;
  195.                 j++;
  196.         }
  197.         evaluate_Postfix(output,stack);
  198.         return output;
  199. }
  200. int main()
  201. {
  202.         char *str="6+4(3+25)-5";
  203.         LINKED_STACK s = stack_init();
  204.         infixToPosfix(s,str);
  205. }