数学表达式的解析给出了错误的树

Question

因此代码相当复杂，所以我尝试编写一些涵盖最重要问题的简洁伪代码。我正在尝试解析数学表达式。例如：1-5*(-2)+3 = 14

我使用的语法是：

expression = term   OR term+expression OR term-expression
term       = factor OR factor*term     OR factor/term
factor     = number OR -factor         OR (expression)

我写了一段代码来检查表达式是否遵循此语法，它适用于检查表达式但不适用于计算它。

伪代码是这样的：

double readExpression()
    number = readTerm()
    if token == +
        number2 = readExpression()
        return number + number2
    else if token == -
        number2 = readExpression()
        return number - number2
    else
        return number
...
(The code for readTerm() is identical to readExpression() in structure)
...
double readFactor()
    if token == number
        return number
    else if token == -
        number = readFactor()
        return (-1)*number
    else if token == (
        number = readExpression()
        return number
    else raise exception

如果我用这段代码进行上述计算，它会给我一棵看起来像这样的树：

所以无论如何，正如你们数学家现在已经弄清楚的那样，表达式应该给出 14 而不是树所建议的 8。我注意到当表达式前面有减号时会出现问题，因为在这个问题中会影响整个正确的术语，而它们应该只影响中间术语。

几周来我一直在发疯似的思考并思考解决方案并查看其他代码等等。请不要向我扔一堆链接，如果它们不是真的很简单也很好，因为我一直在浏览树遍历和其他相关主题。

现阶段我可以做什么？正如我所说，我的程序可以判断它是对还是错。所以现在我只需要解析一个正确的表达式。我应该写另一个 class 来解析正确的表达式吗？它更容易吗？无论如何，我看不出该代码看起来与此有何不同。

Answer 1

是的，我会解析方程式，看起来您错过了 operations/parsing 顺序的关键部分。您需要对双重否定进行额外检查。

这里的关键因素是：在有两个相同操作符的情况下，最左边的操作总是先执行。

首先让我们缩小问题范围。

这个1-5*(-2)+3等于1--10+3。

现在为了我们的目的，让我们为第一个运算符分配一个正数，因为它有助于说明一点：

1--10+3 等同于 +1--10+3

现在，如果我们通过正确的解析器将运行 +1--10+3 定位到 --，我们将知道此 -- 等于 +，但仅在以下情况下使用:

+X--Y = X+Y

所以现在我们的解析器已经将 1--10+3 的原始表达式转换为 1+10+3 并且我们知道它等于 14.

总而言之：是的，您需要一个解析器，但要特别注意 +X--Y 和 X+Y 的工作方式。

也看看这个答案：

数学表达式的解析给出了错误的树

Parsing of math expression gives wrong tree

java

syntax

tree

recursion