Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import itertools
- import sys
- from collections import *
- d = {}
- pre = {'*': 3, '+': 2, '-': 2, '>': 1, '(': 0, ')': 0}
- # Token
- s = input()
- for t in '+-*>()':
- s = s.replace(t, ' ' + t + ' ')
- print ("Orig: ", s, file=sys.stderr)
- s = s.split()
- for i in range(len(s)):
- try:
- s[i] = int(s[i])
- except:
- # dn or operands
- pass
- print ("Token:", s, file=sys.stderr)
- stack = [] # operands
- output = []
- for token in s:
- if (type(token) == int) or token[0] == 'd':
- output.append(token)
- elif token != '(' and token != ')':
- # operator
- while (len(stack) > 0) and ((pre[stack[-1]] > pre[token]) or (pre[stack[-1]] == pre[token] and token != '<')) and stack[-1] != '(':
- output.append(stack[-1])
- del stack[-1]
- stack.append(token)
- elif token == '(':
- stack.append(token)
- else:
- # Assuming parentheses are matched i.e. no open/closed
- while stack[-1] != '(':
- output.append(stack[-1])
- del stack[-1]
- del stack[-1] # Pop (
- output += stack[::-1] # Pop is tail
- print ("RPN: ", output, file=sys.stderr)
- def ev(array):
- stack = []
- for token in array:
- if type(token) == int:
- stack.append(token)
- else:
- b = stack[-1]
- del stack[-1]
- a = stack[-1]
- del stack[-1]
- res = None
- if token == '+': res = a + b
- if token == '-': res = a - b
- if token == '*': res = a * b
- if token == '>': res = int(a > b)
- stack.append(res)
- return stack[-1] # Assuming expression is valid
- def possible(output):
- first = 0
- while first < len(output) and str(output[first])[0] != 'd':
- first += 1
- if first == len(output):
- # All are numbers/operands
- return [ev(output)]
- limit = int(output[first][1:])
- answer = []
- for re in range(1, limit + 1):
- tmp = output.copy() # shallow copies
- tmp[first] = re
- answer += possible(tmp)
- return answer
- print ("Possible:", possible(output), file=sys.stderr)
- c = Counter(map(str, possible(output)))
- print ("Statistics:", c, file=sys.stderr)
- for key in sorted(list(c.keys()), key=int):
- print ("%s %.2f" % (key, round(c[key] / sum(c.values()) * 100, 2)))
Add Comment
Please, Sign In to add comment