8

我目前正在从 Java 过渡到 Python，并承担了尝试创建一个计算器的任务，该计算器可以对中缀表示的数学表达式执行符号运算（不使用像 Sympy 这样的自定义模块）。目前，它被构建为接受以空格分隔的字符串，并且只能执行 (、)、+、-、* 和 / 运算符。不幸的是，我无法弄清楚简化符号表达式的基本算法。

例如，给定字符串 '2 * ( ( 9 / 6 ) + 6 * x )'，我的程序应该执行以下步骤：

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

但是我不能让程序在分发 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如果您需要更实用的东西，请访问https://github.com/pyparsing/pyparsing（您不需要不必使用 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 回答