Задачка достаточно сложная :)

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

typedef struct __stack{
	struct __stack *prev;
	char data;
} stack;

int pop(stack **S){
	if(!*S) return -1; // stack is empty
	char r = (*S)->data;
	stack *o = *S;
	if((*S)->prev)
		*S = (*S)->prev;
	else
		*S = NULL;
	free(o);
printf("pop %c\n", r);
	return r;
}

void push(stack **S, char c){
	stack *s = calloc(1, sizeof(stack));
	s->data = c;
	if(!*S) *S = s;
	else{
		s->prev = *S;
		*S = s;
	}
printf("push %c\n", c);
}

int nondestructive_pop(stack **S){
	if(!*S) return -1;
	return (*S)->data;
}

int main(int argc, char **argv){
	char *word, *result, *iptr, *optr, *newword, *nptr, ch;
	stack *S = NULL;
	if(argc != 3){
		printf("Usage: %s word1 word2\n", argv[0]);
		return 1;
	}
	word = strdup(argv[1]);
	result = strdup(argv[2]);
	iptr = word, optr = result;
	if(strlen(word) != strlen(result)){
		printf("Strlen of word1 and word2 should be the same!\n");
		return 2;
	}
	newword = calloc(strlen(result)+1, 1);
	nptr = newword;
	for(; *iptr || S; ){
		ch = *iptr;
printf("compare %c and %c\n", ch, *optr);
		if(ch == *optr){
			*nptr++ = ch;
			optr++;
			iptr++;
			continue;
		}
		if(!S){
			push(&S, ch);
			iptr++;
			continue;
		}
		if(nondestructive_pop(&S) != *optr){
			if(ch){
				push(&S, ch);
				iptr++;
			}else break;
		}else{
			*nptr++ = pop(&S);
			optr++;
		}
	}
	if(strcmp(newword, result)) printf("Impossible!\n");
	else printf("All OK!\n");
	return 0;
}