Guest User

Untitled

a guest
Jun 21st, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.34 KB | None | 0 0
  1. import itertools
  2. import sys
  3. from collections import *
  4.  
  5. d = {}
  6. pre = {'*': 3, '+': 2, '-': 2, '>': 1, '(': 0, ')': 0}
  7.  
  8. # Token
  9. s = input()
  10. for t in '+-*>()':
  11.     s = s.replace(t, ' ' + t + ' ')
  12. print ("Orig: ", s, file=sys.stderr)
  13. s = s.split()
  14. for i in range(len(s)):
  15.     try:
  16.         s[i] = int(s[i])
  17.     except:
  18.         # dn or operands
  19.         pass
  20. print ("Token:", s, file=sys.stderr)
  21.  
  22. stack = [] # operands
  23. output = []
  24. for token in s:
  25.     if (type(token) == int) or token[0] == 'd':
  26.         output.append(token)
  27.     elif token != '(' and token != ')':
  28.         # operator
  29.         while (len(stack) > 0)  and ((pre[stack[-1]] > pre[token]) or (pre[stack[-1]] == pre[token] and token != '<')) and stack[-1] != '(':
  30.             output.append(stack[-1])
  31.             del stack[-1]
  32.         stack.append(token)
  33.     elif token == '(':
  34.         stack.append(token)
  35.     else:
  36.         # Assuming parentheses are matched i.e. no open/closed
  37.         while stack[-1] != '(':
  38.             output.append(stack[-1])
  39.             del stack[-1]
  40.         del stack[-1] # Pop (
  41. output += stack[::-1] # Pop is tail
  42. print ("RPN:  ", output, file=sys.stderr)
  43.  
  44. def ev(array):
  45.     stack = []
  46.     for token in array:
  47.         if type(token) == int:
  48.             stack.append(token)
  49.         else:
  50.             b = stack[-1]
  51.             del stack[-1]
  52.             a = stack[-1]
  53.             del stack[-1]
  54.             res = None
  55.             if token == '+': res = a + b
  56.             if token == '-': res = a - b
  57.             if token == '*': res = a * b
  58.             if token == '>': res = int(a > b)
  59.             stack.append(res)
  60.     return stack[-1] # Assuming expression is valid
  61.  
  62. def possible(output):
  63.     first = 0
  64.     while first < len(output) and str(output[first])[0] != 'd':
  65.         first += 1
  66.     if first == len(output):
  67.         # All are numbers/operands
  68.         return [ev(output)]
  69.     limit = int(output[first][1:])
  70.     answer = []
  71.     for re in range(1, limit + 1):
  72.         tmp = output.copy() # shallow copies
  73.         tmp[first] = re
  74.         answer += possible(tmp)
  75.     return answer
  76.  
  77. print ("Possible:", possible(output), file=sys.stderr)
  78. c = Counter(map(str, possible(output)))
  79. print ("Statistics:", c, file=sys.stderr)
  80. for key in sorted(list(c.keys()), key=int):
  81.     print ("%s %.2f" % (key, round(c[key] / sum(c.values()) * 100, 2)))
Add Comment
Please, Sign In to add comment