Non-commutative sympify (or simplify)

Question

I would like to be able to simplify mathematical expressions from a string in Python. There are several "commutative" ways of doing it. Is there a non-commutative function for that?

I know that sympify from sympy can do some non-commutative jobs, here you have an example:

from sympy import *
x=Symbol('x',commutative=False)
y=Symbol('y',commutative=False)

print sympify(3*x*y - y*x - 2*x*y)

it will print xy -yx, however if we apply sympify to the string, that is,

print sympify('3*x*y - y*x - 2*x*y')

The result is 0.

Is there a way of simplifying the above string to preserve non-commutativity of x and y?

I found that someone has already asked about it here http://osdir.com/ml/python-sympy/2012-02/msg00250.html and someone has answered http://osdir.com/ml/python-sympy/2012-02/msg00255.html, however the solution seems not to work in general.

I preferred to ask first, if there is no immediate solution I guess that I will have to code it myself.

Answer 1

You still need to tell Sympy that there are constraints on the symbols x and y. To do this, still create Symbol instances for them, and then just pass those parameters in as locals to sympify:

In [120]: x = sympy.Symbol('x', commutative=False)

In [121]: y = sympy.Symbol('y', commutative=False)

In [122]: sympy.sympify('3*x*y - y*x - 2*x*y', locals={'x':x, 'y':y})
Out[122]: x*y - y*x

To do it programmatically, SymPy provides some nice parsing tools for extracting symbols from a string expression. The key idea is that you have to suppress evaluation since normal evaluation will make commutativity assumptions that ruin your ability to extract what you need:

In [155]: s = sympy.parsing.sympy_parser.parse_expr('3*x*y - y*x - 2*x*y', evaluate=False)

In [156]: s.atoms(sympy.Symbol)
Out[156]: {x, y}

It does not appear that there is a direct way to mutate the assumption state of an already-created Symbol, which is unfortunate. But you can iterate through these symbols, and make a new collection of symbols with the same names and the non-commutative assumption, and use that for locals in sympify.

def non_commutative_sympify(expr_string):
    parsed_expr = sympy.parsing.sympy_parser.parse_expr(
        expr_string, 
        evaluate=False
    )

    new_locals = {sym.name:sympy.Symbol(sym.name, commutative=False)
                  for sym in parsed_expr.atoms(sympy.Symbol)}

    return sympy.sympify(expr_string, locals=new_locals)

Which gives, e.g.:

In [184]: non_commutative_sympify('3*x*y - y*x - 2*x*y')
Out[184]: x*y - y*x

In [185]: non_commutative_sympify('x*y*z - y*z*x - 2*x*y*z + z*y*x')
Out[185]: -x*y*z - y*z*x + z*y*x

Answer 2

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')