Build AST Expression tree from RPN Tokens

I am trying to implement a parser for my to-be published crate. I have converted the input into Tokens and then fromInfix to RPN but then while building the tree I am having some issues. My issue is that I can't find a way to handle brackets , () without running into borrow checker errors. (the rest works)

An example input is this

 [Term(1), Operator(+), OpenParenthesis, Term(2), Operator(*), Term(3), CloseParenthesis] // infix 
 [Term(1), Term(2), Term(3), CloseParenthesis, Operator(*), OpenParenthesis, Operator(+)] // rpn (passed to into_expression_tree

The tree building function

pub(super) fn into_expression_tree(rpn_tokens  : Vec<Token>) -> Option<Expression> {
        let mut stack: Vec<Expression> = Vec::new();

        // TODO : MAYBE give more infomation , why give expr is invalid instead of just None
        for token in rpn_tokens.into_iter() {
            match token {
                Token::Term(term) => stack.push(term.into()),
                Token::Operator(operator) => {
                    let right = stack.pop()?;
                    let left = stack.pop()?;
                    stack.push(Expression::new_binary(operator, left, right));  
                },
                _ => todo!()
            }
        }

        match stack.len() {
            1 => Some(stack.pop().unwrap()),
            _ => {
                println!(" stack.len() != 1 so None");
                None
            }
        }
    }

I am not sure if this is need but here is the infix to rpn convertor


pub(super) fn to_rpn(vec : Vec<Token>) -> Vec<Token> {
        let mut output: Vec<Token> = Vec::new();
        let mut operator_stack: Vec<Token> = Vec::new();

        for token in vec {
            match token {
                Token::Term(_) => output.push(token),
                Token::Operator(op1) => {
                    while let Some(&Token::Operator(ref op2)) = operator_stack.last() {
                        if op1.precedence() <= op2.precedence() {
                            output.push(operator_stack.pop().unwrap());
                        } else {
                            break;
                        }
                    }
                    operator_stack.push(Token::Operator(op1));
                }
                Token::OpenParenthesis => operator_stack.push(token),
                Token::CloseParenthesis => {
                    output.push(Token::CloseParenthesis);
                
                    while let Some(top) = operator_stack.pop() {
                        if let Token::OpenParenthesis = top {
                            break;
                        }
         
                        output.push(top);
                    }

                    output.push(Token::OpenParenthesis);
                }

            }
        }
  
        while let Some(op) = operator_stack.pop() {
            output.push(op);
        }
  
        output
    }

And finally the struct definitions..



pub(super) enum Token {
    Term(f64),
    Operator(ArithmeticOperation),
    OpenParenthesis,
    CloseParenthesis
}

impl From<f64> for Token {
    fn from(value: f64) -> Self {
        Token::Term(value)
    }
}

impl From<ArithmeticOperation> for Token {
    fn from(value: ArithmeticOperation) -> Self {
        Token::Operator(value)
    }
}

impl ArithmeticOperation {
    const fn precedence(&self) -> i32 {
        match self {
            ArithmeticOperation::Plus | ArithmeticOperation::Minus => 1,
            ArithmeticOperation::Mal | ArithmeticOperation::Durch => 2,
        }
    }
}



#[derive(Clone)]
#[cfg_attr(test, derive(PartialEq))]
pub enum Expression {
    /// Represents a basic unit in a mathematical expression.
    Term(Term),

    /// Represents a binary operation between two expressions.
    ///
    /// The `Binary` variant includes the type of mathematical operation and the left
    /// and right operands as boxed expressions.
    Binary {
        /// - `operation`: The type of mathematical operation being performed, such as
        ///    addition, subtraction, multiplication, or division. It is of type `ArithmeticOperation`.
        operation: ArithmeticOperation,

        /// - `left`: The left operand of the binary operation, represented as a boxed `Expression`.
        left: Box<Expression>,

        /// - `right`: The right operand of the binary operation, also represented as a boxed `Expression`.
        right: Box<Expression>,
    },

    /// Represents a more complex expression that contains nested expressions.
    ///
    /// The `Nested` variant allows expressions to be nested within parentheses.
    Nested(Box<Expression>),
}
impl Expression {
    pub(crate) fn new_binary(operation: ArithmeticOperation,left: Expression,right: Expression) -> Self {
        Expression::Binary { operation , left : Box::new(left) , right : Box::new(right) }
    }
}

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.