Могу ли я написать функцию, которая выполняет символические вычисления в Python 2.7?

Question

В настоящее время я перехожу с Java на Python и взял на себя задачу создания калькулятора, который может выполнять символические операции над математическими выражениями с инфиксной нотацией ( без использования пользовательских модулей, таких как Sympy ).,В настоящее время он построен для приема строк, разделенных пробелами, и может выполнять только операторы (,), +, -, * и /.К сожалению, я не могу понять базовый алгоритм для упрощения символьных выражений.

Например, учитывая строку '2 * ((9/6) + 6 * x)', моя программа должна выполнитьследующие шаги:

1. 2 * (1,5 + 6 * x)
2. 3 + 12 * x

Но я не могу заставить программуигнорировать x при распределении 2. Кроме того, как я могу обработать 'x * 6 / x', чтобы он возвращал '6' после упрощения?

РЕДАКТИРОВАТЬ: Чтобы уточнить, с помощью "символическое «Я имел в виду, что во время выполнения оставшихся вычислений в выводе будут присутствовать буквы типа« А »и« f ».

РЕДАКТИРОВАТЬ 2: Я (в основном) закончил код.Я публикую его здесь, если кто-нибудь в будущем наткнется на этот пост, или если кому-то из вас будет любопытно.

    def reduceExpr(useArray):

        # Use Python's native eval() to compute if no letters are detected.
        if (not hasLetters(useArray)):
            return [calculate(useArray)] # Different from eval() because it returns string version of result

        # Base case. Returns useArray if the list size is 1 (i.e., it contains one string). 
        if (len(useArray) == 1):
            return useArray

        # Base case. Returns the space-joined elements of useArray as a list with one string.
        if (len(useArray) == 3):
            return [' '.join(useArray)]

        # Checks to see if parentheses are present in the expression & sets.
        # Counts number of parentheses & keeps track of first ( found. 
        parentheses = 0
        leftIdx = -1

        # This try/except block is essentially an if/else block. Since useArray.index('(') triggers a KeyError
        # if it can't find '(' in useArray, the next line is not carried out, and parentheses is not incremented.
        try:
            leftIdx = useArray.index('(')
            parentheses += 1
        except Exception:
            pass

        # If a KeyError was returned, leftIdx = -1 and rightIdx = parentheses = 0.
        rightIdx = leftIdx + 1

        while (parentheses > 0):
            if (useArray[rightIdx] == '('):
                parentheses += 1
            elif (useArray[rightIdx] == ')'):
                parentheses -= 1
            rightIdx += 1

        # Provided parentheses pair isn't empty, runs contents through again; else, removes the parentheses
        if (leftIdx > -1 and rightIdx - leftIdx > 2):
            return reduceExpr(useArray[:leftIdx] + [' '.join(['(',reduceExpr(useArray[leftIdx+1:rightIdx-1])[0],')'])] + useArray[rightIdx:])
        elif (leftIdx > -1):
            return reduceExpr(useArray[:leftIdx] + useArray[rightIdx:])

        # If operator is + or -, hold the first two elements and process the rest of the list first
        if isAddSub(useArray[1]):
            return reduceExpr(useArray[:2] + reduceExpr(useArray[2:]))
        # Else, if operator is * or /, process the first 3 elements first, then the rest of the list
        elif isMultDiv(useArray[1]):
            return reduceExpr(reduceExpr(useArray[:3]) + useArray[3:])
        # Just placed this so the compiler wouldn't complain that the function had no return (since this was called by yet another function).
        return None

Answer 1

Вам нужно гораздо больше обработки, прежде чем приступить к операциям с символами.Форма, которую вы хотите получить, представляет собой дерево операций со значениями в конечных узлах.Сначала вам нужно выполнить лексер для строки, чтобы получить элементы - хотя, если у вас всегда есть элементы, разделенные пробелом, может быть достаточно просто разбить строку.Затем вам нужно проанализировать этот массив токенов, используя нужную вам грамматику.

Если вам нужна теоретическая информация о грамматиках и разборе текста, начните здесь: http://en.wikipedia.org/wiki/Parsing Если вам нужно что-то более практичное, перейдите кhttps://github.com/pyparsing/pyparsing (вам не нужно использовать сам модуль pyparsing, но их документация содержит много интересной информации) или http://www.nltk.org/book

С 2 * ( ( 9 / 6 ) + 6 * x ), вам нужно добраться доДерево выглядит так:

      *
2           +
         /     *
        9 6   6 x

Затем вы можете посетить каждый узел и решить, хотите ли вы его упростить.Константные операции будет проще всего исключить - просто вычислите результат и замените узел "/" на 1,5, потому что все дочерние элементы являются константами.

Существует много стратегий для продолжения, но, по сути, вам нужно найти способпройти через дерево и модифицировать его, пока ничего не изменится.

Если вы хотите напечатать результат, просто прогуляйтесь по дереву снова и создайте выражение, которое его описывает.

Answer 2

Если вы анализируете выражения в Python, вы можете рассмотреть синтаксис Python для выражений и проанализировать их, используя ast модуль (AST = дерево абстрактного синтаксиса).

Преимущества использования синтаксиса Python: вам не нужно создавать отдельный язык для этой цели, синтаксический анализатор встроен, как и оценщик. Недостатки: в дереве синтаксического анализа довольно много дополнительных сложностей, которые вам не нужны (вы можете избежать некоторых из них, используя встроенные классы NodeVisitor и NodeTransformer для своей работы).

>>> import ast
>>> a = ast.parse('x**2 + x', mode='eval')
>>> ast.dump(a)
"Expression(body=BinOp(left=BinOp(left=Name(id='x', ctx=Load()), op=Pow(),
right=Num(n=2)), op=Add(), right=Name(id='x', ctx=Load())))"

Вот пример класса, который обходит дерево разбора Python и выполняет рекурсивное свертывание констант (для бинарных операций), чтобы показать вам, что вы можете сделать довольно легко.

from ast import *

class FoldConstants(NodeTransformer):
    def visit_BinOp(self, node):
        self.generic_visit(node)
        if isinstance(node.left, Num) and isinstance(node.right, Num):
            expr = copy_location(Expression(node), node)
            value = eval(compile(expr, '<string>', 'eval'))
            return copy_location(Num(value), node)
        else:
            return node

>>> ast.dump(FoldConstants().visit(ast.parse('3**2 - 5 + x', mode='eval')))
"Expression(body=BinOp(left=Num(n=4), op=Add(), right=Name(id='x', ctx=Load())))"