1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
/*! A simple binary expression tree, for parsing and preparing expressions which can be executed on dynamic contents. An expression is built by calling the `push_operator`, `open_par`, `close_par` and `push_atom` functions. It can then be evaluated with the `eval` function which takes as parameters * a function which gives a value to an atom * a function which, given an operator and one or two values, gives a new value * a function deciding whether to shortcut Normal evaluation order is left to right but is modified with parenthesis. # Example : parsing and evaluating boolean expressions Here we parse expressions like `"(A | B) & !(C | D | E)"` and evaluate them. ``` use bet::BeTree; /// The operators in this example are AND, OR, and NOT operating on booleans. /// `And` and `Or` are binary while `Not` is unary. #[derive(Debug, Clone, Copy, PartialEq)] enum BoolOperator { And, Or, Not, } /// simple but realistic example of an expression parsing. /// /// You don't have to parse tokens in advance, you may accumulate /// into atoms with `mutate_or_create_atom`. /// /// For more reliable results on user inputs, you may want to check /// the consistency (or use default operators) during parsing /// with `accept_atom`, `accept_unary_operator`, etc. fn parse(input: &str) -> BeTree<BoolOperator, char> { let mut expr = BeTree::new(); for c in input.chars() { match c { '&' => expr.push_operator(BoolOperator::And), '|' => expr.push_operator(BoolOperator::Or), '!' => expr.push_operator(BoolOperator::Not), ' ' => {}, '(' => expr.open_par(), ')' => expr.close_par(), _ => expr.push_atom(c), } } expr } /// evaluate the expression. /// /// `trues` is the set of chars whose value is true. /// /// If no operation is expected to fail, you may use /// `eval` instead of `eval_faillible`, for a simpler /// API. fn eval(expr: &BeTree<BoolOperator, char>, trues: &[char]) -> bool { expr.eval_faillible( // the function evaluating leafs - here it's simple |c| Ok(trues.contains(c)), // the function applying an operator to one or two values |op, a, b| match (op, b) { (BoolOperator::And, Some(b)) => Ok(a & b), (BoolOperator::Or, Some(b)) => Ok(a | b), (BoolOperator::Not, None) => Ok(!a), _ => { Err("unexpected operation") } }, // when to short-circuit. This is essential when leaf // evaluation is expensive or when the left part guards // for correctness of the right part evaluation |op, a| match (op, a) { (BoolOperator::And, false) => true, (BoolOperator::Or, true) => true, _ => false, }, ).unwrap().unwrap() } // checking complex evaluations with T=true and F=false assert_eq!(eval(&parse("!((T|F)&T)"), &['T']), false); assert_eq!(eval(&parse("!(!((T|F)&(F|T)&T)) & !F & (T | (T|F))"), &['T']), true); // we evaluate an expression with two different sets of values let expr = parse("(A | B) & !(C | D | E)"); assert_eq!(eval(&expr, &['A', 'C', 'E']), false); assert_eq!(eval(&expr, &['A', 'B']), true); // Let's show the left to right evaluation order // and importance of parenthesis assert_eq!(eval(&parse("(A & B)|(C & D)"), &['A', 'B', 'C']), true); assert_eq!(eval(&parse(" A & B | C & D "), &['A', 'B', 'C']), false); ``` */ mod be_tree; #[cfg(test)] mod test_bool; #[cfg(test)] mod test_bool_faillible; pub use { be_tree::BeTree, };