how about using string operations:
In[54]:= nums = {"4", "5", "1", "18"}
Out[54]= {"4", "5", "1", "18"}
In[55]:= ops = Permutations[{"+", "-", "*", "^"}, {3}]
Out[55]= {{"+", "-", "*"}, {"+", "-", "^"}, {"+", "*", "-"}, {"+",
"*", "^"}, {"+", "^", "-"}, {"+", "^", "*"}, {"-", "+", "*"}, {"-",
"+", "^"}, {"-", "*", "+"}, {"-", "*", "^"}, {"-", "^", "+"}, {"-",
"^", "*"}, {"*", "+", "-"}, {"*", "+", "^"}, {"*", "-", "+"}, {"*",
"-", "^"}, {"*", "^", "+"}, {"*", "^", "-"}, {"^", "+", "-"}, {"^",
"+", "*"}, {"^", "-", "+"}, {"^", "-", "*"}, {"^", "*", "+"}, {"^",
"*", "-"}}
In[56]:= d = First[Dimensions[%]]
Out[56]= 24
In[57]:= Table[StringJoin[Riffle[nums, ops[[i, All]]]], {i, d}]
Out[57]= {"4+5-1*18", "4+5-1^18", "4+5*1-18", "4+5*1^18", "4+5^1-18", \
"4+5^1*18", "4-5+1*18", "4-5+1^18", "4-5*1+18", "4-5*1^18", \
"4-5^1+18", "4-5^1*18", "4*5+1-18", "4*5+1^18", "4*5-1+18", \
"4*5-1^18", "4*5^1+18", "4*5^1-18", "4^5+1-18", "4^5+1*18", \
"4^5-1+18", "4^5-1*18", "4^5*1+18", "4^5*1-18"}
In[59]:= list = ToExpression[%]
Out[59]= {-9, 8, -9, 9, -9, 94, 17, 0, 17, -1, 17, -86, 3, 21, 37, \
19, 38, 2, 1007, 1042, 1041, 1006, 1042, 1006}