面试题：C++递归函数实现表达式求值

Question

给定一个包含加、减、乘、除（+、-、*、/）运算符以及括号的算术表达式字符串，例如"(3+5)*(2 - 1)"，请使用C++递归函数实现该表达式的求值。需要考虑运算符优先级、括号处理以及浮点数运算等情况，同时说明递归的设计思路及如何处理递归过程中的错误情况。

Answer 1

1. 递归设计思路

1. 基本原理：递归的核心思想是将复杂的表达式求值问题分解为多个子问题。对于一个算术表达式，括号内的子表达式可以看作是一个独立的求值单元，按照运算符优先级，先计算括号内的子表达式，再计算整个表达式。
2. 边界条件：当表达式中不再有括号，且只剩下一个数字或简单的二元运算时，递归结束。
3. 处理优先级：乘法和除法优先级高于加法和减法。在递归过程中，先处理乘除运算，再处理加减运算。

2. 处理递归过程中的错误情况

1. 语法错误：例如括号不匹配、运算符不合法等。可以通过在解析表达式时，检查括号的数量是否匹配，以及运算符是否在合法集合内（+、-、*、/）。
2. 除零错误：在进行除法运算时，检查除数是否为零，如果为零则抛出异常或返回错误提示。

3. C++ 代码实现

#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#include <stdexcept>

// 跳过空白字符
void skipWhitespace(const std::string& exp, size_t& i) {
    while (i < exp.length() && std::isspace(exp[i])) {
        ++i;
    }
}

// 获取下一个数字
double getNumber(const std::string& exp, size_t& i) {
    std::string numStr;
    while (i < exp.length() && (std::isdigit(exp[i]) || exp[i] == '.')) {
        numStr += exp[i];
        ++i;
    }
    --i; // 回退一个字符，因为循环结束时多走了一步
    std::istringstream iss(numStr);
    double num;
    iss >> num;
    return num;
}

// 处理乘除运算
double parseMulDiv(const std::string& exp, size_t& i) {
    double left = parseExpression(exp, i);
    while (true) {
        skipWhitespace(exp, i);
        if (i + 1 >= exp.length()) break;
        char op = exp[i + 1];
        if (op != '*' && op != '/') break;
        i += 2;
        double right = parseExpression(exp, i);
        if (op == '*') {
            left *= right;
        } else {
            if (right == 0) {
                throw std::runtime_error("Division by zero");
            }
            left /= right;
        }
    }
    return left;
}

// 处理加减运算
double parseAddSub(const std::string& exp, size_t& i) {
    double left = parseMulDiv(exp, i);
    while (true) {
        skipWhitespace(exp, i);
        if (i + 1 >= exp.length()) break;
        char op = exp[i + 1];
        if (op != '+' && op != '-') break;
        i += 2;
        double right = parseMulDiv(exp, i);
        if (op == '+') {
            left += right;
        } else {
            left -= right;
        }
    }
    return left;
}

// 解析表达式
double parseExpression(const std::string& exp, size_t& i) {
    skipWhitespace(exp, i);
    if (exp[i] == '(') {
        ++i;
        double result = parseAddSub(exp, i);
        skipWhitespace(exp, i);
        if (i >= exp.length() || exp[i] != ')') {
            throw std::runtime_error("Mismatched parentheses");
        }
        ++i;
        return result;
    } else {
        return getNumber(exp, i);
    }
}

// 主函数调用递归解析
double evaluateExpression(const std::string& exp) {
    size_t i = 0;
    return parseAddSub(exp, i);
}

你可以使用以下方式调用这个函数：

int main() {
    std::string expression = "(3 + 5) * (2 - 1)";
    try {
        double result = evaluateExpression(expression);
        std::cout << "Result: " << result << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}