1063.c

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

#define EXIT_WITH_ERROR(msg) fprintf(stderr, "%s\n", msg), exit(1)

struct Node
{
    char value;
    struct Node *next;
};

void push(struct Node **list, char value)
{
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    if(new_node) {
        new_node->value = value;
        new_node->next = *list;
        *list = new_node;
    } else {
        EXIT_WITH_ERROR("Error while allocating memory");
    }
}

void append(struct Node **list, char value)
{
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    if(new_node) {
        new_node->value = value;
        new_node->next = NULL;
        // if the list is not empty
        if(*list != NULL) {
            struct Node *aux = *list;
            while(aux->next != NULL) {
                aux = aux->next;
            }
            aux->next = new_node;    
        } else {
            *list = new_node;
        }
    } else {
        EXIT_WITH_ERROR("Error while allocating memory");
    }
}

struct Node *pop(struct Node **list)
{
    struct Node *remove = NULL;
    if(*list != NULL) {
        remove = *list;
        *list = remove->next;
    }
    return remove;
}

void clear(struct Node **list)
{
    while(*list != NULL) {
        free(pop(list));
    }
}

int main(int argc, char *argv[])
{
    int num;
    char wanted_str[70];
    char str[70];
    struct Node *remove_stack = NULL;
    struct Node *wanted_stack = NULL;
    struct Node *insert_queue = NULL;
    scanf("%d", &num);

    while(num != 0) {
        scanf(" %69[^\n]", str);
        scanf(" %69[^\n]", wanted_str);
        
        for(int i=0; str[i]!='\0'; i++) {
            if(str[i]>='a' && str[i]<='z') {
                append(&insert_queue, str[i]);
            } 
        }
        int length = strlen(str);
        for(int i=length-1; i>=0; i--) {
            if(wanted_str[i]>='a' && wanted_str[i]<='z') {
                push(&wanted_stack, wanted_str[i]);
            }
        }
       
        memset(str, 0, sizeof(str));

        while(insert_queue != NULL) {
            while(insert_queue != NULL && insert_queue->value != wanted_stack->value) {
                struct Node *aux = pop(&insert_queue); // I
                strcat(str, "I");
                push(&remove_stack, aux->value);
                free(aux);
            }
            if(insert_queue != NULL) {
                free(pop(&insert_queue)); // I
                free(pop(&wanted_stack));
                strcat(str, "IR");
            }
            while(remove_stack != NULL && wanted_stack != NULL && remove_stack->value == wanted_stack->value) {
                free(pop(&remove_stack));
                free(pop(&wanted_stack));
                strcat(str, "R");
            }
        }
        if(wanted_stack != NULL) {
            strcat(str, " Impossible");
        }
        printf("%s\n", str);
        scanf("%d", &num);
        clear(&wanted_stack);
        clear(&remove_stack);
        clear(&insert_queue);
    }

    return 0;
}