import sys def evaluate(expression, bindings): lo, hi = -2147483648, 2147483647 letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_' def name_ok(s): return isinstance(s, str) and 1 <= len(s) <= 32 and s[0] in letters and all(c in letters + '0123456789' for c in s) if not isinstance(expression, str) or not 1 <= len(expression) <= 4096 or not isinstance(bindings, dict) or len(bindings) > 64: raise ValueError() if any(not name_ok(k) or isinstance(v, bool) or not isinstance(v, int) or not lo <= v <= hi for k, v in bindings.items()): raise ValueError() parts = [] i = 0 while i < len(expression): c = expression[i] if c in ' \r\n\t': i += 1 continue start = i if c in letters: i += 1 while i < len(expression) and expression[i] in letters + '0123456789': i += 1 token = expression[start:i] if not name_ok(token): raise ValueError() elif c in '0123456789': i += 1 while i < len(expression) and expression[i] in '0123456789': i += 1 token = expression[start:i] elif expression[i:i+2] in ('&&', '||', '<=', '>=', '==', '!='): token = expression[i:i+2] i += 2 elif c in '()+-*/%!<>?:': token = c; i += 1 else: raise ValueError() parts.append(token) ranks = {op: rank for rank, ops in enumerate([['?:'], ['||'], ['&&'], ['==', '!='], ['<', '<=', '>', '>='], ['+', '-'], ['*', '/', '%'], ['u+', 'u-', 'u!']], 0) for op in ops} nodes, operators = [], [] need = True def reduce_one(): op = operators.pop() arity = 3 if op == '?:' else 1 if op.startswith('u') else 2 if len(nodes) < arity: raise ValueError() args = nodes[-arity:] del nodes[-arity:] nodes.append((op, *args)) for word in parts: if word == '(': if not need: raise ValueError() operators.append(word) elif word == ')': if need: raise ValueError() while operators and operators[-1] != '(': if operators[-1] == '?': raise ValueError() reduce_one() if not operators: raise ValueError() operators.pop() need = False elif need: if word in ('+', '-', '!'): operators.append('u' + word) elif word[0] in '0123456789': nodes.append(('lit', int(word))); need = False elif name_ok(word): nodes.append(('var', word)); need = False else: raise ValueError() elif word == ':': while operators and operators[-1] not in ('?', '('): reduce_one() if not operators or operators[-1] != '?': raise ValueError() operators[-1] = '?:' need = True elif word == '?': while operators and operators[-1] not in ('(', '?', '?:'): reduce_one() operators.append('?') need = True elif word in ranks: while operators and operators[-1] not in ('(', '?') and ranks[operators[-1]] >= ranks[word]: reduce_one() operators.append(word) need = True else: raise ValueError() if need: raise ValueError() while operators: if operators[-1] in ('(', '?'): raise ValueError() reduce_one() if len(nodes) != 1: raise ValueError() stack = [(nodes[0], False)] values = [] while stack: node, phase = stack.pop() op = node[0] if op == 'lit': value = node[1] elif op == 'var': if node[1] not in bindings: raise NameError() value = bindings[node[1]] elif phase is False: stack.extend([(node, 1), (node[1], False)]) continue elif phase == 1: a = values.pop() if op in ('u+', 'u-', 'u!'): value = +a if op == 'u+' else -a if op == 'u-' else int(a == 0) elif op == '?:': stack.append((node[2 if a else 3], False)); continue elif (op == '&&' and a == 0) or (op == '||' and a != 0): value = int(op == '||') else: stack.extend([((op, a), 2), (node[2], False)]) continue else: a, b = node[1], values.pop() if op in ('&&', '||'): value = int(b != 0) elif op in ('/', '%'): if b == 0: raise ZeroDivisionError() q, _ = divmod(abs(a), abs(b)) if (a < 0) != (b < 0): q = -q value = q if op == '/' else a - b*q elif op == '+': value = a + b elif op == '-': value = a - b elif op == '*': value = a * b else: value = int({'==': a == b, '!=': a != b, '<': a < b, '<=': a <= b, '>': a > b, '>=': a >= b}[op]) if not lo <= value <= hi: raise OverflowError() values.append(value) return values[0]