Repository: nw-rs/citrus-cas (language: rust)

Issue:
switch from the shunting yard algorithm to recursive descent



Discussion / hints:

Fix patch:
diff --git a/Cargo.toml b/Cargo.toml
index e09a422..7687bc6 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -10,7 +10,7 @@ repository = "https://github.com/willemml/rcas"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
-nom = { version = "7.1.1", default-features = false }
+nom = { version = "7.1.1", default-features = false, features = ["alloc"] }
 heapless = "0.7.14"
 libm = "0.2.2"
 
diff --git a/src/bin/bin.rs b/src/bin/bin.rs
index 76313d0..aced37e 100644
--- a/src/bin/bin.rs
+++ b/src/bin/bin.rs
@@ -1,4 +1,4 @@
-use std::{io, str::FromStr};
+/*use std::{io, str::FromStr};
 use heapless::{String, Vec};
 
 use rcas::{Expression, VariableMap, ExpressionMap, UserFunctionMap,Error,};
@@ -43,3 +43,5 @@ fn main() {
         }
     }
 }
+*/
+fn main() {}
\ No newline at end of file
diff --git a/src/expression.rs b/src/expression.rs
deleted file mode 100644
index 8c09667..0000000
--- a/src/expression.rs
+++ /dev/null
@@ -1,219 +0,0 @@
-use core::{
-    fmt::{Display, Formatter, self},
-    str::FromStr,
-};
-
-use heapless::{Vec, String};
-
-use crate::{
-    parser::math_expr,
-    token::{Operation, Token},
-    Error,
-    expression_map::ExpressionMap,
-};
-
-fn function_constructor<const E: usize>(tokens: Vec<Token, E>) -> Result<Vec<Token, E>, Error> {
-    let mut output = Vec::new();
-
-    let mut function_staging = String::<8>::new();
-    for token in tokens {
-        match token {
-            Token::Var(var) => function_staging.push(var).map_err(|_| Error::NotEnoughMemory)?,
-            _ => {
-                match function_staging.len() {
-                    0 => {}
-                    1 => output.push(Token::Var(function_staging.pop().unwrap())).unwrap(),
-                    _ => {
-                        output.push(Token::Func(function_staging.clone()).into()).unwrap();
-                        function_staging.clear();
-                    }
-                }
-                output.push(token).map_err(|_| Error::NotEnoughMemory)?;
-            }
-        }
-    }
-
-    Ok(output)
-}
-
-/// the shunting yard algorithm converts an infix
-/// notation expression, for example 5 + 2 * 7, into
-/// a postfix notation expression, for example 5 2 7 * +
-fn shunting_yard<const E: usize>(tokens: Vec<Token, E>) -> Result<Vec<Token, E>, Error> {
-    let mut output = Vec::new();
-    let mut stack: Vec<Token, E> = Vec::new();
-
-    for token in tokens {
-        match token {
-            Token::Op(op) => {
-                while let Some(&Token::Op(top)) = stack.last() {
-                    if top.precedence() > op.precedence() || (top.precedence() == op.precedence() && !top.right_associative()) {
-                        output
-                            .push(stack.pop().unwrap())
-                            .map_err(|_| Error::NotEnoughMemory)?;
-                    } else {
-                        break;
-                    }
-                }
-                stack.push(token).map_err(|_| Error::NotEnoughMemory)?;
-            }
-            Token::Paren(true) => {
-                stack.push(token).map_err(|_| Error::NotEnoughMemory)?;
-            }
-            Token::Paren(false) => {
-                while let Some(stack_token) = stack.last() {                 
-                    if stack_token == &Token::Paren(true) {
-                        stack.pop().unwrap();
-                        break;
-                    } else {
-                        output
-                            .push(stack.pop().unwrap())
-                            .map_err(|_| Error::NotEnoughMemory)?;
-                    }
-                }
-                //TODO: this is incorrect, because it doesn't check whether or not it's in a function
-                stack.push(Token::Terminator).map_err(|_| Error::NotEnoughMemory)?;
-            }
-            _ => {
-                output.push(token).map_err(|_| Error::NotEnoughMemory)?;
-            }
-        }
-    }
-
-    while let Some(token) = stack.pop() {
-        output.push(token).map_err(|_| Error::NotEnoughMemory)?;
-    }
-
-    Ok(output)
-}
-
-/// A sequence of tokens which make up
-/// an expression in postfix notation
-#[derive(Debug, Clone)]
-pub struct Expression<const E: usize> {
-    //TODO: implement postfix to infix fmt conversion
-    pub tokens: Vec<Token, E>,
-}
-
-impl<const E: usize> FromStr for Expression<E> {
-    type Err = Error; //TODO: error type
-
-    fn from_str(s: &str) -> Result<Self, Self::Err> {
-        let infix = math_expr(s).unwrap().1;
-        let function_added = function_constructor(infix)?;
-        let tokens = shunting_yard(function_added)?;
-        Ok(Expression { tokens })
-    }
-}
-
-//TODO: write as infix instead of postfix
-impl<const E: usize> fmt::Display for Expression<E> {
-    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
-        self.tokens.iter().try_for_each(|token| {
-            write!(f, "{}", token)
-        })?;
-        Ok(())
-    }
-}
-
-impl<const E: usize> Expression<E> {
-    pub fn new(tokens: Vec<Token, E>) -> Self {
-        Expression { tokens }
-    }
-
-    pub fn evaluate(&self) -> Result<Expression<E>, Error> {
-        let mut stack: Vec<Token, E> = Vec::new();
-
-        for token in self.tokens.iter() {
-            match token {
-                Token::Number(f) => {
-                    stack
-                        .push(Token::Number(*f))
-                        .map_err(|_| Error::NotEnoughMemory)?;
-                }
-                Token::Op(op) => {
-                    //TODO: convert into a confined array to support non-binary operations
-                    let rhs: f32 = match stack.pop().unwrap() {
-                        Token::Number(n) => n,
-                        _ => return Ok(Expression::new(Vec::new())),
-                    };
-                    let lhs: f32 = match stack.pop().unwrap() {
-                        Token::Number(n) => n,
-                        _ => return Ok(Expression::new(Vec::new())),
-                    };
-
-                    let result = match op {
-                        Operation::Add => lhs + rhs,
-                        Operation::Subtract => lhs - rhs,
-                        Operation::Multiply => lhs * rhs,
-                        Operation::Divide => lhs / rhs,
-                        Operation::Power => libm::powf(lhs, rhs),
-                    };
-
-                    stack
-                        .push(Token::Number(result))
-                        .map_err(|_| Error::NotEnoughMemory)?;
-                }
-                _ => return Err(Error::InvalidSyntax), //TODO: create value enum and implement value precedence to sort and combine by num, then var, then func
-            }
-        }
-
-        Ok(Expression::new(stack))
-    }
-
-    pub fn approximate<const N: usize>(
-        &self,
-        maps: &Vec<&dyn ExpressionMap<E>, N>, //forgive me father for I have sinned
-    ) -> Result<Approx, Error> {
-        let mut exprs = Expression::new(self.tokens.clone());
-
-        //this checks whether the maps need to continue operating on the expression
-        while maps.iter().fold(false, |t, map| {
-            t || map.stack_contains(&exprs)
-        }) {
-            //every ExpressionMap is applied to the expression
-            for map in maps.iter() {
-                exprs = map.approximate(&exprs);
-            }
-        }
-
-        let mut ensure_implimentation: Expression<E> = Expression::new(Vec::new());
-        for token in exprs.tokens.iter() {
-            match token {
-                &Token::Terminator => {},
-                _ => {
-                    ensure_implimentation.tokens.push(token.clone())
-                        .map_err(|_| Error::NotEnoughMemory)?;
-                }
-            }
-        }
-
-        let mut result = ensure_implimentation
-            .evaluate()?
-            .tokens;
-
-        if result.len() != 1 {
-            //this should not occur, because variables and functions should be replaced with numbers, or return undefined before this
-            return Ok(Approx::Undef);
-        }
-        Ok(match result.pop().unwrap() {
-            Token::Number(n) => Approx::Num(n),
-            _ => Approx::Undef,
-        })
-    }
-}
-
-#[derive(Debug, Clone, Copy)]
-pub enum Approx {
-    Num(f32),
-    Undef,
-}
-
-impl Display for Approx {
-    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
-        match self {
-            Approx::Num(n) => write!(f, "{}", n),
-            Approx::Undef => write!(f, "undefined"),
-        }
-    }
-}
diff --git a/src/expression_map.rs b/src/expression_map.rs
deleted file mode 100644
index 2f1dc2a..0000000
--- a/src/expression_map.rs
+++ /dev/null
@@ -1,206 +0,0 @@
-use heapless::{Vec, LinearMap, String,};
-
-use crate::{token::Token, Expression, Error, Approx};
-
-/// parses tokens which need modifiable definition
-pub trait ExpressionMap<const E: usize> {
-    fn stack_contains(&self, stack: &Expression<E>) -> bool;
-    fn evaluate(&self, stack: &Expression<E>) -> Expression<E>;
-    fn approximate(&self, stack: &Expression<E>) -> Expression<E>;
-}
-
-pub struct VariableMap<const E: usize, const L: usize> {
-    map: LinearMap<char, Expression<E>, L>,
-}
-
-impl<const E: usize, const L: usize> ExpressionMap<E> for VariableMap<E, L> {
-    fn stack_contains(&self, stack: &Expression<E>) -> bool {
-        for token in stack.tokens.iter() {
-            match token {
-                Token::Var(_) => return true,
-                _ => continue,
-            }
-        }
-        return false;
-    }
-
-    fn evaluate(&self, stack: &Expression<E>) -> Expression<E> {
-        Expression { tokens: stack.tokens.clone() }
-    }
-
-    fn approximate(&self, stack: &Expression<E>) -> Expression<E> {
-        Expression { tokens: stack.tokens
-        .iter()
-        .map(|token| {
-            match token {
-                Token::Var(var) => {
-                    if let Some(expr) = self.map.get(&var) {
-                        match expr.approximate(&Vec::<&dyn ExpressionMap<E>, 1>::from_slice(&[self]).unwrap()) {
-                            Ok(Approx::Num(n)) => Ok(Some(Token::Number(n))),
-                            Ok(Approx::Undef) => Ok(None),
-                            Err(err) => Err(err),
-                        }
-                    } else {
-                        return Ok(None);
-                    }
-                }
-                _ => Ok(Some(token.clone())),
-            }
-        })
-        .filter_map(Result::transpose)
-        .collect::<Result<Vec<Token, E>, Error>>()
-        .unwrap() }
-    }
-}
-
-impl<const E: usize, const L: usize> VariableMap<E, L> {
-    pub fn new() -> Self {
-        VariableMap {
-            map: LinearMap::<char, Expression<E>, L>::new(),
-        }
-    }
-
-    pub fn insert(&mut self, var: char, expr: Expression<E>) -> Result<Option<Expression<E>>, Error> {
-        self.map.insert(var, expr).map_err(|_| Error::NotEnoughMemory)
-    }
-
-    pub fn get(&self, var: char) -> Option<&Expression<E>> {
-        self.map.get(&var)
-    }
-
-    pub fn remove(&mut self, var: char) -> Option<Expression<E>> {
-        self.map.remove(&var)
-    }
-
-    pub fn clear(&mut self) {
-        self.map.clear();
-    }
-
-    pub fn len(&self) -> usize {
-        self.map.len()
-    }
-}
-
-pub struct UserFunctionMap<const E: usize, const L: usize, const V: usize> {
-    function_map: LinearMap<String<8>, Expression<E>, L>,
-    argument_list: LinearMap<String<8>, Vec<char, V>, L>,
-}
-
-impl<const E: usize, const L: usize, const V: usize> ExpressionMap<E> for UserFunctionMap<E, L, V> {
-    fn stack_contains(&self, stack: &Expression<E>) -> bool {
-        for token in stack.tokens.iter() {
-            match token {
-                Token::Func(_) => return true,
-                _ => continue,
-            }
-        }
-        return false;
-    }
-
-    fn evaluate(&self, stack: &Expression<E>) -> Expression<E> {
-        Expression { tokens: stack.tokens.clone() }
-    }
-
-    fn approximate(&self, stack: &Expression<E>) -> Expression<E> {
-        let mut new_tokens = Vec::<Token, E>::new();
-        
-        let mut skip = 0;
-        for (i, token) in stack.tokens.iter().enumerate() {
-            if skip > 0 { //there has to be a better way to do this
-                skip -= 1;
-                continue;
-            }
-            
-            skip = 0; //skip the terminator
-            match token {
-                Token::Func(func) => {
-                    let mut arguments: Vec<Vec::<Token, V>, V> = Vec::new();
-                    let mut argument_approx: Vec<Approx, E> = Vec::new();
-                    let mut argument_count = 0;
-
-                    //fill the arguments vector with Vec::new()
-                    for _ in 1..arguments.capacity() {
-                        arguments.push(Vec::new()).map_err(|_| Error::NotEnoughMemory).unwrap();
-                    }
-
-                    for sub_token in stack.tokens.iter().skip(i + 1) {
-                        match sub_token {
-                            Token::Divider => argument_count += 1,
-                            Token::Terminator => break,
-                            _ => arguments[argument_count].push(sub_token.clone()).unwrap(),
-                        }
-                        skip += 1;
-                    }
-
-                    for vector in arguments.iter().take(argument_count + 1) {
-                        argument_approx
-                            .push(Expression::<V> { tokens: vector.clone() }
-                            .approximate(&Vec::<&dyn ExpressionMap<V>, E>::new()).unwrap()).unwrap();
-                    }
-
-                    for sub_token in self.function_map.get(&func).unwrap().tokens.iter() {
-                        match sub_token {
-                            Token::Var(var) => {
-                                if let Some(approx_token) = match argument_approx[self.argument_list.get(&func).unwrap().binary_search(var).unwrap()] {
-                                    Approx::Num(n) => Some(Token::Number(n)),
-                                    _ => unimplemented!(),
-                                }{
-                                    new_tokens.push(approx_token.clone()).unwrap();
-                                } else {
-                                    new_tokens.push(sub_token.clone()).unwrap();
-                                }
-                            }
-                            _ => new_tokens.push(sub_token.clone()).unwrap(),
-                        }
-                    }
-                }
-                _ => new_tokens.push(token.clone()).unwrap(),
-            }
-        }
-
-        Expression { tokens: new_tokens }
-    }
-}
-
-impl<const E: usize, const L: usize, const V: usize> UserFunctionMap<E, L, V> {
-    pub fn new() -> Self {
-        UserFunctionMap {
-            function_map: LinearMap::<String<8>, Expression<E>, L>::new(),
-            argument_list: LinearMap::<String<8>, Vec<char, V>, L>::new(),
-        }
-    }
-
-    pub fn insert_function(&mut self, name: String<8>, expr: Expression<E>) -> Result<Option<Expression<E>>, Error> {
-        self.function_map.insert(name, expr).map_err(|_| Error::NotEnoughMemory)
-    }
-
-    pub fn insert_arguments(&mut self, name: String<8>, vars: Vec<char, V>) -> Result<Option<Vec<char, V>>, Error> {
-        self.argument_list.insert(name, vars).map_err(|_| Error::NotEnoughMemory)
-    }
-
-    pub fn get_function(&self, name: String<8>) -> Option<&Expression<E>> {
-        self.function_map.get(&name)
-    }
-
-    pub fn get_arguments(&self, name: String<8>) -> Option<&Vec<char, V>> {
-        self.argument_list.get(&name)
-    }
-
-    pub fn remove_function(&mut self, name: String<8>) -> Option<Expression<E>> {
-        self.function_map.remove(&name)
-    }
-
-    pub fn remove_arguments(&mut self, name: String<8>) -> Option<Vec<char, V>> {
-        self.argument_list.remove(&name)
-    }
-
-    pub fn clear(&mut self) {
-        self.function_map.clear();
-        self.argument_list.clear();
-    }
-
-    pub fn len(&self) -> usize {
-        assert!(self.function_map.len() == self.argument_list.len());
-        self.function_map.len()
-    }
-}
diff --git a/src/expression_tree.rs b/src/expression_tree.rs
new file mode 100644
index 0000000..9adb8df
--- /dev/null
+++ b/src/expression_tree.rs
@@ -0,0 +1,108 @@
+use core::fmt;
+use alloc::boxed::Box;
+
+use heapless::{Vec, String};
+
+#[derive(Debug, Clone, PartialEq)]
+pub enum Numeric {
+    Integer(i32),
+    Decimal(f32),
+    Radical(i16, i16), //might be unnecessary?
+}
+
+impl fmt::Display for Numeric {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            Numeric::Integer(i) => write!(f, "{}", i),
+            Numeric::Decimal(d) => write!(f, "{}", d),
+            Numeric::Radical(r1, r2) => write!(f, "({})/({})", r1, r2), //must always be in the form of (a)/(b), for reinterpretation to work (?)
+        }
+    }
+}
+
+#[derive(Debug, Clone, PartialEq)]
+pub enum Atom {
+    Numeric(Numeric),
+    Variable(char),
+}
+
+impl fmt::Display for Atom {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            Atom::Numeric(n) => write!(f, "{}", n),
+            Atom::Variable(v) => write!(f, "{}", v),
+        }
+    }
+}
+
+//concrete syntax tree, not an abstract syntax tree
+#[derive(Debug, PartialEq)]
+pub enum Expression {
+    //atoms
+    Atom(Atom),
+
+    //unary operators
+    Negate(Box<Expression>),
+    Factorial(Box<Expression>),
+    Percent(Box<Expression>),
+
+    //binary operators
+    Add(Box<Expression>, Box<Expression>),
+    Subtract(Box<Expression>, Box<Expression>),
+    Multiply(Box<Expression>, Box<Expression>),
+    Divide(Box<Expression>, Box<Expression>),
+    Power(Box<Expression>, Box<Expression>),
+    Modulus(Box<Expression>, Box<Expression>),
+
+    //n-ary operators
+    Function { //TODO: make smaller somehow?
+        name: String<8>,
+        args: Vec<Box<Expression>, 8>,
+    },
+}
+
+impl Expression {
+    //reorganizes the expression tree to combine similar operations
+    pub fn simplify(&mut self) {
+        
+    }
+    //simplifies, then iterates the evaluation maps over the tree
+    pub fn evaluate(&self) -> Expression {
+        unimplemented!()
+    }
+    //evaluates, then iterates the approximation maps over the tree
+    pub fn approximate(&self) -> Result<f32, ()> {
+        unimplemented!()
+    }
+}
+
+impl fmt::Display for Expression {
+    //TODO: smarter parentheses, likely using some kind of traversal?
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            Expression::Atom(a) => write!(f, "{}", a),
+            
+            Expression::Negate(e) => write!(f, "-({})", e),
+            Expression::Factorial(e) => write!(f, "({})!", e),
+            Expression::Percent(e) => write!(f, "({})%", e),
+            
+            Expression::Add(l, r) => write!(f, "({} + {})", l, r),
+            Expression::Subtract(l, r) => write!(f, "({} - {})", l, r),
+            Expression::Multiply(l, r) => write!(f, "({} * {})", l, r),
+            Expression::Divide(l, r) => write!(f, "({} / {})", l, r),
+            Expression::Power(l, r) => write!(f, "({} ^ {})", l, r),
+            Expression::Modulus(l, r) => write!(f, "({} % {})", l, r),
+            
+            Expression::Function { name, args } => {
+                write!(f, "{}(", name)?;
+                for (i, arg) in args.iter().enumerate() {
+                    if i > 0 {
+                        write!(f, ", ")?;
+                    }
+                    write!(f, "{}", arg)?;
+                }
+                write!(f, ")")
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/src/lib.rs b/src/lib.rs
index 92e9fe0..d7932c8 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,18 +1,14 @@
 #![no_std]
 
-mod expression;
-mod parser;
-mod token;
-mod expression_map;
+extern crate alloc;
 
-pub use expression::{Approx, Expression};
-pub use expression_map::{ExpressionMap, VariableMap,UserFunctionMap,};
-pub use parser::approx as parse_approximation;
-pub use parser::math_expr as parse_math_expression;
-pub use parser::eval as parse_evaluation;
+mod parser;
+mod expression_tree;
+mod modifier;
 
 #[derive(Debug)]
 pub enum Error {
     NotEnoughMemory,
     InvalidSyntax,
+    UndefinedSymbol,
 }
diff --git a/src/parser.rs b/src/parser.rs
index 91c3477..0fd1af0 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -1,98 +1,412 @@
-use core::str::FromStr;
-
-use heapless::Vec;
+use alloc::{boxed::Box, vec::Vec};
 
 use nom::{
-    branch::alt,
-    character::complete::{anychar, one_of},
-    combinator::complete,
-    error::Error,
-    multi::fold_many0,
-    number::complete::float as float_par,
-    IResult,
+    IResult, 
+    sequence::{delimited, tuple,}, 
+    character::complete::{space0, char,}, 
+    combinator::map, 
+    branch::alt, 
+    bytes::complete::take_while1,
+    multi::many0,
 };
 
-use crate::{
-    expression::{Approx, Expression},
-    token::{Operation, Token},
-    expression_map::ExpressionMap,
-};
+use crate::expression_tree::{Expression, Numeric, Atom};
+
+pub fn parse(input: &str) -> Expression {
+    parse_add_sub(input).map_err(|_| "failed to parse").unwrap().1
+}
 
-fn operation(i: &str) -> IResult<&str, Token, Error<&str>> {
-    let (i, t) = one_of("+-*/^")(i)?;
-
-    Ok((
-        i,
-        Token::Op(match t {
-            '+' => Operation::Add,
-            '-' => Operation::Subtract,
-            '/' => Operation::Divide,
-            '*' => Operation::Multiply,
-            '^' => Operation::Power,
-            _ => unreachable!(),
-        }),
-    ))
+fn parse_recursive(input: &str) -> IResult<&str, Expression> {
+    alt((parse_parentheses, parse_numeric))(input)
 }
 
-fn parenthesis(i: &str) -> IResult<&str, Token, Error<&str>> {
-    let (i, t) = one_of("()")(i)?;
-
-    Ok((
-        i,
-        match t {
-            '(' => Token::Paren(true),
-            ')' => Token::Paren(false),
-            _ => unreachable!(),
-        },
-    ))
+fn parse_parentheses(input: &str) -> IResult<&str, Expression> {
+    delimited(
+        space0, 
+        delimited(char('('), parse_add_sub, char(')')), 
+        space0,
+    )(input)
 }
 
-fn divider(i: &str) -> IResult<&str, Token, Error<&str>> {
-    let (i, _) = one_of(",")(i)?;
+fn parse_numeric(input: &str) -> IResult<&str, Expression> {
+    map(
+        delimited(space0, take_while1(is_numeric_value), space0),
+        parse_number
+    )(input)
+}
 
-    Ok((
-        i,
-        Token::Divider,
-    ))
+fn is_numeric_value(c: char) -> bool {
+    c.is_digit(10) || c == '.'
 }
 
-fn variable(i: &str) -> IResult<&str, Token, Error<&str>> {
-    let (i, c) = anychar(i)?;
+fn parse_number(input: &str) -> Expression {
+    Expression::Atom(
+        Atom::Numeric(
+            match input.contains('.') {
+                true => Numeric::Decimal(input.parse::<f32>().unwrap()),
+                false => Numeric::Integer(input.parse::<i32>().unwrap()),
+            }
+        )
+    )
+}
 
-    Ok((i, Token::Var(c)))
+fn parse_unary(input: &str) -> IResult<&str, Expression> {
+    alt((parse_negate, parse_exponents))(input)
 }
 
-fn float(i: &str) -> IResult<&str, Token, Error<&str>> {
-    let (i, f) = float_par(i)?;
-    Ok((i, Token::Number(f)))
+fn parse_exponents(input: &str) -> IResult<&str, Expression> {
+    let (input, num) = parse_recursive(input)?;
+    let (input, ops) = many0(tuple((char('^'), parse_exponents)))(input)?;
+    Ok((input, fold_binary_operators(num, ops)))
 }
 
-fn math_token(i: &str) -> IResult<&str, Token, Error<&str>> {
-    alt((operation, float, parenthesis, divider, variable))(i)
+fn parse_negate(input: &str) -> IResult<&str, Expression> {
+    map(
+        delimited(space0, tuple((char('-'), parse_unary)), space0),
+        parse_unary_op
+    )(input)
 }
 
-pub fn math_expr<const E: usize>(i: &str) -> IResult<&str, Vec<Token, E>, Error<&str>> {
-    fold_many0(complete(math_token), Vec::new, |mut acc, t| {
-        acc.push(t).expect("Not enough memory."); //TODO: make this return an error instead of panicking
-        acc
-    })(i)
+fn parse_mult_div_mod(input: &str) -> IResult<&str, Expression> {
+    let (input, num) = parse_unary(input)?;
+    let (input, ops) = many0(tuple((alt((char('*'), char('/'), char('%'))), parse_unary)))(input)?;
+    Ok((input, fold_binary_operators(num, ops)))
 }
 
-pub fn approx<const E: usize, const N: usize>(
-    input: &str,
-    maps: &Vec<&dyn ExpressionMap<E>, N>,
-) -> Result<Approx, crate::Error> {
-    match Expression::from_str(input.trim()) {
-        Ok(it) => it,
-        Err(_err) => unimplemented!(),
+fn parse_add_sub(input: &str) -> IResult<&str, Expression> {
+    let (input, num) = parse_mult_div_mod(input)?;
+    let (input, ops) = many0(tuple((alt((char('+'), char('-'))), parse_mult_div_mod)))(input)?;
+    Ok((input, fold_binary_operators(num, ops)))
+}
+
+fn parse_unary_op(operator_pair: (char, Expression)) -> Expression {
+    match operator_pair {
+        ('-', expr) => Expression::Negate(Box::new(expr)),
+        ('!', expr) => Expression::Factorial(Box::new(expr)),
+        ('%', expr) => Expression::Percent(Box::new(expr)),
+        _ => panic!("Invalid operator"),
     }
-    .approximate(maps)
 }
 
-pub fn eval<const E: usize>(input: &str) -> Result<Expression<E>, crate::Error> {
-    match Expression::from_str(input.trim()) {
-        Ok(it) => it,
-        Err(_err) => unimplemented!(),
+fn fold_binary_operators(expr: Expression, ops: Vec<(char, Expression)>) -> Expression {
+    ops.into_iter().fold(expr, |acc, val| parse_binary_op(val, acc))
+}
+
+fn parse_binary_op(operator_pair: (char, Expression), expr1: Expression) -> Expression {
+    let (op, expr2) = operator_pair;
+    match op {
+        '+' => Expression::Add(Box::new(expr1), Box::new(expr2)),
+        '-' => Expression::Subtract(Box::new(expr1), Box::new(expr2)),
+        '*' => Expression::Multiply(Box::new(expr1), Box::new(expr2)),
+        '/' => Expression::Divide(Box::new(expr1), Box::new(expr2)),
+        '^' => Expression::Power(Box::new(expr1), Box::new(expr2)),
+        '%' => Expression::Modulus(Box::new(expr1), Box::new(expr2)),
+        _ => panic!("Invalid operator"),
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use alloc::boxed::Box;
+
+    use super::parse;
+    use crate::expression_tree::*;
+
+    #[test]
+    fn test_integer() {
+        assert_eq!(parse("1"), 
+            Expression::Atom(
+                Atom::Numeric(
+                    Numeric::Integer(1)
+                )
+            )
+        );
+        assert_eq!(parse("55"), 
+            Expression::Atom(
+                Atom::Numeric(
+                    Numeric::Integer(55)
+                )
+            )
+        );
+    }
+
+    #[test]
+    fn test_decimal() {
+        assert_eq!(parse("1.0"), 
+            Expression::Atom(
+                Atom::Numeric(
+                    Numeric::Decimal(1.0)
+                )
+            )
+        );
+    }
+
+    #[test]
+    fn test_add() {
+        assert_eq!(parse("1 + 2"),
+            Expression::Add(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(2)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_subtract() {
+        assert_eq!(parse("1 - 2"),
+            Expression::Subtract(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(2)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_add_negative() {
+        assert_eq!(parse("1 + -2"),
+            Expression::Add(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Negate(
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(2)
+                        )
+                    ))
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_modulus() {
+        assert_eq!(parse("1 % 2"),
+            Expression::Modulus(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(2)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_multiply() {
+        assert_eq!(parse("1 * 2"),
+            Expression::Multiply(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(2)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_divide() {
+        assert_eq!(parse("1 / 2"),
+            Expression::Divide(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(2)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_multiply_negative() {
+        assert_eq!(parse("1 * -2"),
+            Expression::Multiply(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Negate(
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(2)
+                        )
+                    ))
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_exponent() {
+        assert_eq!(parse("1 ^ 2"),
+            Expression::Power(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(2)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_parentheses() {
+        assert_eq!(parse("(1 + 2) * 5"),
+            Expression::Multiply(
+                Box::new(Expression::Add(
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(1)
+                        )
+                    )),
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(2)
+                        )
+                    ))
+                )),
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(5)
+                    )
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_spaceless() {
+        assert_eq!(parse("1+2*5"),
+            Expression::Add(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Multiply(
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(2)
+                        )
+                    )),
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(5)
+                        )
+                    ))
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_whitespace() {
+        assert_eq!(parse(" 1    +  2 *   5  "),
+            Expression::Add(
+                Box::new(Expression::Atom(
+                    Atom::Numeric(
+                        Numeric::Integer(1)
+                    )
+                )),
+                Box::new(Expression::Multiply(
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(2)
+                        )
+                    )),
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(5)
+                        )
+                    ))
+                ))
+            )
+        );
+    }
+
+    #[test]
+    fn test_multi_level_expression() {
+        assert_eq!(parse("1 * 2 + 3 / 4 ^ 6 % 7"),
+            Expression::Add(
+                Box::new(Expression::Multiply(
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(1)
+                        )
+                    )),
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(2)
+                        )
+                    ))
+                )),
+                Box::new(Expression::Modulus(
+                    Box::new(Expression::Divide(
+                        Box::new(Expression::Atom(
+                            Atom::Numeric(
+                                Numeric::Integer(3)
+                            )
+                        )),
+                        Box::new(Expression::Power(
+                            Box::new(Expression::Atom(
+                                Atom::Numeric(
+                                    Numeric::Integer(4)
+                                )
+                            )),
+                            Box::new(Expression::Atom(
+                                Atom::Numeric(
+                                    Numeric::Integer(6)
+                                )
+                            ))
+                        ))
+                    )),
+                    Box::new(Expression::Atom(
+                        Atom::Numeric(
+                            Numeric::Integer(7)
+                        )
+                    ))
+                ))
+            )
+        );
     }
-    .evaluate()
 }
\ No newline at end of file
diff --git a/src/token.rs b/src/token.rs
deleted file mode 100644
index 85eacc7..0000000
--- a/src/token.rs
+++ /dev/null
@@ -1,102 +0,0 @@
-use core::{fmt::{Display, Formatter, Result}, cmp::Ordering};
-
-use heapless::String;
-
-#[derive(Debug, Clone)]
-pub enum Token {
-    Number(f32),
-    Op(Operation),
-    Var(char),
-    Paren(bool),
-    Func(String<8>),
-    Divider,
-    Terminator,
-}
-
-impl PartialEq for Token {
-    fn eq(&self, other: &Self) -> bool {
-        match (self, other) {
-            (Token::Number(n1), Token::Number(n2)) => n1 == n2,
-            (Token::Op(op1), Token::Op(op2)) => op1 == op2,
-            (Token::Var(v1), Token::Var(v2)) => v1 == v2,
-            (Token::Paren(p1), Token::Paren(p2)) => p1 == p2,
-            (Token::Func(f1), Token::Func(f2)) => f1 == f2,
-            _ => false,
-        }
-    }
-}
-
-impl Eq for Token {}
-
-impl Display for Token {
-    fn fmt(&self, f: &mut Formatter) -> Result {
-        match self {
-            Token::Number(n) => write!(f, "{}", n),
-            Token::Op(op) => write!(f, "{}", op),
-            Token::Var(var) => write!(f, "{}", var),
-            Token::Paren(true) => write!(f, "("),
-            Token::Paren(false) => write!(f, ")"),
-            Token::Func(func) => write!(f, "{}", func),
-            Token::Divider => write!(f, ","),
-            _ => write!(f, ""),
-        }
-    }
-}
-
-#[derive(Debug, Clone, Copy)]
-pub enum Operation {
-    Add,
-    Subtract,
-    Divide,
-    Multiply,
-    Power,
-}
-
-impl Ord for Operation {
-    fn cmp(&self, other: &Self) -> Ordering {
-        self.precedence().cmp(&other.precedence())
-    }
-}
-
-impl PartialOrd for Operation {
-    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
-impl PartialEq for Operation {
-    fn eq(&self, other: &Self) -> bool {
-        self.precedence() == other.precedence()
-    }
-}
-
-impl Eq for Operation {}
-
-impl Operation {
-    pub fn precedence(&self) -> u8 {
-        match self {
-            Operation::Add | Operation::Subtract => 1,
-            Operation::Multiply | Operation::Divide => 2,
-            Operation::Power => 3,
-        }
-    }
-
-    pub fn right_associative(&self) -> bool {
-        match self {
-            Operation::Power => true,
-            _ => false,
-        }
-    }
-}
-
-impl Display for Operation {
-    fn fmt(&self, f: &mut Formatter) -> Result {
-        match self {
-            Operation::Add => write!(f, "+"),
-            Operation::Subtract => write!(f, "-"),
-            Operation::Divide => write!(f, "/"),
-            Operation::Multiply => write!(f, "*"),
-            Operation::Power => write!(f, "^"),
-        }
-    }
-}


Test patch: