用递归下降法进行表达式分析

递归下降法是一种常用的自顶向下的语法分析方法，可以用于对表达式进行分析。下面是一个简单的表达式分析器的代码实现：

// 定义 Token 类型
enum TokenType {
    NUMBER,
    PLUS,
    MINUS,
    MUL,
    DIV,
    LPAREN,
    RPAREN,
    END
};

// 定义 Token 结构体
struct Token {
    TokenType type;
    std::string value;
};

// 定义表达式分析器类
class Parser {
public:
    Parser(const std::string& input) : input_(input), current_(0) {}

    double Parse() {
        return Expr();
    }

private:
    // 定义递归下降的各个函数
    double Expr() {
        double left = Term();
        while (current_ < input_.size()) {
            Token op = GetToken();
            if (op.type != PLUS && op.type != MINUS) {
                UngetToken();  // 不是加减运算符，回退 Token
                break;
            }
            double right = Term();
            if (op.type == PLUS) {
                left += right;
            } else {
                left -= right;
            }
        }
        return left;
    }

    double Term() {
        double left = Factor();
        while (current_ < input_.size()) {
            Token op = GetToken();
            if (op.type != MUL && op.type != DIV) {
                UngetToken();  // 不是乘除运算符，回退 Token
                break;
            }
            double right = Factor();
            if (op.type == MUL) {
                left *= right;
            } else {
                left /= right;
            }
        }
        return left;
    }

    double Factor() {
        Token token = GetToken();
        if (token.type == NUMBER) {
            return std::stod(token.value);
        } else if (token.type == LPAREN) {
            double expr = Expr();
            token = GetToken();
            if (token.type != RPAREN) {
                throw std::runtime_error("Expected ')'");
            }
            return expr;
        } else {
            throw std::runtime_error("Invalid token");
        }
    }

    // 辅助函数
    Token GetToken() {
        if (unget_) {
            unget_ = false;
            return saved_token_;
        }

        while (current_ < input_.size() && std::isspace(input_[current_])) {
            ++current_;
        }
        if (current_ == input_.size()) {
            return {END, ""};
        }
        char ch = input_[current_];
        ++current_;
        if (ch >= '0' && ch <= '9') {
            std::string value;
            value.push_back(ch);
            while (current_ < input_.size() && input_[current_] >= '0' && input_[current_] <= '9') {
                value.push_back(input_[current_]);
                ++current_;
            }
            return {NUMBER, value};
        } else if (ch == '+') {
            return {PLUS, "+"};
        } else if (ch == '-') {
            return {MINUS, "-"};
        } else if (ch == '*') {
            return {MUL, "*"};
        } else if (ch == '/') {
            return {DIV, "/"};
        } else if (ch == '(') {
            return {LPAREN, "("};
        } else if (ch == ')') {
            return {RPAREN, ")"};
        } else {
            throw std::runtime_error("Invalid token");
        }
    }

    void UngetToken() {
        unget_ = true;
    }

    std::string input_;
    size_t current_;
    bool unget_ = false;
    Token saved_token_;
};

上述代码中，`TokenType` 是 Token 的类型枚举，`Token` 结构体表示一个 Token。`Parser` 类实现了表达式分析器，包括 `Expr()`、`Term()` 和 `Factor()` 函数，分别对应表达式的整体、运算符和操作数三个部分。`GetToken()` 和 `UngetToken()` 函数用于获取和回退 Token。最后，`Parse()` 函数调用 `Expr()` 函数开始分析整个表达式，并返回结果。

这个表达式分析器可以处理包括加减乘除运算和括号在内的简单表达式，例如：

Parser parser("1 + 2 * (3 - 4) / 5");
double result = parser.Parse();  // result = 1.6