diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.rs | 342 |
1 files changed, 328 insertions, 14 deletions
diff --git a/src/main.rs b/src/main.rs index 0bb1740..a02f2b5 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,18 +1,246 @@ +use std::collections::HashMap; + #[derive(Debug, PartialEq)] enum Token { Number(f64), - Operator(char), + Operator(Operator), Function(String), Variable(String), RightParen, - LeftParen + LeftParen, + Comma +} + +#[derive(Debug, PartialEq)] +enum Operator { + Add, Sub, Mul, Div, Mod, Exp, Chs } #[derive(Debug, PartialEq)] -enum TokenizerError { +enum TokenizeError { TooManyDots(String), ConstantNotFound(String), - BadCharacter(char) + BadCharacter(char), + BadOperator(char) +} + +#[derive(Debug, PartialEq)] +enum ParseError { + MismatchedParens, + MissingLeftParen, + TrailingParen, +} + +#[derive(Debug, PartialEq)] +enum CompileError { + BadOperator(Operator), + BadFunction(String), + BadToken(Token) +} + +#[derive(Debug, PartialEq)] +enum Word { + Push(f64), + PushVar(String), + Add, + Subtract, + Multiply, + Divide, + Modulo, + Power, + Negate, + Sin, + Cos, + Tan, + Sqrt +} + +#[derive(Debug, PartialEq)] +enum ExecuteError { + DivideByZero, + BadVariable(String), + UnimplementedWord(Word), + StackUnderflow +} + +#[derive(Debug, PartialEq)] +enum ExpressionError { + Tokenize(TokenizeError), + Parse(ParseError), + Compile(CompileError), + Execute(ExecuteError) +} + +impl Word { + fn pops(&self) -> usize { + match self { + Word::Push(_) => 0, + Word::PushVar(_)=> 0, + Word::Negate => 1, + Word::Sin => 1, + Word::Cos => 1, + Word::Tan => 1, + Word::Sqrt => 1, + Word::Add => 2, + Word::Subtract => 2, + Word::Multiply => 2, + Word::Divide => 2, + Word::Modulo => 2, + Word::Power => 2, + } + } +} + +impl Operator { + fn precedence(&self) -> u8 { + match self { + Operator::Add | Operator::Sub => 2, + Operator::Mul | Operator::Div | Operator::Mod => 3, + Operator::Exp => 4, + Operator::Chs => 5 + } + } + + fn is_left_associative(&self) -> bool { + match self { + Operator::Add | Operator::Sub | Operator::Mul | Operator::Div | Operator::Mod | Operator::Chs => true, + Operator::Exp => false + } + } + + fn is_right_associative(&self) -> bool { + match self { + Operator::Add | Operator::Sub | Operator::Mul | Operator::Div | Operator::Mod | Operator::Chs => false, + Operator::Exp => true + } + } +} + +impl TryFrom<char> for Operator { + type Error = TokenizeError; + + fn try_from(c: char) -> Result<Self, Self::Error> { + match c { + '+' => Ok(Operator::Add), + '-' => Ok(Operator::Sub), + '*' => Ok(Operator::Mul), + '/' => Ok(Operator::Div), + '^' => Ok(Operator::Exp), + '$' => Ok(Operator::Chs), + _ => Err(TokenizeError::BadOperator(c)) + } + } +} + +impl TryFrom<Token> for Word { + type Error = CompileError; + + fn try_from(t: Token) -> Result<Self, Self::Error> { + match t { + Token::Number(n) => Ok(Word::Push(n)), + Token::Variable(s) => Ok(Word::PushVar(s)), + Token::Operator(o) => match o { + Operator::Add => Ok(Word::Add), + Operator::Sub => Ok(Word::Subtract), + Operator::Mul => Ok(Word::Multiply), + Operator::Div => Ok(Word::Divide), + Operator::Mod => Ok(Word::Modulo), + Operator::Exp => Ok(Word::Power), + Operator::Chs => Ok(Word::Negate) + // _ => Err(CompileError::BadOperator(o)) + }, + Token::Function(s) => match s.as_str() { + "sin" => Ok(Word::Sin), + "cos" => Ok(Word::Cos), + "tan" => Ok(Word::Tan), + _ => Err(CompileError::BadFunction(s)) + }, + _ => Err(CompileError::BadToken(t)) + } + } +} + +impl From<TokenizeError> for ExpressionError { + fn from(e: TokenizeError) -> Self { + ExpressionError::Tokenize(e) + } +} + +impl From<ParseError> for ExpressionError { + fn from(e: ParseError) -> Self { + ExpressionError::Parse(e) + } +} + +impl From<CompileError> for ExpressionError { + fn from(e: CompileError) -> Self { + ExpressionError::Compile(e) + } +} + +impl From<ExecuteError> for ExpressionError { + fn from(e: ExecuteError) -> Self { + ExpressionError::Execute(e) + } +} + +struct Expression { + words: Vec<Word> +} + +impl Expression { + pub fn try_new(expression: &str) -> Result<Expression, ExpressionError> { + let tokens = tokenize(expression)?; + let parsed = parse(tokens)?; + let words = compile(parsed)?; + Ok(Self { words }) + } + + pub fn eval(&self, vars: &[(&str, f64)]) -> Result<f64, ExpressionError> { + let mut stack: Vec<f64> = Vec::new(); + + for word in &self.words { + let mut a: f64 = 0.0; + let mut b: f64 = 0.0; + + match word.pops() { + 1 => { + a = stack.pop().ok_or(ExecuteError::StackUnderflow)?; + } + + 2 => { + b = stack.pop().ok_or(ExecuteError::StackUnderflow)?; + a = stack.pop().ok_or(ExecuteError::StackUnderflow)?; + } + + _ => {} + } + + let y = match word { + Word::Push(n) => *n, + Word::PushVar(v) => vars.iter() + .find(|(k, _)| *k == v) + .map(|(_, a)| *a) + .ok_or(ExecuteError::BadVariable(v.to_string()))?, + Word::Add => a + b, + Word::Subtract => a - b, + Word::Multiply => a * b, + Word::Divide => a / b, + Word::Modulo => a % b, + Word::Power => a.powf(b), + Word::Negate => -a, + Word::Sin => a.sin(), + Word::Cos => a.cos(), + Word::Tan => a.tan(), + Word::Sqrt => a.sqrt(), + _ => 0.0 + }; + + stack.push(y); + } + + Ok(stack.pop().unwrap()) + } } fn str_to_const(s: &str) -> Option<f64> { @@ -23,7 +251,7 @@ fn str_to_const(s: &str) -> Option<f64> { } } -fn tokenize(input: &str) -> Result<Vec<Token>, TokenizerError> { +fn tokenize(input: &str) -> Result<Vec<Token>, TokenizeError> { let mut tokens = Vec::new(); let mut chars = input.chars().peekable(); @@ -38,7 +266,7 @@ fn tokenize(input: &str) -> Result<Vec<Token>, TokenizerError> { chars.next(); has_dot |= c == '.'; } else if c == '.' && has_dot { - return Err(TokenizerError::TooManyDots(num)); + return Err(TokenizeError::TooManyDots(num)); } else { break; } @@ -48,7 +276,16 @@ fn tokenize(input: &str) -> Result<Vec<Token>, TokenizerError> { '+' | '-' | '*' | '/' | '%' | '^' => { chars.next(); - tokens.push(Token::Operator(ch)); + if (ch == '+' || ch == '-') && + (tokens.len() == 0 || + (tokens.len() > 1 && matches!(tokens.last(), Some(Token::Operator(_))))) { + if ch == '-' { + /* change sign */ + tokens.push(Token::Operator(Operator::Chs)); + } + } else { + tokens.push(Token::Operator(Operator::try_from(ch)?)); + } } 'a'..='z' | '_' => { @@ -83,11 +320,11 @@ fn tokenize(input: &str) -> Result<Vec<Token>, TokenizerError> { s.push(c); chars.next(); } - let n = str_to_const(&s).ok_or(TokenizerError::ConstantNotFound(s))?; + let n = str_to_const(&s).ok_or(TokenizeError::ConstantNotFound(s))?; tokens.push(Token::Number(n)); } - c if c.is_whitespace() || c == ',' => { + c if c.is_whitespace() => { while let Some(&c) = chars.peek() { if c.is_whitespace() { chars.next(); @@ -97,18 +334,23 @@ fn tokenize(input: &str) -> Result<Vec<Token>, TokenizerError> { } } - '(' => { + ',' => { chars.next(); - tokens.push(Token::RightParen); + tokens.push(Token::Comma); } ')' => { chars.next(); + tokens.push(Token::RightParen); + } + + '(' => { + chars.next(); tokens.push(Token::LeftParen); } _ => { - return Err(TokenizerError::BadCharacter(ch)); + return Err(TokenizeError::BadCharacter(ch)); } } } @@ -116,9 +358,81 @@ fn tokenize(input: &str) -> Result<Vec<Token>, TokenizerError> { Ok(tokens) } +fn parse(tokens: Vec<Token>) -> Result<Vec<Token>, ParseError> { + let mut output: Vec<Token> = Vec::new(); + let mut operators: Vec<Token> = Vec::new(); + + for token in tokens { + match token { + Token::Number(_) | Token::Variable(_) => { + output.push(token); + } + + Token::Function(_) => { + operators.push(token); + } + + Token::Operator(o1) => { + while let Some(Token::Operator(o2)) = operators.last() && + ((o2.precedence() > o1.precedence()) || + ((o1.precedence() == o2.precedence()) && o1.is_left_associative())) { + output.push(operators.pop().unwrap()); + } + operators.push(Token::Operator(o1)); + } + + Token::Comma => { + while !matches!(operators.last(), Some(&Token::LeftParen)) { + output.push(operators.pop().unwrap()); + } + } + + Token::LeftParen => { + operators.push(token); + } + + Token::RightParen => { + while let Some(top) = operators.last() { + if matches!(top, Token::LeftParen) { + break; + } + output.push(operators.pop().unwrap()); + } + + if !matches!(operators.pop(), Some(Token::LeftParen)) { + return Err(ParseError::MismatchedParens); + } + } + } + } + + while let Some(t) = operators.pop() { + if t == Token::LeftParen { + return Err(ParseError::TrailingParen); + } + output.push(t); + } + + Ok(output) +} + +fn compile(tokens: Vec<Token>) -> Result<Vec<Word>, CompileError> { + tokens.into_iter().map(Word::try_from).collect() +} + fn main() { - let input = "x + 4 * (3 - sin((y+PI)) / 2.123)^2"; - println!("{}", input); + //let input = "-x + 4 * -(3 - sin((y+PI)) / 2.123)^2"; + /*println!("{}", input); let tokens = tokenize(input).unwrap(); println!("{:#?}", tokens); + let program = parse(tokens).unwrap(); + println!("{:#?}", program); + let executable = compile(program).unwrap(); + println!("{:#?}", executable);*/ + + let input = "x * sin(PI/2)"; + let expression = Expression::try_new(input).unwrap(); + let vars = [("x", 3.0)]; + println!("{:#?}", expression.words); + println!("{}", expression.eval(&vars).unwrap()); } |