8

私は現在 Java から Python に移行しており、( Sympy のようなカスタム モジュールを使用せずに) 中置表記の数式で記号演算を実行できる電卓を作成しようとするタスクを引き受けました。現在、スペースで区切られた文字列を受け入れるように構築されており、(、)、+、-、*、および / 演算子のみを実行できます。残念ながら、シンボリック式を単純化するための基本的なアルゴリズムを理解できません。

たとえば、文字列 '2 * ( ( 9 / 6 ) + 6 * x )' が与えられた場合、プログラムは次の手順を実行する必要があります。

  1. 2 * (1.5 + 6 * x)
  2. 3 + 12 * ×

しかし、2を配布するときにプログラムにxを無視させることはできません。さらに、「x * 6 / x」を処理して、単純化後に「6」を返すにはどうすればよいですか?

編集：明確にするために、「シンボリック」とは、残りの計算を実行しながら、出力に「A」や「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
4

2 に答える 2

4

シンボルの操作に入る前に、さらに多くの処理が必要です。取得するフォームは、リーフ ノードに値を持つ操作のツリーです。まず、文字列に対してレクサーを実行して要素を取得する必要がありますが、スペースで区切られた要素が常にある場合は、文字列を分割するだけで十分な場合があります。次に、必要な文法を使用してそのトークンの配列を解析する必要があります。

文法とテキストの解析に関する理論的な情報が必要な場合は、ここから始めてください: http://en.wikipedia.org/wiki/Parsing pyparsing モジュール自体を使用する必要はありませんが、それらのドキュメントには多くの興味深い情報があります) またはhttp://www.nltk.org/book

から2 * ( ( 9 / 6 ) + 6 * x )、次のようなツリーに到達する必要があります。

      *
2           +
         /     *
        9 6   6 x

次に、各ノードにアクセスして、単純化するかどうかを決定できます。定数演算は最も簡単に削除できます。すべての子は定数であるため、結果を計算して「/」ノードを 1.5 に交換するだけです。

続行するには多くの戦略がありますが、基本的には、ツリーを調べて、変更するものがなくなるまで変更する方法を見つける必要があります。

結果を印刷したい場合は、ツリーをもう一度たどって、それを記述する式を生成します。

于 2011-07-14T23:35:50.750 に答える
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())))"
于 2011-07-15T00:30:12.927 に答える