一个非常简单的解析器

• 下载源代码 - 3.25 Kb

引言

有一天，我15岁的时候，我去了家附近的一家商店，看到了一台科学计算器。当我使用这台计算器时，有什么东西引起了我的注意。这台计算器不像我当时习惯使用的其他简单计算器。在计算器显示屏的顶部有一个条，你可以在其中输入任何表达式（例如 5*sin(pi/2)+5），然后计算器会计算出结果。我惊叹于计算器是如何理解文本的，即解析表达式并计算结果的。现在，18岁了，我决定制作一系列实现相同功能的程序。这是我这个系列的第一款程序。

本文介绍了一个简单的程序，该程序可以解析仅包含加、减、乘、除和数字的简单表达式（例如 5+6*3.3），并计算其结果。

开始吧

我不喜欢废话太多，所以我想最好的方式是通过一个例子来阐述我的想法。考虑以下表达式

1*2*3-4*5/6.6+2

首先我们需要记住的是，乘法和除法比加法和减法有更高的优先级。我们需要找到一种方法来实现这一点。最好的方法是将表达式划分为项。这样，结果就是计算以下各项的值：

1*2*3
4*5/6.6
2

在单独计算每个项的值之后，我们将它们相加，同时注意每个表达式前面的符号。例如，表达式 4*5/6.6 前面有一个减号，所以我们应该从最终结果中减去该项的值，而不是加上它。对于这个例子，将发生以下序列：

1. fResult（我们将用于表达式的最终结果）的值将被设置为零。
2. 由于我们使用的是 *从右到左* 解析，右边的项将比左边的项先计算。
3. 项 2 将被计算并加到fResult。因此，fResult 的值将为 2。
4. 项 4*5/6.6（其值为 3.030303）将被计算并（由于负号）从最终结果中减去。因此，fResult 将包含 -1.030303。
5. 项 1*2*3（其值为 6）将被计算并加到最终结果。因此，fResult 将包含 4.969697。

让我们来看一下以下代码片段

bool EvaluateExpression(const char * strExpression, double & fResult)
{
    // Evaluates the value of each term.
    int nLength = strlen(strExpression);
    int nEnd = nLength - 1;
    double fTerm;
    fResult = 0.0;
    // Searches the expression from right to left for a '+'
    // or '-', i.e. partition the expression
    //  into terms.
    for (int i = nLength - 1; i >= 0; i--)
        if (strExpression[i] == '+')
        {
            if (!EvaluateTerm(strExpression + i + 1, nEnd - i, fTerm))
                // Invalid term!!!
                return false;
            fResult += fTerm;
            nEnd = i-1;
        }
        else
            if (strExpression[i] == '-')
            {
                if (!EvaluateTerm(strExpression + i + 1, nEnd - i, fTerm))
                    // Invalid term!!!
                    return false;
                fResult -= fTerm;
                nEnd = i-1;
            }

    // The first term is often not preceded by a sign!!!
    if (strExpression[0] != '+' && strExpression[0] != '-')
    {
        if (!EvaluateTerm(strExpression, nEnd + 1, fTerm))
            // Invalid term!!!
            return false;
        fResult += fTerm;
        nEnd = i-1;
    }

    return true;
}

正如我们所见，该函数从 *右到左* 搜索表达式字符串以查找任何 '+' 或 '-'。一个项要么位于两个符号（'+' 或 '-'）之间，要么位于一个符号和一个表达式的末尾之间。找到一个项后，函数 EvaluateExpression 会调用另一个函数，即 EvaluateTerm 来计算找到的项的值。稍后，我们将看到 EvaluateTerm 函数是如何工作的。

函数计算出项的值后，会检查其符号并将项的值加到最终结果中。

现在，让我们看看 EvaluateTerm 函数。这个函数几乎和 EvaluateExpression 函数有相同的思路。就像我们处理表达式一样，找到一个项的值的更好方法是将其划分为数字并计算该项，同时注意每个数字前面的符号。例如：

4*5/6.6

我们将这个项划分为：

4
5
6.6

然后根据每个数字的符号计算结果。例如，对于项 4*5/6.6，将发生以下序列：

1. fResult（我们将用于 *项* 的最终结果）的值将被设置为一（而不是零）。
2. 由于我们使用的是 *从右到左* 解析，右边的数字将比左边的数字先计算。
3. fResult 将除以 6.6，结果为 0.151515。
4. fResult 将乘以 5，结果为 0.757576。
5. fResult 将乘以 4，结果为 3.030303，这就是该项的最终结果。

让我们看看这个函数的代码：

bool EvaluateTerm(const char * strTerm, int nTermLength, double & fResult)
{
    // Evaluates the value of each term.
    int nEnd = nTermLength - 1;
    fResult = 1.0;
    double fNumber;
    // Searches the term from right to left for
    // a '*' or '/', i.e. partition the terms
    //  into numbers.
    for (int i = nEnd; i >= 0; i--)
        if (strTerm[i] == '*')
        {
            if (!StrToFloat(strTerm + i + 1, nEnd - i, fNumber))
                // Invalid number!!!
                return false;
            fResult *= fNumber;
            nEnd = i-1;
        }
        else
            if (strTerm[i] == '/')
            {
                if (!StrToFloat(strTerm + i + 1, nEnd - i, fNumber))
                    // Invalid number!!!
                    return false;
                fResult /= fNumber;
                nEnd = i-1;
            }

    // The first term should not be preceded by a sign!!!
    if (strTerm[0] != '*' && strTerm[0] != '/')
    {
        if (!StrToFloat(strTerm, nEnd + 1, fNumber))
            // Invalid number!!!
            return false;
        fResult *= fNumber;
    }

    return true;
}

正如我们所见，该函数从 *右到左* 跟踪该项，查找 '*' 或 '/'。就像项的情况一样，一个数字要么位于两个符号（现在是 '*' 和 '/'，而不是 '+' 和 '-'）之间，要么位于一个符号和一个 *项* 的末尾之间。

注意：StrToFloat 函数将字符串转换为它所代表的值。

最终注释

在完成文章之前，我想提及以下两点：

1. 用户应验证表达式不包含任何无效字符。在示例中，这是使用 VerifyExpression 函数完成的。此函数会搜索表达式字符串中除了 '+', '-', '*', '/', '.', 和 '0'-'9' 之外的任何字符。如果找到这样的字符，它将通知表达式无效。为了不使文章过于冗长，将函数留给读者自己查看，因为它不是什么难事。
2. 在这个示例中，我没有使用异常处理，因为它不是本文的主题。但在实际应用程序中，最好使用异常处理，而不是仅仅返回 'false'，这只能告诉我们“您的表达式无法计算”！

问题

1. 我本想在程序中输入 5*6，但为了测试 VerifyExpression 函数（该函数不接受空格作为有效字符），我决定输入表达式 5 *6 和 5* 6。我预计程序会显示“无效表达式！”，但令我惊讶的是，程序并没有这样做，而是显示 5 作为第一个测试结果，0 作为第二个测试结果。为什么？
2. 以下表达式是无效表达式，但程序并未报错，并可能产生意外结果：

   5**6
   5//6
   1+*2
   5*+6

   运行程序并测试它们。你能找出答案的原因吗？此外，你能解决这些问题吗？

3. 在我的程序中，我使用了 *从右到左* 解析。你认为我为什么这样做？试着做一个类似的程序，使用 *从左到右* 解析。哪个更容易？

备注：如果您查看 VerifyExpression 函数，您会注意到该函数只搜索无效字符。例如，表达式 5**6 会通过 VerifyExpression 函数的测试。您如何发现此类语法错误？

嗯，如果您解决了问题 2 中提到的问题，您就会发现此类语法错误会自动被发现。这是怎么回事？