diff -r f899af683bbe -r aeb0d0788869 calc.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/calc.py	Sun Apr 19 19:45:42 2015 +0300
@@ -0,0 +1,474 @@
+import re
+import cmath
+import math
+import random
+import time
+import operator
+from copy import deepcopy
+
+epsilon = 1e-10
+
+# http://stackoverflow.com/a/2182437
+class Enum (set):
+	def __init__ (self, *args):
+		super (Enum, self).__init__ (args)
+
+	def __getattr__ (self, name):
+		if name in self:
+			return name
+		raise AttributeError
+
+	def __setattr__ (self, name, value):
+		raise AttributeError
+
+class Operator (object):
+	def __init__ (self, name, symbol, operands, priority, function):
+		self.name = name
+		self.symbol = symbol
+		self.operands = operands
+		self.priority = priority
+		self.function = function
+
+	def __str__ (self):
+		return '''<operator %s>''' % self.name
+
+	def __repr__ (self):
+		return self.__str__()
+
+class FunctionCall (object):
+	def __init__ (self, funcname, args):
+		assert (type(args) is list)
+		self.funcname = funcname
+		self.args = args
+
+	def __str__ (self):
+		return '''<function %s (%s)>''' % (self.funcname, self.args)
+
+	def __repr__ (self):
+		return self.__str__()
+
+def do_realf (func, *args):
+	for x in args:
+		if x.imag:
+			raise ValueError ('%s called with a complex number' % func.__name__)
+
+	return func (*[x.real for x in args])
+
+def do_intf (func, *args):
+	for x in args:
+		if x.imag:
+			raise ValueError ('%s called with a complex number' % func.__name__)
+
+		if x.real - math.floor (x.real):
+			raise ValueError ('%s called with a floating point number' % func.__name__)
+
+	return func (*[int (x.real) for x in args])
+
+def realf (func):
+	return lambda *args: do_realf (func, *args)
+
+def intf (func):
+	return lambda *args: do_intf (func, *args)
+
+Operators = []
+OperatorData = {
+	'lneg':		{ 'symbol': '!',  'operands': 1, 'priority': 5, 'function': lambda x: not x },
+	'compl':	{ 'symbol': '~',  'operands': 1, 'priority': 5, 'function': intf (operator.inv) },
+	'neg':		{ 'symbol': '-',  'operands': 1, 'priority': 5, 'function': lambda x: -x },
+	'pow':		{ 'symbol': '**', 'operands': 2, 'priority': 10, 'function': lambda x, y: x ** y },
+	'mul':		{ 'symbol': '*',  'operands': 2, 'priority': 50, 'function': lambda x, y: x * y },
+	'div':		{ 'symbol': '/',  'operands': 2, 'priority': 50, 'function': lambda x, y: x / y },
+	'mod':		{ 'symbol': '%',  'operands': 2, 'priority': 50, 'function': lambda x, y: math.fmod (x, y) },
+	'add':		{ 'symbol': '+',  'operands': 2, 'priority': 100, 'function': lambda x, y: x + y },
+	'sub':		{ 'symbol': '-',  'operands': 2, 'priority': 100, 'function': lambda x, y: x - y },
+	'eq':		{ 'symbol': '==', 'operands': 2, 'priority': 500, 'function': lambda x, y: x == y },
+	'neq':		{ 'symbol': '!=', 'operands': 2, 'priority': 500, 'function': lambda x, y: x != y },
+	'lt':		{ 'symbol': '<',  'operands': 2, 'priority': 500, 'function': lambda x, y: x < y },
+	'lteq':		{ 'symbol': '<=', 'operands': 2, 'priority': 500, 'function': lambda x, y: x <= y },
+	'gt':		{ 'symbol': '>',  'operands': 2, 'priority': 500, 'function': lambda x, y: x > y },
+	'gteq':		{ 'symbol': '>=', 'operands': 2, 'priority': 500, 'function': lambda x, y: x >= y },
+	'btand':	{ 'symbol': '&',  'operands': 2, 'priority': 600, 'function': intf (operator.and_) },
+	'btxor':	{ 'symbol': '^',  'operands': 2, 'priority': 601, 'function': intf (operator.xor) },
+	'btor':		{ 'symbol': '|',  'operands': 2, 'priority': 602, 'function': intf (operator.or_) },
+	'and':		{ 'symbol': '&&', 'operands': 2, 'priority': 603, 'function': lambda x, y: x and y },
+	'or':		{ 'symbol': '||', 'operands': 2, 'priority': 604, 'function': lambda x, y: x or y },
+}
+
+for name, data in OperatorData.iteritems():
+	Operators.append (Operator (name=name, symbol=data['symbol'], operands=data['operands'],
+		priority=data['priority'], function=data['function']))
+
+OperatorSymbols={}
+for op in Operators:
+	if op.symbol in OperatorSymbols:
+		OperatorSymbols[op.symbol].append (op)
+	else:
+		OperatorSymbols[op.symbol] = [op]
+
+Constants = {
+	'pi': cmath.pi,
+	'e': cmath.e,
+	'phi': 1.6180339887498948482,
+	'epsilon': epsilon,
+}
+
+random.seed (time.time())
+
+Functions = {
+	'round':	{ 'function': realf (round) },
+	'floor':	{ 'function': realf (math.floor) },
+	'ceil':		{ 'function': realf (math.ceil) },
+	'fact':		{ 'function': intf (math.factorial) },
+	'abs':		{ 'function': realf (math.fabs) },
+	'degrees':	{ 'function': realf (math.degrees) },
+	'radians':	{ 'function': realf (math.radians) },
+	'erf':		{ 'function': realf (math.erf) },
+	'erfc':		{ 'function': realf (math.erfc) },
+	'gamma':	{ 'function': realf (math.gamma) },
+	'lgamma':	{ 'function': realf (math.lgamma) },
+	'sqrt':		{ 'function': cmath.sqrt },
+	'ln':		{ 'function': cmath.log },
+	'log':		{ 'function': cmath.log10 },
+	'sin':		{ 'function': cmath.sin },
+	'sinh':		{ 'function': cmath.sinh },
+	'asin':		{ 'function': cmath.asin },
+	'asinh':	{ 'function': cmath.asinh },
+	'cos':		{ 'function': cmath.cos },
+	'cosh':		{ 'function': cmath.cosh },
+	'acos':		{ 'function': cmath.acos },
+	'acosh':	{ 'function': cmath.acosh },
+	'tan':		{ 'function': cmath.tan },
+	'tanh':		{ 'function': cmath.tanh },
+	'atan':		{ 'function': cmath.atan },
+	'atanh':	{ 'function': cmath.atanh },
+	'exp':		{ 'function': cmath.exp },
+	'phase':	{ 'function': cmath.phase },
+	'lg':		{ 'function': lambda x: cmath.log (x, 2) },
+	're':		{ 'function': lambda x: x.real },
+	'im':		{ 'function': lambda x: x.imag },
+	'conjugate':{ 'function': lambda x: x.conjugate() },
+	'rand':		{ 'function': random.random },
+}
+
+Tokens = ['(', ')']
+
+# Symbol table
+SymbolType = Enum ('CONSTANT', 'FUNCTION', 'OPERATOR', 'TOKEN')
+SymbolTypes = {}
+Symbols = []
+
+for name, value in Constants.iteritems():
+	Symbols.append (name)
+	SymbolTypes[name] = SymbolType.CONSTANT
+
+for name, data in Functions.iteritems():
+	Symbols.append (name)
+	SymbolTypes[name] = SymbolType.FUNCTION
+
+for op in Operators:
+	if op.symbol not in Symbols:
+		Symbols.append (op.symbol)
+	SymbolTypes[op.symbol] = SymbolType.OPERATOR
+
+for name in Tokens:
+	SymbolTypes[name] = SymbolType.TOKEN
+
+Symbols += Tokens
+Symbols = sorted (Symbols, key=lambda x: len (x), reverse=True)
+
+def parse_number (expr):
+	"""Tries to parse a number from the expression. Returns (value, length) on success."""
+	i = 0
+	value = None
+
+	if expr[0] == 'i':
+		# Special case, we just have 'i' -- need special handling here because otherwise this would
+		# call float('') in the complex number routine, which throws an error.
+		# TODO: maybe 'i' can be a symbol instead?
+		return (1j, 1)
+
+	# Try parse increasingly long substrings until we are unable to create a float or complex number
+	# from it.
+	try:
+		while i < len (expr):
+			if expr[i] == 'i':
+				value = complex (0.0, float (expr[:i]))
+			else:
+				value = complex (float (expr [:i + 1]), 0.0)
+			i += 1
+
+		return (value, i)
+	except ValueError:
+		if i != 0:
+			# Got a number (the error happened when we tried to parse past the number)
+			return (value, i)
+		else:
+			# The error happened on the first character. So this is not a number.
+			return None
+
+def parse_symbol (expr):
+	for sym in Symbols:
+		if expr[:len (sym)] == sym:
+			return sym
+
+	return None
+
+def tokenize (expr):
+	expr = re.sub ('\s+', '', expr.strip())
+	i=0
+	tokens = []
+
+	while i < len(expr):
+		sym = parse_symbol (expr[i:])
+
+		if sym:
+			symtype = SymbolTypes[sym]
+			if symtype == SymbolType.CONSTANT:
+				tokens.append (Constants[sym])
+			else:
+				tokens.append (sym)
+
+			i += len(sym)
+			continue
+
+		result = parse_number (expr[i:])
+		if result:
+			num, length = result
+			tokens.append (num)
+			i += length
+			continue
+
+		raise ValueError ("""bad expression, couldn't parse: %s""" % expr[i:])
+
+	return tokens
+
+def rindex (li, value):
+	return (len(li) - 1) - li[::-1].index(value)
+
+def process_parens (expr):
+	"""Processes parentheses of expr into sublists in-place.
+	[1.0, '*', '(', 3.5, '+', 1j, ')']
+	-> [1.0, '*', [3.5, '+', 1j]]"""
+	if '(' not in expr and ')' not in expr:
+		return
+
+	try:
+		parenStart = rindex (expr, '(')
+		parenEnd = expr.index (')', parenStart)
+	except ValueError:
+		raise ValueError ("""mismatched parentheses in expression: %s""" % expr)
+
+	subexpr = expr[parenStart + 1:parenEnd]
+	del expr[parenStart + 1:parenEnd + 1]
+	expr[parenStart] = subexpr
+	process_parens (expr)
+
+def process_functions (expr):
+	"""Processes functions in-place"""
+	i = 0
+	while i < len (expr):
+		if type (expr[i]) is list:
+			process_functions (expr[i])
+
+		if (type(expr[i]) is not str) or (expr[i] not in Functions):
+			i += 1
+			continue
+
+		# Ensure that arguments follow
+		if (i + 1 >= len (expr)) or (type (expr[i + 1]) is not list):
+			raise ValueError ("""function %s used without arguments""" % expr[i])
+
+		args = expr[i + 1]
+		del expr[i + 1]
+		expr[i] = FunctionCall (expr[i], args)
+		i += 1
+
+def is_operand (x):
+	# Operands can be either lists (which also mean parens, thus can be single-expressions)
+	# or complex numbers
+	return type(x) in [complex, list]
+
+def find_fitting_operator (sym, numOperands):
+	# Pass 1: exact numOperands match
+	for op in Operators:
+		if op.symbol != sym:
+			continue
+
+		if op.operands == numOperands:
+			# print '%s, %d -> %s (1st pass)' % (sym, numOperands, op)
+			return op
+
+	# Pass 2: by symbol
+	for op in Operators:
+		if op.symbol == sym:
+			# print '%s, %d -> %s (2nd pass)' % (sym, numOperands, op)
+			return op
+
+	raise ValueError ('''unknown operator %s!''' % sym)
+
+def process_operators (expr):
+	"""Processes operators"""
+	i = 0
+
+	# Find all operators in this expression
+	while i < len (expr):
+		if type (expr[i]) is list:
+			process_functions (expr[i])
+			process_operators (expr[i])
+
+		if type (expr[i]) is FunctionCall:
+			process_functions (expr[i].args)
+			process_operators (expr[i].args)
+
+		if (type(expr[i]) is not str) or (expr[i] not in OperatorSymbols):
+			i += 1
+			continue
+
+		args = []
+		argIndices = []
+		if i > 0 and is_operand (expr[i - 1]):
+			args.append (expr[i - 1])
+			argIndices.append (i - 1)
+
+		if i - 1 < len(expr) and is_operand (expr[i + 1]):
+			args.append (expr[i + 1])
+			argIndices.append (i + 1)
+
+		# Resolve operators with the same symbol based on operand count
+		numOperands = 0
+		for arg in args:
+			if is_operand (arg):
+				numOperands += 1
+
+		expr[i] = find_fitting_operator (expr[i], numOperands)
+		i += 1
+
+def find_priority_operator (expr):
+	"""Finds the operator with most priority in the expression"""
+	bestOp = None
+	bestOpIndex = -1
+
+	for i in range (0, len (expr)):
+		sym = expr[i]
+
+		if type (sym) is not Operator:
+			continue
+
+		if not bestOp or sym.priority < bestOp.priority:
+			bestOp = sym
+			bestOpIndex = i
+
+	return (bestOp, bestOpIndex)
+
+def realPrint (x):
+	print x
+
+tabs=''
+def evaluate (expr, verbose=False):
+	global tabs
+	printFunc = realPrint if verbose else lambda x:None
+	printFunc (tabs + 'Preprocess: %s' % expr)
+
+	# If there are sub-expressions in here, those need to be evaluated first
+	i = 0
+	while i < len (expr):
+		sym = expr[i]
+
+		if type (sym) is list and sym:
+			printFunc (tabs + 'Evaluating sub-expression: %s' % (sym))
+			tabs += '\t'
+			expr[i] = evaluate (list (sym), verbose)
+			tabs = tabs[:-1]
+			printFunc (tabs + '-> %s' % expr[i])
+
+		# If there are function calls, evaluate those
+		if type (sym) is FunctionCall:
+			tabs += '\t'
+			if sym.args:
+				sym.args = [evaluate (sym.args, verbose)]
+			tabs = tabs[:-1]
+
+			printFunc (tabs + 'Evaluating function call: %s' % (sym))
+			expr[i] = Functions[sym.funcname]['function'] (*sym.args)
+			printFunc (tabs + '-> %s' % expr[i])
+			
+		i += 1
+
+	printFunc (tabs + 'Evaluate: %s' % expr)
+	runaway = 0
+	while True:
+		runaway += 1
+		if runaway > 1000:
+			raise ValueError ('infinite loop detected')
+
+		op, i = find_priority_operator (expr)
+		if not op:
+			break
+
+		if op.operands == 2:
+			argIndices = [i - 1, i + 1]
+		else:
+			argIndices = [i + 1]
+
+		args = [expr[x] for x in argIndices]
+		argIndices = sorted (argIndices, reverse=True)
+		printFunc (tabs + 'Processing: (%s, %d) with args %s' % (op, i, args))
+		expr[i] = op.function (*args)
+		printFunc (tabs + '-> %s' % expr[i])
+
+		for i2 in argIndices:
+			del expr[i2]
+
+	printFunc (tabs + 'Result: %s' % expr[0])
+
+	if len(expr) != 1:
+		printFunc (tabs + 'Bad expression detected, tokens: %s' % expr)
+		raise ValueError ('malformed expression')
+
+	return expr[0]
+
+def repr_number (x):
+	"""Returns a string representation for a real number"""
+	rep = '%.10f' % x
+
+	if '.' in rep:
+		while rep[-1] == '0':
+			rep = rep[:-1]
+
+		if rep[-1] == '.':
+			rep = rep[:-1]
+
+	return rep
+
+def repr_imaginary (x):
+	rep = repr_number (x)
+
+	if rep == '1':
+		return 'i'
+
+	if rep == '-1':
+		return '-i'
+
+	return rep + 'i'
+
+def represent (x):
+	"""Returns a string representation of a float or complex number"""
+	if math.fabs (x.imag) > epsilon:
+		if math.fabs (x.real) > epsilon:
+			# Complex number
+			return '%s %s %s' % (repr_number (x.real),
+				'+' if x.imag >= 0 else '-',
+				repr_imaginary (math.fabs (x.imag)))
+		else:
+			# Pure imaginary number
+			return repr_imaginary (x.imag)
+	else:
+		# Real number
+		return repr_number (x.real)
+
+def calc (expr, verbose=False):
+	expr = tokenize (expr)
+	process_parens (expr)
+	process_functions (expr)
+	process_operators (expr)
+	return represent (evaluate (expr, verbose))