#!/usr/bin/python

#char_set = ['1','2','3','4','5','6','7','8','9','+','-','*','/']
char_set = ['1','2','3','4','5','6','7','+','-','*','/']
best_str = ""
best_val = 0

def is_op(c):
  if (c=='+' or c=='-' or c=='*' or c=='/'):
    return 1
  else:
    return 0

def is_legal(str):
  if is_op(str[0]):
    return 0
  elif is_op(str[len(str)-1]):
    return 0
  else:
    for i in range(len(str)-1):
      if is_op(str[i]) and is_op(str[i+1]):
        return 0
    return 1


def permute_and_evaluate(current_str, char_list):
  global best_str
  global best_val

  if len(char_list) == 0:
    if is_legal(current_str):
      current_val = eval(current_str)
      if (current_val > best_val):
        best_val = current_val
        best_str = current_str
        print "best string so far: ", best_str
        print "value is : ", best_val
        print " "
  else:
    for c in char_list:
      next_str = current_str + str(c)
      next_char_list = list(char_list)
      next_char_list.remove(c)
      permute_and_evaluate(next_str, next_char_list)

permute_and_evaluate("", char_set)

print "Best string is ", best_str
print "Value is ", best_val