Advertisement
Guest User

Untitled

a guest
May 24th, 2018
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. """
  2. 1+2+3
  3. 6
  4.  
  5. 2+2*2
  6. 8
  7.  
  8. 4+5*5+4
  9. 81
  10.  
  11.  
  12. 4+5*5+4
  13.  
  14. """
  15.  
  16. expr_str = input()
  17. n = len(expr_str)
  18.  
  19.  
  20. def calc(a, b, op):
  21. if op == "+":
  22. return a + b
  23. elif op == "*":
  24. return a * b
  25. else:
  26. raise Exception("unknown op")
  27.  
  28.  
  29. def arifm(expr):
  30. MAX_VAL = 10000000
  31. MIN_VAL = -MAX_VAL
  32. m = (len(expr) + 1) // 2
  33. max_arr = []
  34. min_arr = []
  35.  
  36. for i in range(0, m):
  37. max_arr.append([0] * m)
  38. min_arr.append([0] * m)
  39. max_arr[i][i] = int(expr[2 * i])
  40. min_arr[i][i] = int(expr[2 * i])
  41.  
  42. for s in range(0, m - 1):
  43. for i in range(0, m - s - 1):
  44. j = i + s + 1
  45. min_val = MAX_VAL
  46. max_val = MIN_VAL
  47.  
  48. for k in range(i, j):
  49. a = calc(min_arr[i][k], min_arr[k + 1][j], expr[2 * k + 1])
  50. b = calc(min_arr[i][k], max_arr[k + 1][j], expr[2 * k + 1])
  51. c = calc(max_arr[i][k], min_arr[k + 1][j], expr[2 * k + 1])
  52. d = calc(max_arr[i][k], max_arr[k + 1][j], expr[2 * k + 1])
  53. min_val = min(min_val, min(a, min(b, min(c, d))))
  54. max_val = max(max_val, max(a, max(b, max(c, d))))
  55.  
  56. min_arr[i][j] = min_val
  57. max_arr[i][j] = max_val
  58.  
  59. return max_arr[0][m - 1]
  60.  
  61.  
  62. print(arifm(expr_str))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement