Infix to Prefix Expression Linked List

Please kindly advise why my current output is not as per expected output and the possible solution:

Write a function, in2preLL() to convert an infix expression into a prefix expression linked list. We assumed that the character string only contains positive integer numbers, operators ('+' , '-', '*', '/' ) and parenthesis.

The function prototype is given as follows:

void in2preLL (char *infix, LinkedList *inExpLL)

Example:

input:

99+(88-77)*(66/(55-44)+33)

Expected output:

+ 99 * - 88 77 + / 66 - 55 44 33

Current output:

+ 9 9 * - 8 8 7 7 + / 6 6 - 5 5 4 4 3 3

My code as below:

#include #include #define SIZE 1000 //The size of the arrayenum ExpType {OPT,OPERAND};typedef struct _stackNode{ char item; struct _stackNode *next;}StackNode;typedef struct _stack{ int size; StackNode *head;}Stack;void push(Stack *sPtr, char item);int pop(Stack *sPtr);char peek(Stack s);int isEmptyStack(Stack s);typedef struct _listnode{ int item; enum ExpType type; struct _listnode *next;} ListNode;typedef struct _linkedlist{ int size; ListNode *head;} LinkedList;void insertNode(LinkedList *llPtr, int item,enum ExpType type);int deleteNode(LinkedList *llPtr);void removeAllNodes(LinkedList *llPtr);int isEmptyLinkedList (LinkedList ll);void in2PreLL(char* infix, LinkedList *inExpLL);void printExpLL(LinkedList inExp);int main(){ char infix[SIZE]; //printf("Enter an infix expression: "); scanf("%[^ ]%*c",infix); LinkedList inExpLL; inExpLL.head = NULL; inExpLL.size = 0; in2PreLL(infix, &inExpLL); printExpLL(inExpLL); removeAllNodes(&inExpLL); return 0;}void printExpLL(LinkedList inExpLL){ ListNode* temp = NULL; temp = inExpLL.head; while(temp!= NULL){ if(temp->type == OPERAND) printf(" %d ",temp->item); else printf(" %c ",(char)(temp->item)); temp = temp->next; } printf(" ");}void insertNode(LinkedList *LLPtr, int item, enum ExpType type) { ListNode *newNode; newNode = malloc(sizeof(ListNode)); if(newNode==NULL) exit(0); newNode->item = item; newNode->type = type; newNode->next = LLPtr->head; LLPtr->head=newNode; LLPtr->size++;}int deleteNode(LinkedList *LLPtr) { if(LLPtr==NULL || LLPtr->size==0){ return 0; } else{ ListNode *temp = LLPtr->head; LLPtr->head = LLPtr->head->next; free(temp); LLPtr->size--; return 1; }}int isEmptyLinkedList (LinkedList ll) { if(ll.size==0) return 1; else return 0;}void removeAllNodes(LinkedList *LLPtr){ while(deleteNode(LLPtr));}void push(Stack *sPtr, char item){ StackNode *newNode; newNode = malloc(sizeof(StackNode)); newNode->item = item; newNode->next = sPtr->head; sPtr->head = newNode; sPtr->size++;}int pop(Stack *sPtr){ if(sPtr == NULL || sPtr->head == NULL){ return 0; } else{ StackNode *temp = sPtr->head; sPtr->head = sPtr->head->next; free(temp); sPtr->size--; return 1; }}char peek(Stack s){ return s.head->item;}int isEmptyStack(Stack s){ if(s.size == 0) return 1; else return 0;}int precedence(char op){ if(op=='*' || op=='/') return 1; else return 0;}void in2PreLL(char* infix, LinkedList *inExpLL){ //Write your code here Stack s; ListNode *temp=NULL,*cur,*pre=NULL; s.head=NULL; s.size=0; int i=0,j=0; char inRev[SIZE],c; while(infix[i]!='\0') { i++; } for(j=i-1; j>=0; j--) { inRev[i-1-j]=infix[j]; } inRev[i]='\0'; j=0; while(j { c=inRev[j++]; switch(c) { case '*': case '/': case '+': case '-': while(!isEmptyStack(s) && peek(s)!=')' && precedence(peek(s))>precedence(c)) { insertNode(inExpLL,(int)(peek(s)),OPT); pop(&s); } push(&s,c); break; case ')': push(&s,c); break; case '(': while(!isEmptyStack(s)) { if(peek(s)!=')') { insertNode(inExpLL,(int)(peek(s)),OPT); pop(&s); } else { pop(&s); break; } } break; default: insertNode(inExpLL,(c-'0'),OPERAND); } } while(isEmptyStack(s)==0) { insertNode(inExpLL,peek(s),OPT); pop(&s); } cur=inExpLL->head; return;}