J

Didn't try to make it clever at all, so it's fairly slow (minutes, not seconds). Maybe rewriting foldl_ops in terms of destructive array update would improve matters, but the biggest problem is that I don't skip unnecessary calculations (because we've already found a match or already reached too big a number). This is concise and follows clearly from the definitions, however.

data_file_name =: '7.data
lines =: cutopen fread data_file_name
NB. parse_line yields a boxed vector of length 2, target ; operands
NB. &. is "under": u &. v is v^:_1 @: u @: v with right rank of v
parse_line =: monad : '(". &. >) (>y) ({.~ ; (}.~ >:)) '':'' i.~ >y'
NB. m foldl_ops n left folds n by the string of binary operators named by m,
NB. as indices into the global operators, the leftmost element of m naming
NB. an operator between the leftmost two elements of n. #m must be #n - 1.
foldl_ops =: dyad define
   if. 1 >: # y do. {. y else.
      (}. x) foldl_ops (((operators @. ({. x))/ 2 {. y) , 2 }. y)
   end.
)
NB. b digit_strings n enumerates i.b^n as right justified digit strings
digit_strings =: dyad : '(y # x) #:"1 0 i. x ^ y'
feasible =: dyad define
   operators =: x  NB. global
   'target operands' =. y
   +./ target = ((# operators) digit_strings (<: # operands)) foldl_ops"1 operands
)
compute =: monad : '+/ ((> @: {.) * (y & feasible))"1 parse_line"0 lines'
result1 =: compute +`*

concat =: , &.: (10 & #.^:_1)
result2 =: compute +`*`concat