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}