Here is my solution. For the algorithm please see either my above comments or the comments in the code. I will appreciate if someone comes with a more elegant piece of code.
"""
Created on Sat Aug 22 22:15:16 2015
@author: GnacikM
"""
from sympy import *
import re
import string
"""
names for variables in a list
"""
alpha = list(string.ascii_lowercase)
Alpha = list(string.ascii_uppercase)
"""
Creating symbols
"""
def symbol_commutativity(my_symbol, name, status):
my_symbol = Symbol(str(name), commutative=status)
return my_symbol
symbols_lower = []
for item in alpha:
symbols_lower.append(symbol_commutativity(item, item, False))
symbols_upper = []
for item in Alpha:
symbols_upper.append(symbol_commutativity(item, item, False))
"""
Transforming an infix expression to Reverse Polish Notation
http://andreinc.net/2010/10/05/converting-infix-to-rpn-shunting-yard-algorithm/
"""
#Associativity constants for operators
LEFT_ASSOC = 0
RIGHT_ASSOC = 1
#Supported operators
OPERATORS = {
'+' : (0, LEFT_ASSOC),
'-' : (0, LEFT_ASSOC),
'*' : (5, LEFT_ASSOC),
'/' : (5, LEFT_ASSOC),
'%' : (5, LEFT_ASSOC),
'^' : (10, RIGHT_ASSOC)
}
#Test if a certain token is operator
def isOperator(token):
return token in OPERATORS.keys()
#Test the associativity type of a certain token
def isAssociative(token, assoc):
if not isOperator(token):
raise ValueError('Invalid token: %s' % token)
return OPERATORS[token][1] == assoc
#Compare the precedence of two tokens
def cmpPrecedence(token1, token2):
if not isOperator(token1) or not isOperator(token2):
raise ValueError('Invalid tokens: %s %s' % (token1, token2))
return OPERATORS[token1][0] - OPERATORS[token2][0]
#Transforms an infix expression to RPN
def infixToRPN(tokens):
out = []
stack = []
#For all the input tokens [S1] read the next token [S2]
for token in tokens:
if isOperator(token):
# If token is an operator (x) [S3]
while len(stack) != 0 and isOperator(stack[-1]):
# [S4]
if (isAssociative(token, LEFT_ASSOC) and cmpPrecedence(token, stack[-1]) <= 0) or (isAssociative(token, RIGHT_ASSOC) and cmpPrecedence(token, stack[-1]) < 0):
# [S5] [S6]
out.append(stack.pop())
continue
break
# [S7]
stack.append(token)
elif token == '(':
stack.append(token) # [S8]
elif token == ')':
# [S9]
while len(stack) != 0 and stack[-1] != '(':
out.append(stack.pop()) # [S10]
stack.pop() # [S11]
else:
out.append(token) # [S12]
while len(stack) != 0:
# [S13]
out.append(stack.pop())
return out
"""
Evaluating an expression in Reverse Polish Notation, an input is a list
http://danishmujeeb.com/blog/2014/12/parsing-reverse-polish-notation-in-python
"""
def parse_rpn(expression):
stack = []
for val in expression:
if val in ['-', '+', '*', '/', '^']:
op1 = stack.pop()
if len(stack)==0:
op2 = 0
else:
op2 = stack.pop()
if val=='-':
result = op2 - op1
elif val=='+':
result = op2 + op1
elif val=='*':
result = op2 * op1
elif val=='/':
result = op2 / op1
elif val=='^':
result = op2 ** op1
stack.append(result)
else:
stack.append(val)
return stack
"""
Definition of my non-commutative sympify
"""
def nc_sympify(string):
expression_list = re.findall(r"(-\number|\b\w*[\.]?\w+\b|[\(\)\+\*\-\/^])", string)
""" Modifying expression_list to fix the issue with negative numbers """
t = len(expression_list)
i=0
while i<t:
if len(expression_list[i])>1 and expression_list[i][0]=='-' and expression_list[i-1]!='(':
new_list1 = expression_list[:i]
if i<len(expression_list):
new_list2 = expression_list[i+1:]
else:
new_list2 = []
new_entry1 = expression_list[i][0]
new_entry2 = expression_list[i][1:]
expression_list[:] = new_list1 +[new_entry1] +[new_entry2]+new_list2
t = len(expression_list)
i+=1
"""End of this modification """
for i in xrange(len(expression_list)):
if expression_list[i] in alpha:
for j in range(len(alpha)):
if expression_list[i] == alpha[j]:
expression_list[i] = symbols_lower[j]
elif expression_list[i] in Alpha:
for k in xrange(len(Alpha)):
if expression_list[i] == Alpha[k]:
expression_list[i] = symbols_upper[k]
elif expression_list[i] not in ['-', '+', '*', '/', '(', ')', '^', ' ']:
expression_list[i] = float(expression_list[i] )
if i>0 and expression_list[i].is_integer()==True and expression_list[i-1]!='/':
expression_list[i]=int(expression_list[i])
elif i==0 and expression_list[i].is_integer()==True:
expression_list[i]=int(expression_list[i])
output = infixToRPN(expression_list)
return parse_rpn(output)[0]
print nc_sympify('3*x*y - y*x - 2*x*y')
