这是我在教科书中找到的一段代码，用于使用递归来评估前缀表达式。我无法理解这段代码及其经历的过程。
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;
}
我想我主要对 return 语句以及它最终如何导致解决前缀表达式感到困惑。提前致谢！
每次调用 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）。
为了得到这些“东西”是什么，函数 eval() 被调用，并更新了 i 的值。每次调用 eval() 都会获取下一个表达式的值，并更新位置 i。
因此，对 eval() 的 2 次连续调用获得以下 2 个表达式的值。
然后我们将 + 运算符应用于 2 个值，并返回结果。
这将有助于完成一个示例，例如"+ * 2 3 * 4 5"，它是(2*3)+(4*5)的前缀表示法。
理解递归示例的最好方法是通过一个示例来工作：
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。重要的是在读取i后递增a[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，然后返回结果。
与其将代码分解成块等，我将尝试尽可能简单地解释这个概念。
eval 函数总是跳过空格，以便它指向表达式字符串中当前位置的数字字符 ('0'->'9')、加法 ('+') 或乘法 ('*')。
如果它遇到一个数字，它会继续吃数字数字，直到它到达一个非数字数字，以整数格式返回总结果。
如果遇到运算符（'+' 和 '*'），它需要两个整数，因此 eval 调用自身两次以从表达式字符串中获取接下来的两个数字并将结果作为整数返回。
没有指定“eval() + eval()”中的哪个 eval 是首先评估的。这对于交换运算符来说是可以的，但对于 - 或 / 会失败，因为 eval() 作为副作用会推进全局位置计数器，以便（及时）第二个 eval 获得（在空间中）第二个表达式。但这很可能是（在太空中）第一次评估。
我认为修复很容易；分配给一个温度并用它计算：
if (a[i] == '-')
{ i++; int tmp = eval(); return tmp - eval(); }
所以这段代码只能吃+、*、空格和数字。它应该吃一个可以是以下命令之一的命令：
- + <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.
}
您给出的示例使用了几个全局变量。它们在函数范围之外持续存在，并且必须在调用函数之前进行初始化。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
返回值要么是找到的值，要么是运算符的结果和找到的后续结果。因此递归地，该函数连续查看输入字符串并执行操作，直到字符串结束或找到无效字符。