Change C programs from using arrays to using linked list

Question

I'm a beginner in C. I have written a 'infix, prefix, postfix conversion' program using arrays. But now I would like to change the program to use linked list to illustrate the stack.

Could anyone help modify this small part of the codes to use linked list so I can see the pattern and understand how it works ? Thank you.

Here's the code for 'prefix to infix conversion'

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>



char PrefixToInfix(char expression[]){

char *input,ans[50],answer[50][50],opr[3],temp[5]; //Initializing variables
char stack2[50],stack1[50],opstack[50],optemp;
int topa=-1,topops=-1,counter=0;
input=expression;



for( ;*input!= '\0';input++)
{
    if (*input==' ') input++;

    if (isalnum(*input)) //Checking for digit
    {
        temp[0]=*input;
        input++;
        if(isalnum(*input)){ //In double digit cases
            temp[1]=*input;
            temp[2]='\0';
        }
        else
        {
        temp[1]='\0';
            input--;
        }
    strcpy(answer[++topa],temp); //Push to stack
    counter++;
    if(counter >= 2)
    {
    strcpy(stack2,answer[topa--]); //Pop 2 operand from stack and put the operator in between them, with a parenthesis opening and closing it, and push it into stack
    strcpy(stack1,answer[topa--]);
    strcpy(ans,"(");
    strcat(ans," ");
    strcat(ans,stack1);
    strcat(ans," ");
    optemp=opstack[topops--];
    opr[0]=optemp;
    opr[1]='\0';
    strcat(ans,opr);
    strcat(ans," ");
    strcat(ans,stack2);
    strcat(ans," ");
    strcat(ans,")");
    strcpy(answer[++topa],ans);
    counter--;
    }
}
else
{
    opstack[++topops]=*input; //If operator found add to operator stack
    if(counter==1)counter=0;
}

}
while(topa!=0)
{
strcpy(stack2,answer[topa--]); //Pop 2 operand from stack and put the operator in between them, with a parenthesis opening and closing it, and push it into stack
strcpy(stack1,answer[topa--]);
strcpy(ans,"(");
strcat(ans," ");
strcat(ans,stack1);
strcat(ans," ");
optemp=opstack[--topops];
opr[0]=optemp;
opr[1]='\0';
strcat(ans,opr);
strcat(ans," ");
strcat(ans,stack2);
strcat(ans," ");
strcat(ans,")");
strcpy(answer[++topa],ans);
}
printf("Infix Expression: ");
printf("%s\n",answer[topa]);

}

int main(){

char exp[50];

printf("enter expression: ");
scanf(" %20[^\n]", exp);
PrefixToInfix(exp);


}

Answer 1

Here is a way to transform the existing source code from fixed-array stack to linked-list stack. As @KamiKaze suggests, the first step will be to create a linked-list able to be manage as a stack.

Step 1 - create the linked-list structure.

typedef struct sStack {
    char *value;
    struct sStack *next;
} Stack;

Step 2 - add push() and pop() function to manage the linked-list as a stack.

Stack *pushStack(Stack *pStack, char *answer)
{
    Stack *pTemp = malloc(sizeof(Stack));
    pTemp->next = pStack;
    pTemp->value = malloc(strlen(answer)+1);
    strcpy(pTemp->value,answer);
    return (pTemp);
}

Stack *popStack(Stack *pStack, char *answer)
{
    Stack *pTemp = NULL;

    if (pStack != NULL) {
        strcpy(answer,pStack->value);
        pTemp = pStack->next;
        free(pStack->value);
        free(pStack);
        return (pTemp);
    }
    // to prevent error
    strcpy(answer,"");
    return (pTemp);
}

Step 3 - declare and initialize two stacks in PrefixToInfix(): valStack to store values and opStack to store operators.

char PrefixToInfix(char expression[])
{
    Stack *valStack = NULL;
    Stack *opStack = NULL;
    char sOpTmp[3];

Step 4 - when add a new value or a new operator in the stack, use the function pushStack()

// to push a value
valStack = pushStack(valStack, temp);
// to push operator
sprintf(sOpTmp,"%c",*input);
opStack = pushStack(opStack,sOpTmp);

Instead of

// adding a value
strcpy(answer[++topa],temp);
// adding an operator
opstack[++topops]=*input;

Step 5 - when remove a value or an operator from the stack, use the function popStack()

// to pop values
valStack = popStack(valStack, stack2);
valStack = popStack(valStack, stack1);
// to pop an operator
opStack = popStack(opStack,opr);

Instead of

// removing values
strcpy(stack2,answer[topa--]);
strcpy(stack1,answer[topa--]);
// removing an operator
optemp=opstack[topops--];
opr[0]=optemp;
opr[1]='\0';

Step 6 - the while-condition checks the valStack pointers.

When valStack->next is NULL, the valStack->value contains the complete Infix expression.

while((valStack!=NULL) && (valStack->next!=NULL))
{

Instead of

while(topa!=0)
{

Last Step - display the Infix expression

To prevent a bad return value due to valStack == NULL, use the popStack() function instead of valStack->value.

valStack = popStack(valStack, ans);
printf("%s\n",ans);

Instead of

printf("%s\n",answer[topa]);