Python: 如何用逻辑算法计算代数表达式？

Question

我是编程新手，开始了一个小项目以变得更好。我想做一个不太基础的shell计算器，基本的方法很快就搞定了，学到了很多东西。但我的新目标是评估完整的代数表达式，例如：(2+3)^(80/(3*4)) 我认为算法会像人类一样派上用场 'step by step' - 解决整个问题的 1 位并重新开始。所以我想先检查所有有趣的代数符号：（术语是用户输入）

    open_brackets     =[i.start() for i in re.finditer('\(',str(term))]
    close_brackets    =[i.start() for i in re.finditer('\)',str(term))]
    powers            =[i.start() for i in re.finditer('\^',str(term))]
    mult              =[i.start() for i in re.finditer('\*',str(term))]
    div               =[i.start() for i in re.finditer('\/',str(term))]
    plus              =[i.start() for i in re.finditer('\+',str(term))]
    minus             =[i.start() for i in re.finditer('\-',str(term))]

现在我有了这些信息，我认为寻找最右边的左括号并找到相应的右括号可能很有用：

last_open_bracket = open_brackets[len(open_brackets)-1]
    next_closed_bracket = 0
    for i in close_brackets : 
        if last_open_bracket < i :
            next_closed_bracket = i
            break

从那以后，我只运行遇到问题，因为我不知道如何构建整个事情，而且我已经搞砸了好几次。查看这些括号内部并检查它们之间的代数符号显然很有用。权力的一个例子，因为他们首先是：

for i in powers : 
        if (last_open_bracket < i) and (next_closed_bracket > i) :

我现在可以，一旦找到“^”的位置，就逐步向左移动“^”，直到我碰到不是 int 或“.”类型的东西。因为这是在浮点数中使用的，更具体地说，我搜索下一个代数符号或括号。依此类推，直到我有 2 个数字，然后我可以使用它们的力量。然后将原输入中所有用于本次计算的符号和数字切出，并将计算结果添加到正确的位置，重新开始。

我的问题是处理括号内可能发生的所有不同情况，例如

多次操作即 (2+3+4)
识别 (-9) 或 -(9) 中的“-”不是减去某些东西的调用

还有在某些情况下如何处理不同的括号，例如，我早先提出要切掉所有使用的符号和数字，但是在不同的情况下我们需要不同的手段：

(9) --> 9
(2+3) --> 5
(-2)^2 -/-> -2^2

如您所见，我需要一点思维帮助，我不知道如何将这个算法概念化。我希望你能帮助我，祝你有个愉快的一天！

Answer 1

我见过一些解析器并自己编写了几个，但我从未见过像您正在尝试的算法。你的困难可能意味着你应该使用另一种整体算法。

我建议您一次只扫描表达式字符串中的一个字符，从左到右，然后适当地对每个字符执行操作。如果你想要简单，你可以使用 PEMDAS 和一组例程来制作递归算法。你的顶层计算一个表达式，下一个括号组，下一个求幂，下一个乘法和除法，最后一个加法和减法。您还需要一个例程来评估数字文字，一个用于否定，一个用于一元加。

还有其他方法，例如为每个运算符使用令牌，将内容放在堆栈上，以及使用给出每个运算符的操作顺序的字典。此处求幂时要小心，因为它的顺序是从右到左而不是从左到右。但是你的需求看起来很简单，递归的方法对你来说会更简单。

Answer 2

虽然您的代数语言非常有限，但这并非易事。

您当然可以按照其他答案的建议着手编写自己的解析器。或者您可以使用解析器生成器让您的解析器根据语法规则生成。

这是一种可能的解决方案草图：

您首先需要为您的代数语言定义语法。在维基百科上有 a similar language 的正式语法。

您尝试评估的语言似乎与上下文无关。

指定形式语法有多种规则。一种叫做 EBNF（扩展巴科斯诺尔形式）。

上下文无关语言的语法通常被定义为包含终结符和非终结符的产生式规则，规则的左侧只包含一个非终结符。

在您的案例中，终止符号是数字（0 到 9）、括号和运算符 +-/*^。

对于您的语言，我想一个单一的非终结符号 S 就足够了。

您的规则可能如下所示：

S        -> ( <S> + <S> );
S        -> ( <S> - <S> );
S        -> ( <S> / <S> );
... 
S        -> 0|1|2|3|4|5|6|7|8|9;

This is a nice tool 试用您的上下文无关规则：

一旦指定了语法，就可以使用解析器生成器（例如 ANTLR）生成一个解析器，如果输入字符串符合您的查询，它将把您的输入字符串转换为 parse tree，并且否则抛出异常。

维基百科为不同种类的语言提供了 list of parser generators。您应该查看上下文无关语言部分。

然后您将需要使用结构递归评估抽象语法树。

Answer 3

您可能要考虑的一件事是自下而上的解析器。您可以通过基于操作顺序的过滤来使用它，在递归解析方法中使用正则表达式。首先，您将括号内的内容传递下来进行解析。然后，你利用你的力量并将它们传递给解析。然后你把你的乘法和除法从左到右传递给解析。最后，您进行加法和减法并将它们传递给解析，同样是从左到右。在底层，（即 *、/、-、+、^）您在将表达式传回之前评估它们。可以找到关于该主题的维基百科文章 here。

Python: 如何用逻辑算法计算代数表达式？

Python: How can I evaluate algebraic expressions with a logic algorithm?

python

algorithm

math

calculator

evaluation