Advertisement
WONGDEEM

Untitled

Mar 24th, 2021
1,030
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define SIZE 80 //The size of the array
  5.  
  6. enum ExpType {OPT,OPERAND};
  7.  
  8. typedef struct _stackNode{
  9.     char item;
  10.     struct _stackNode *next;
  11. }StackNode;
  12.  
  13. typedef struct _stack{
  14.    int size;
  15.    StackNode *head;
  16. }Stack;
  17.  
  18. typedef struct _stackNode2{
  19.     char item[SIZE];
  20.     struct _stackNode *next;
  21. }StackNode2;
  22.  
  23. typedef struct _stack2{
  24.    int size;
  25.    StackNode *head;
  26. }Stack2;
  27.  
  28. void push(Stack *sPtr, char item);
  29. void push2(Stack2 *sPtr, char item);
  30. int pop(Stack *sPtr);
  31. int pop2(Stack2 *sPtr);
  32. char peek(Stack s);
  33. char peek2(Stack2 s);
  34. int isEmptyStack(Stack s);
  35. int isEmptyStack2(Stack2 s);
  36.  
  37. typedef struct _listnode
  38. {
  39.     int  item;
  40.     enum ExpType type;
  41.     struct _listnode *next;
  42. } ListNode;
  43.  
  44. typedef struct _linkedlist{
  45.    int size;
  46.    ListNode *head;
  47. } LinkedList;
  48.  
  49. void insertNode(LinkedList *llPtr, int item,enum ExpType type);
  50. int deleteNode(LinkedList *llPtr);
  51. void removeAllNodes(LinkedList *llPtr);
  52. int isEmptyLinkedList (LinkedList ll);
  53.  
  54.  
  55. void in2PreLL(char* infix, LinkedList *inExpLL);
  56.  
  57. void printExpLL(LinkedList inExpLL);
  58.  
  59. int isOperand(char c) {
  60.   return ((c >= 'a' && c <= 'z') || (c >='A' && c <= 'Z')) ? 1 : 0;
  61. }
  62.  
  63. int isOperator(char c) {
  64.   return (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') ? 1: 0;
  65. }
  66. int prec(char c) {
  67.   switch (c) {
  68.     case '+':
  69.     case '-':
  70.       return 1;
  71.  
  72.     case '*':
  73.     case '/':
  74.       return 2;
  75.     }
  76.     return -1;
  77. }
  78.  
  79. void insertNodeToBack(LinkedList *llPtr, int item, enum ExpType type) {
  80.   ListNode *newNode = malloc(sizeof(ListNode));
  81.   ListNode *currNode = llPtr->head;
  82.  
  83.   newNode->item = item;
  84.   newNode->type = type;
  85.   newNode->next = NULL;
  86.  
  87.   if (currNode == NULL) {
  88.     llPtr->head = newNode;
  89.     return;
  90.   }
  91.   while (currNode != NULL && currNode->next != NULL) {
  92.     currNode = currNode->next;
  93.   }
  94.   currNode->next = newNode;
  95. }
  96.  
  97.  
  98. void reverse(ListNode** head_ref) {
  99.     ListNode *prev = NULL;
  100.     ListNode *current = *head_ref;
  101.     ListNode *next = NULL;
  102.     while (current != NULL) {
  103.         if (current->item == '(') current->item = ')';
  104.         else if (current->item == ')') current->item = '(';
  105.         next = current->next;
  106.         current->next = prev;
  107.         prev = current;
  108.         current = next;
  109.     }
  110.     *head_ref = prev;
  111. }
  112.  
  113.  
  114.  
  115. void in2Post(LinkedList *infix, LinkedList *postfix) {
  116.     Stack2 s;
  117.     s.head = NULL;
  118.     s.size = 0;
  119.  
  120.     int i = 0;
  121.     int j = 0;
  122.     int sum = 0;
  123.     char tempInt[SIZE], c[SIZE];
  124.     ListNode *currentNode = infix->head;
  125.     while(i<SIZE && currentNode != NULL) {
  126.         if (currentNode->type == OPERAND) {
  127.           sprintf(tempInt, "%d", currentNode->item);
  128.         } else {
  129.           tempInt[0] = (char) currentNode->item;
  130.           tempInt[1] = '\0';
  131.         }
  132.         if (tempInt[0] < 1 || tempInt[0] > 255) {
  133.           currentNode = currentNode->next;
  134.           continue;
  135.         }
  136.         switch(tempInt[0])
  137.         {
  138.         case '*': //operators
  139.         case '/':
  140.         case '+':
  141.         case '-':
  142.             while(isEmptyStack2(s)==0 && peek2(s) != '(' && prec(peek2(s)) >= prec(tempInt[0]) )
  143.             {
  144.                 insertNodeToBack(postfix,peek2(s),OPT);
  145.                 pop2(&s);
  146.             }
  147.             push2(&s,tempInt[0]);
  148.             currentNode = currentNode->next;
  149.             break;
  150.         case '(':
  151.             push2(&s,tempInt[0]);
  152.             currentNode = currentNode->next;
  153.             break;
  154.         case ')':
  155.             while(isEmptyStack2(s)==0)
  156.             {
  157.                 if(peek2(s)!='(')
  158.                 {
  159.                     insertNodeToBack(postfix,peek2(s),OPT);
  160.                     pop2(&s);
  161.                 }
  162.                 else
  163.                 {
  164.                     pop2(&s);
  165.                     break;
  166.                 }
  167.             }
  168.             currentNode = currentNode->next;
  169.             break;
  170.         default: //operand
  171.             insertNodeToBack(postfix,atoi(tempInt),OPERAND);
  172.             currentNode = currentNode->next;
  173.  
  174.         }
  175.     }
  176.  
  177.     while(isEmptyStack2(s)==0)
  178.     {
  179.         insertNodeToBack(postfix,peek2(s),OPT);
  180.         pop2(&s);
  181.     }
  182. }
  183.  
  184. void expressionLL(char* infix, LinkedList *inExpLL) {
  185.   //init variables
  186.   char tempInt[SIZE]; // to store the string of numbers
  187.   int index = 0;
  188.  
  189.   while (*infix != '\0') {
  190.     tempInt[0] = '\0';
  191.     ListNode *temp = malloc(sizeof(ListNode));
  192.  
  193.     //handles insertion of ListNode into the linked list
  194.     if (inExpLL->head == NULL) inExpLL->head = temp;
  195.     else {
  196.       ListNode *currNode = inExpLL->head;
  197.       while (currNode->next != NULL) currNode = currNode->next;
  198.       currNode->next = temp;
  199.     }
  200.  
  201.     //checks where the number ends
  202.     while (*infix>=48 && *infix != '\0') {
  203.       tempInt[index] = *infix;
  204.       infix++;
  205.       index++;
  206.     }
  207.     tempInt[index] = '\0';
  208.     //checks if tempInt is populated with numbers. If not, then insert a node that is an operator
  209.     temp->item = (tempInt[0] == '\0') ? *infix : atoi(tempInt);
  210.     temp->type = (tempInt[0] == '\0') ? OPT : OPERAND;
  211.  
  212.     //if temp's type is OPERAND, insert the current char from infix bc it will be an operator
  213.     if (*infix != '\0' && temp->type != OPT) {
  214.       ListNode *tempOpt = malloc(sizeof(ListNode));
  215.       tempOpt->item = *infix;
  216.       tempOpt->type = OPT;
  217.       temp->next = tempOpt;
  218.     }
  219.     if (*infix != '\0') {
  220.       infix++;
  221.     } else {
  222.       break;
  223.     }
  224.  
  225.     //resets vars for next loop
  226.     tempInt[0] = '\0';
  227.     index = 0;
  228.   }
  229. }
  230.  
  231. int main()
  232. {
  233.     char infix[SIZE];
  234.  
  235.     //printf("Enter an infix expression:\n");
  236.     gets(infix);
  237.  
  238.     LinkedList inExpLL;
  239.     inExpLL.head = NULL;
  240.     inExpLL.size = 0;
  241.  
  242.     in2PreLL(infix, &inExpLL);
  243.  
  244.     printExpLL(inExpLL);
  245.  
  246.     removeAllNodes(&inExpLL);
  247.     return 0;
  248. }
  249.  
  250. void in2PreLL(char* infix, LinkedList *inExpLL)
  251. {
  252.   char tempInt[SIZE];
  253.   LinkedList *infixLL = malloc(sizeof(LinkedList));
  254.   expressionLL(infix,infixLL);
  255.   ListNode *currentNode = infixLL->head;
  256.   while (currentNode != NULL) {
  257.     currentNode = currentNode->next;
  258.   }
  259.   reverse(&(infixLL->head));
  260.   currentNode = infixLL->head;
  261.   while (currentNode != NULL) {
  262.     currentNode = currentNode->next;
  263.   }
  264.  
  265.   in2Post(infixLL,inExpLL);
  266.   reverse(&(inExpLL->head));
  267.   currentNode = inExpLL->head;
  268.   // while (currentNode != NULL) {
  269.   //   printf("%d ",currentNode->item);
  270.   //   currentNode = currentNode->next;
  271.   // }
  272.   // printf("\n");
  273. }
  274.  
  275. void printExpLL(LinkedList inExpLL)
  276. {
  277.     ListNode* temp = NULL;
  278.     temp = inExpLL.head;
  279.     while(temp!= NULL){
  280.         if(temp->type == OPERAND)
  281.             printf(" %d ",temp->item);
  282.         else
  283.             printf(" %c ",(char)(temp->item));
  284.         temp = temp->next;
  285.     }
  286.     printf("\n");
  287. }
  288.  
  289. void insertNode(LinkedList *LLPtr, int item, enum ExpType type) {
  290.     ListNode *newNode;
  291.     newNode = malloc(sizeof(ListNode));
  292.     if(newNode==NULL) exit(0);
  293.  
  294.     newNode->item = item;
  295.     newNode->type = type;
  296.     newNode->next = LLPtr->head;
  297.     LLPtr->head=newNode;
  298.     LLPtr->size++;
  299. }
  300.  
  301. int deleteNode(LinkedList *LLPtr) {
  302.     if(LLPtr==NULL || LLPtr->size==0){
  303.         return 0;
  304.     }
  305.     else{
  306.        ListNode *temp = LLPtr->head;
  307.        LLPtr->head = LLPtr->head->next;
  308.  
  309.        free(temp);
  310.        LLPtr->size--;
  311.        return 1;
  312.     }
  313. }
  314.  
  315. int isEmptyLinkedList (LinkedList ll) {
  316.     if(ll.size==0) return 1;
  317.     else return 0;
  318. }
  319.  
  320. void removeAllNodes(LinkedList *LLPtr)
  321. {
  322.     while(deleteNode(LLPtr));
  323. }
  324.  
  325. void push(Stack *sPtr, char item){
  326.     StackNode *newNode;
  327.     newNode = malloc(sizeof(StackNode));
  328.     newNode->item = item;
  329.     newNode->next = sPtr->head;
  330.     sPtr->head = newNode;
  331.     sPtr->size++;
  332. }
  333.  
  334. void push2(Stack2 *sPtr, char item){
  335.     StackNode *newNode;
  336.     newNode = malloc(sizeof(StackNode));
  337.     newNode->item = item;
  338.     newNode->next = sPtr->head;
  339.     sPtr->head = newNode;
  340.     sPtr->size++;
  341. }
  342.  
  343. int pop(Stack *sPtr){
  344.     if(sPtr == NULL || sPtr->head == NULL){
  345.         return 0;
  346.     }
  347.     else{
  348.        StackNode *temp = sPtr->head;
  349.        sPtr->head = sPtr->head->next;
  350.        free(temp);
  351.        sPtr->size--;
  352.        return 1;
  353.     }
  354. }
  355.  
  356. int pop2(Stack2 *sPtr){
  357.     if(sPtr == NULL || sPtr->head == NULL){
  358.         return 0;
  359.     }
  360.     else{
  361.        StackNode *temp = sPtr->head;
  362.        sPtr->head = sPtr->head->next;
  363.        free(temp);
  364.        sPtr->size--;
  365.        return 1;
  366.     }
  367. }
  368.  
  369. char peek(Stack s){
  370.     return s.head->item;
  371. }
  372.  
  373. char peek2(Stack2 s){
  374.     return s.head->item;
  375. }
  376.  
  377. int isEmptyStack(Stack s){
  378.      if(s.size == 0) return 1;
  379.      else return 0;
  380. }
  381.  
  382. int isEmptyStack2(Stack2 s){
  383.      if(s.size == 0) return 1;
  384.      else return 0;
  385. }
  386.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement