非交换符号化（或化简）

Question

我希望能够简化 Python 中字符串的数学表达式。有几种 "commutative" 方法可以做到这一点。是否有非交换函数？

我知道 sympify 来自 sympy 可以做一些不可交换的工作，这里有一个例子：

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

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

它将打印 xy -yx，但是如果我们对字符串应用 sympify，即

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

结果为0。

有没有办法简化上述字符串以保持 x 和 y 的非交换性？

我发现这里已经有人问过了http://osdir.com/ml/python-sympy/2012-02/msg00250.html and someone has answered http://osdir.com/ml/python-sympy/2012-02/msg00255.html，但是这个解决方案似乎一般都行不通。

我宁愿先问，如果没有立竿见影的解决方案，我想我将不得不自己编写代码。

Answer 1

这是我的解决方案。对于算法，请参阅我上面的评论或代码中的评论。如果有人提供更优雅的代码，我将不胜感激。

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

Answer 2

你还需要告诉 Sympy 符号 x 和 y 有约束。为此，仍然为它们创建 Symbol 个实例，然后将这些参数作为 locals 传递给 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

为了以编程方式执行此操作，SymPy 提供了一些不错的解析工具，用于从字符串表达式中提取符号。关键思想是你必须抑制求值，因为正常求值会做出交换性假设，破坏你提取所需内容的能力：

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}

似乎没有直接的方法来改变已创建的假设状态 Symbol，这很不幸。但是您可以遍历这些符号，并创建一个具有相同名称和非交换假设的新符号集合，并将其用于 sympify.

中的 locals

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)

给出，例如：

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

非交换符号化（或化简）

Non-commutative sympify (or simplify)

python

sympy

mathematical-expressions

python-2.7

commutativity