需要帮助理解递归前缀表达式求值器

Question

这是我在教材中找到的一段代码，用于使用递归评估前缀表达式。我对这段代码和它所经历的过程感到困惑。

    char *a; int i;
    int eval()
      { int x = 0;
        while (a[i] == ' ') i++;
        if (a[i] == '+')
          { i++; return eval() + eval(); }
        if (a[i] == '*')
          { i++; return eval() * eval(); }
        while ((a[i] >= '0') && (a[i] <= '9'))
           x = 10*x + (a[i++] - '0');
        return x;
      }

我想我主要是对返回语句感到困惑，以及它最终如何解决前缀表达式。提前致谢！

- user3421510

---

一个建议（因为我刚刚偶然看到了Eric Lippert的一篇文章）是将技术细节与逻辑分开。这里是我在转述Eric的话。在你的代码中，重要的事情似乎是索引和字符。但实际上你正在做的事情（并且试图理解的）是构建抽象对象之间关系的模型，即数字和运算符，并对其进行评估。（顺便说一句，该模型恰好是建立在堆栈上的;-)）。所以我会先将文本转换成逻辑项，即标记（即词法分析），然后以抽象的方式处理它们。分而治之。 - Peter - Reinstate Monica

Answer 1

最好理解递归示例的方法是通过一个示例进行实践：

char* a = "+11 4"

首先，i 被初始化为0，因为没有默认的初始化器。 i 也是全局的，所以对它的更新将影响所有调用 eval()。

i = 0, a[i] = '+'

没有前导空格，所以第一个 while 循环条件失败。第一个 if 语句成功，i 被增加到 1，然后执行 eval() + eval()。我们将一个接一个地对它们进行评估，然后在获得结果后回来。

i = 1, a[1] = '1'

再次强调，没有前导空格，因此第一个while循环失败。第一个和第二个if语句也失败了。在最后一个while循环中，'1'介于0和9之间（基于ascii值），因此x变为0 + a [1] - '0'，即0 + 1 = 1。重要的是，在读取a[i]之后，i会增加，然后i被增加。 while循环的下一次迭代将添加到x。这里x = 10 * 1 + a[2] - '0'，或者10 + 1 = 11。有了正确的x值，我们可以退出eval()并返回第一个操作数的结果，这里再次是11。

i = 2, a[2] = '4'

与前一步相同，eval()调用中仅执行最后一个while循环语句。x = 0 + a[2] - '0'，或者0 + 4 = 4。因此我们返回4。

此时控制流返回到eval()的原始调用，并且现在我们拥有操作数的两个值。我们只需执行加法即可得到11 + 4 = 15，然后返回结果。

- Michael Hagar

---

谢谢您的回复！它确实帮了我很多。我现在理解得更多了，但是我仍然不明白代码中的 "return eval() + eval()" 如何知道何时停止。它如何知道在自己的 eval 中使最后一位数字为 "4"，就像您的示例中一样？这是我最困惑的事情，但我觉得这对于理解至关重要。 - user3421510

"return eval()+eval()" 代码中的第一个 eval() 将从 '1' 开始并在空格处结束，捕获了 11。第二个 eval() 调用将去除空格，然后捕获 4，在字符串的空终止符处停止，并返回 4。 - Chris

行为很危险，在 eval() + eval() 表达式中没有指定调用函数的顺序。由于它只使用了 + 和 *（交换操作），所以这是可以的；但是如果添加 - 和 /，那么一切都可能失控... - vonbrand

Answer 2

每次调用eval()时，它计算从位置i开始的下一个表达式的值，并返回该值。

在eval内部：
第一个while循环只是忽略所有空格。
然后有3种情况：

(a) 评估以+开头的表达式（即形式为A+B的表达式，在前缀中为"+ A B"）

(b) 评估以*开头的表达式（即A*B = "* A B"）

(c) 评估整数值（即任何连续的数字序列）

最后的while循环处理情况(c)。

情况(a)的代码类似于情况(b)的代码。考虑情况(a)：
如果我们遇到一个+号，这意味着我们需要将序列中找到的下两个“东西”相加。这些“东西”可能是数字，也可能是要求值的表达式（例如X+Y或X*Y）。

为了得到这些“things”是什么，函数eval()被调用并使用更新后的i值。每次调用eval()都会获取下一个表达式的值，并更新位置i。

因此，连续两次调用eval()将获得2个接下来的表达式的值。
然后，我们将+运算符应用于这2个值，并返回结果。

通过一个例子（如"+ * 2 3 * 4 5"）来进行操作会有所帮助，它是前缀表示法，表示为(2*3)+(4*5)。

- dhrumeel

---

谢谢您的回复！现在我对此有了更清晰的认识。如果我想要用递归方式实现后缀表达式求值，我只需要倒着进行吗？也就是说，我应该从字符串的末尾开始，然后执行 "i--" 操作吗？或者这样行不通？ - user3421510

Answer 3

所以这段代码只能处理 +、*、空格和数字。它应该接收一个命令，可以是以下之一：

- + <op1> <op2>
- * <op1> <op2>
<number>

它获取一个指向字符串的指针和一个读取位置，在程序沿着该字符串时递增。

   char *a; int i;
    int eval()
      { int x = 0;
        while (a[i] == ' ') i++; // it eats all spaces
        if (a[i] == '+') 
       /* if the program encounters '+', two operands are expected next. 
          The reading position i already points just before the place 
          from which you have to start reading the next operand 
          (which is what first eval() call will do). 
          After the first eval() is finished, 
          the reading position is moved to the begin of the second operand, 
          which will be read during the second eval() call. */
          { i++; return eval() + eval(); }
        if (a[i] == '*') // exactly the same, but for '*' operation.
          { i++; return eval() * eval(); }
        while ((a[i] >= '0') && (a[i] <= '9')) // here it eats all digit until something else is encountered.
           x = 10*x + (a[i++] - '0'); // every time the new digit is read, it multiplies the previously obtained number by 10 and adds the new digit.
        return x; 
        // base case: returning the number. Note that the reading position already moved past it. 
      }

- Ashalynd

Answer 4

汤里有一根头发可能是评估顺序的问题，参见https://www.securecoding.cert.org/confluence/display/seccode/EXP10-C.+Do+not+depend+on+the+order+of+evaluation+of+subexpressions+or+the+order+in+which+side+effects+take+place。

在“eval() + eval()”中没有指定哪个eval首先被评估。对于可交换运算符来说这没问题，但对于-或/来说会失败，因为eval()作为副作用会推进全局位置计数器，以便（按时间）第二个eval得到（按空间）第二个表达式。但那可能是（按空间）第一个eval。

我认为修复很容易；分配给临时变量并使用它进行计算：

if (a[i] == '-')
      { i++; int tmp = eval(); return tmp - eval(); }

- Peter - Reinstate Monica

Answer 5

你所给出的示例使用了一些全局变量。它们在函数范围外持续存在，并且必须在调用函数之前进行初始化。 i 应该被初始化为 0，这样你就从字符串的开头开始，而前缀表达式是字符串 a。

运算符是你的前缀，因此应该是第一个非空字符，如果你以一个数字（数字串）开头，那么你已经完成了，那就是结果。

例如：a = " + 15 450"

eval() finds '+' at i = 1
    calls eval() 
        which finds '1' at i = 3 and then '5' 
        calculates x = 1 x 10 + 5 
    returns 15
    calls eval() 
        which finds '4' at i = 6 and then '5' and then '0'
        calclulates x = ((4 x 10) + 5) x 10) + 0
    returns 450
    calculates the '+' operator of 15 and 450
returns 465

返回值可以是找到的值或运算符的结果以及后续找到的结果。 因此，递归地，该函数连续查看输入字符串并执行操作，直到字符串结束或找到无效字符为止。

- FredA

Answer 6

与其将代码分成块等等，我会尽量简单地解释这个概念。

eval函数总是跳过空格，以便它指向表达式字符串中当前位置的数字字符('0'-'9')、加法('+')或乘法('*')。

如果它遇到一个数字，它会继续吃掉数字位数，直到它到达一个非数字位数，并以整数格式返回总结果。

如果它遇到运算符 ('+'和'*')，它需要两个整数，因此eval调用自身两次，从表达式字符串获取下两个数字，并将该结果作为整数返回。

- Chris