Priority to the right
Perl, 65 bytes

Includes +2 for -lp

Give input on STDIN. Assumes the empty string is not a valid input

#!/usr/bin/perl -lp
s%.%'+(y/NESW/ESWN/*s/N(.*)W/W$1N/,/N/^/S/)'x4%gere+0or$_=stuck


If you don't mind the absence of a newline after stuck you can drop the l option