面试题：Rust变量在复杂数据结构中的应用及优化

实际场景：简单编译器语法树

假设我们要构建一个简单的编译器语法树，用于解析算术表达式，例如 (3 + 5) * 2。

数据结构定义

枚举定义

enum Token {
    Number(i32),
    Plus,
    Minus,
    Multiply,
    Divide,
    LeftParen,
    RightParen,
}

嵌套结构体定义

struct Expr {
    left: Box<Expr>,
    op: Token,
    right: Box<Expr>,
}

impl Expr {
    fn new(left: Box<Expr>, op: Token, right: Box<Expr>) -> Self {
        Expr { left, op, right }
    }
}

struct NumberExpr {
    value: i32,
}

impl NumberExpr {
    fn new(value: i32) -> Self {
        NumberExpr { value }
    }
}

变量声明与初始化

解析器构建

fn parse(tokens: &[Token]) -> Option<Box<Expr>> {
    let mut index = 0;
    fn parse_expr(tokens: &[Token], mut index: &mut usize) -> Option<Box<Expr>> {
        let left = parse_term(tokens, index)?;
        loop {
            match tokens.get(*index) {
                Some(Token::Plus) | Some(Token::Minus) => {
                    let op = tokens[*index];
                    *index += 1;
                    let right = parse_term(tokens, index)?;
                    return Some(Box::new(Expr::new(left, op, right)));
                }
                _ => break,
            }
        }
        Some(left)
    }

    fn parse_term(tokens: &[Token], mut index: &mut usize) -> Option<Box<Expr>> {
        let left = parse_factor(tokens, index)?;
        loop {
            match tokens.get(*index) {
                Some(Token::Multiply) | Some(Token::Divide) => {
                    let op = tokens[*index];
                    *index += 1;
                    let right = parse_factor(tokens, index)?;
                    return Some(Box::new(Expr::new(left, op, right)));
                }
                _ => break,
            }
        }
        Some(left)
    }

    fn parse_factor(tokens: &[Token], mut index: &mut usize) -> Option<Box<Expr>> {
        match tokens.get(*index) {
            Some(Token::LeftParen) => {
                *index += 1;
                let expr = parse_expr(tokens, index)?;
                if tokens.get(*index) == Some(&Token::RightParen) {
                    *index += 1;
                    Some(expr)
                } else {
                    None
                }
            }
            Some(Token::Number(n)) => {
                let num_expr = Box::new(Expr::new(
                    Box::new(NumberExpr::new(*n).into()),
                    Token::Plus,
                    Box::new(NumberExpr::new(0).into()),
                ));
                *index += 1;
                Some(num_expr)
            }
            _ => None,
        }
    }

    parse_expr(tokens, &mut index)
}

所有权转移

所有权转移在函数间：在 parse 函数及其内部子函数中，当构建 Expr 结构体实例时，left 和 right 字段的所有权被转移到 Expr 实例中。例如，Box::new(Expr::new(left, op, right)) 这里 left 和 right 的所有权被转移到新创建的 Expr 实例中。

优化技巧

减少不必要的内存分配和复制
- 使用 Box 而不是堆上的完整复制：在 Expr 结构体中使用 Box<Expr> 来避免在栈上分配过多内存，因为 Expr 结构体本身可能包含递归结构，如果直接在栈上分配可能导致栈溢出。Box 只在堆上分配一次内存，并且在所有权转移时，只复制一个指针，而不是整个结构体。
- 复用已有的数据结构：在解析过程中，尽量复用已经创建的 Expr 或 NumberExpr 实例，而不是每次都重新分配内存。例如，在 parse_factor 中，对于数字解析创建 NumberExpr 实例时，可以根据情况复用相关部分，而不是重复创建相似的结构。
- 避免中间结果的不必要存储：在解析过程中，尽量直接构建最终的语法树，而不是生成大量中间结果并存储。例如，在 parse_expr 和 parse_term 函数中，直接根据解析的操作符和子表达式构建最终的 Expr 实例，而不是先存储所有子表达式，再统一构建。

通过上述方式，可以在包含嵌套结构体和枚举的复杂数据结构（如编译器语法树）中，合理地定义和使用变量，确保内存安全和高效性能。

星途面试题库

面试题：Rust变量在复杂数据结构中的应用及优化

知识考点

面试题答案

实际场景：简单编译器语法树

数据结构定义

变量声明与初始化

所有权转移

优化技巧