JavaScript (V8), 189 bytes

-10 thanks to @Ausername

s=>eval('i=0;do{c=(i++).toString(4).padStart(Math.log2(i)/2+1,0),(a=[...c]).reduce((r,x)=>[r+1,r+255,r*r,r,x^3||(o+=String.fromCharCode(r))][x]%256,0,o="")}while(o!=s);a.map(d=>"+-so"[d])')

Try it online!

Description:

Shameless brute-forcing. Increments a number, and converts it to base 4. It then interprets it as imnotdeadfish, and stops as soon as the result is equal to the input. Add n to the first 0 for infinitely large inputs. Didn't do this because it causes TIO to error.

JavaScript (V8), 187 bytes

-12 thanks to @Ausername

s=>eval('i=0;do{c=i.toString(4).padStart(Math.log2(++i)/2+1,0,o=""),(a=[...c]).reduce((r,x)=>[r+1,r+255,r*r,r,x^3||(o+=String.fromCharCode(r))][x]%256,0)}while(o!=s);a.map(d=>"+-so"[d])')

Try it online!

Description:

Shameless brute-forcing. Increments a number, and converts it to base 4. It then interprets it as imnotdeadfish, and stops as soon as the result is equal to the input. Add n to the first 0 for infinitely large inputs. Didn't do this because it causes TIO to error.

JavaScript, 199 bytes

s=>eval('i=0;do{c=(i++).toString(4).padStart(Math.log2(i)/2+1,0),[...c].reduce((r,x)=>[r+1,r+255,r**2,(x==3?(o+=String.fromCharCode(r)):0,r)][x]%256,0,o="")}while(o!=s);c.replace(/./g,d=>"+-so"[d])')

Try it online!

Description:

Shameless brute-forcing. Increments a number, and converts it to base 4. It then interprets it as imnotdeadfish, and stops as soon as the result is equal to the input. Add n to the first 0 for infinitely large inputs. Didn't do this because it causes TIO to error.

JavaScript (V8), 189 bytes

-10 thanks to @Ausername

s=>eval('i=0;do{c=(i++).toString(4).padStart(Math.log2(i)/2+1,0),(a=[...c]).reduce((r,x)=>[r+1,r+255,r*r,r,x^3||(o+=String.fromCharCode(r))][x]%256,0,o="")}while(o!=s);a.map(d=>"+-so"[d])')

Try it online!

Description:

Shameless brute-forcing. Increments a number, and converts it to base 4. It then interprets it as imnotdeadfish, and stops as soon as the result is equal to the input. Add n to the first 0 for infinitely large inputs. Didn't do this because it causes TIO to error.