递归解析四则运算表达式

"郭炜教授的《程序设计与算法》课程中的递归（二）部分，主要讲解如何使用递归方法解决四则运算表达式的计算问题。该内容涉及到C语言编程，通过递归函数实现对表达式的解析和求值。" 在计算机科学中，递归是一种解决问题的方法，它通过调用自身来解决更小规模的相同问题。在这个例子中，郭炜教授阐述了如何利用递归来解析和计算包含加、减、乘、除运算的数学表达式。递归的关键在于将复杂问题分解为更简单的子问题，直至子问题变得足够简单可以直接解答。 首先，表达式是由项组成的，而项又由因子和运算符构成。这个结构可以形成一个递归定义： 1. 表达式可以是一个项，加上一个可选的加或减运算符，后面跟着另一个项。 2. 项可以是一个因子，加上一个可选的乘或除运算符，后面跟着另一个因子。 3. 因子可以是括号内的表达式，或者是一个整数。 基于这样的定义，我们可以设计三个递归函数： - `expression_value()`：求一个表达式的值。它首先计算第一项的值（`term_value()`），然后在一个循环中处理后续的加减运算符和项。 - `term_value()`：求一个项的值。它先计算第一因子的值（`factor_value()`），然后在一个循环中处理后续的乘除运算符和因子。 - `factor_value()`：求一个因子的值。因子可能是整数或者括号内的表达式。如果遇到左括号，就调用`expression_value()`，否则直接读取整数值。 在C语言代码中，`peek()`函数用来查看输入流中的下一个字符而不移除它，`get()`函数则用于从输入流中获取并移除一个字符。递归函数通过不断地调用自身处理表达式的各个部分，直到遇到不能再细分的基础情况（如整数或括号内的表达式）。 这个递归算法可以正确处理像`(2+3)*(5+7)+9/3`这样的输入，并返回结果63。它展示了递归在解决复杂计算问题时的强大之处，尤其是在处理具有层次结构的数据或问题时。通过这种方式，递归可以优雅地映射到问题的自然结构，使得代码更加清晰和简洁。