boolean_logic/
evaluator.rs

1use std::collections::{HashSet, VecDeque};
2use indexmap::{IndexMap, IndexSet};
3use crate::{evaluator_result::EvaluatorResult, tokenizer::{Token, Tokens}};
4use std::fmt;
5
6
7#[derive(Debug)]
8pub struct EvaluatorError {
9    message: String,
10}
11impl fmt::Display for EvaluatorError {
12    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
13        write!(f, "{}", self.message)
14    }
15}
16
17pub struct Evaluator {
18   tokens: Tokens,
19   idents: HashSet<char>
20}
21
22impl Evaluator {
23    pub fn new(tokens: Tokens)-> Result<Self,EvaluatorError> {
24        //do some validation
25        let mut tokens = tokens;
26        fn check_enclosing(tkns: &[Token], left: Token, right: Token)-> Result<(),EvaluatorError> {
27            let mut p_count = 0;
28            for t in tkns {
29                if t == &left {
30                    p_count +=1;
31                }else if t == &right {
32                    p_count -=1;
33                }
34                
35                if p_count < 0 {
36                    break;
37                }
38            }
39            if p_count != 0 {
40                return  Err(EvaluatorError { message: "mis-match parentheses".into() });
41            }
42            Ok(())
43        }
44        let tkns: &[Token] = &tokens;
45        if tkns.len() == 0 {
46            return  Err(EvaluatorError { message: "Empty expression.".into() });
47        }
48
49        check_enclosing(tkns, Token::OpenParen, Token::CloseParen)?;
50        check_enclosing(tkns, Token::OpenBracket, Token::CloseBracket)?;
51        check_enclosing(tkns, Token::OpenCurlyBrace, Token::CloseCurlyBrace)?;
52        
53        tokens.enclose(Token::OpenParen, Token::CloseParen);
54
55        let idents: HashSet<char> = tokens.iter().filter_map(|t| {
56            match t {
57                Token::Ident(chr)=> {
58                    return Some(*chr);
59                }
60                _ => None
61            }
62        }).collect();
63        Ok(Evaluator { tokens , idents})
64    }
65}
66
67impl Evaluator {
68    pub fn evaluate(&self, values: &IndexMap<char,bool>) -> Result<IndexMap<String, bool>, EvaluatorError> {
69        //validate values
70        if !self.idents.iter().all(|x| values.contains_key(x)) {
71            return Err(EvaluatorError{message: "Please provide value for all idents.".into()});
72        }
73        let mut operators_stack = VecDeque::<Token>::new();
74        let mut operands_stack = VecDeque::<(Option<String>,Token)>::new();
75        let mut result: IndexMap<String,bool> = IndexMap::new();
76        let tokens: &[Token] = &self.tokens;
77        for token in tokens {
78            match token {
79                Token::Ident(chr) => {
80                     let v = values.get(chr).unwrap();
81                     let v = if *v {
82                        Token::True
83                    }else {
84                        Token::False
85                    };
86                    operands_stack.push_front((Some(chr.to_string()),v));
87                },
88                Token::OpenParen | Token::OpenBracket | Token::OpenCurlyBrace => {
89                    operators_stack.push_front(token.clone());
90                },
91                Token::CloseParen | Token::CloseBracket | Token::CloseCurlyBrace => {
92                  while let Some(op) = operators_stack.pop_front() {
93                      if op == Token::OpenParen || 
94                         op == Token::OpenBracket || 
95                         op == Token::OpenCurlyBrace {break;}
96                      Self::evaluate_operator(op, &mut operands_stack);
97                      let res = operands_stack.front().unwrap().clone();
98                      if let Some(name) = res.0 {
99                        result.insert(name, res.1.into());
100                      }
101                  }  
102                },
103                Token::False => operands_stack.push_front((Some("false".into()),token.clone())),
104                Token::True => operands_stack.push_front((Some("true".into()),token.clone())),
105                _ => {
106                    while operators_stack.len() > 0 && (get_priority(&operators_stack.front().unwrap())<=get_priority(&token)) {
107                        Self::evaluate_operator(operators_stack.pop_front().unwrap(),&mut operands_stack);
108                        let res = operands_stack.front().unwrap().clone();
109                        if let Some(name) = res.0 {
110                            result.insert(name, res.1.into());
111                        }
112                    }
113                    operators_stack.push_front(token.clone());
114                }
115            }
116        }
117        Ok(result)
118    }
119    fn evaluate_operator(operator: Token, operands_stack: &mut VecDeque::<(Option<String>,Token)>){
120        
121        let op_symbol: String;
122        let ev_result: Token;
123        let opnd_count = get_operands_count(&operator);
124        let opnd1_ =  operands_stack.pop_front().unwrap();
125        let opnd1: bool = opnd1_.1.into();
126        let mut opnd2_: (Option<String>, Token) = (None,Token::False);
127        let mut opnd2 = false;
128        if opnd_count == 2 {
129            opnd2_ = operands_stack.pop_front().unwrap();
130            opnd2 = opnd2_.1.into();
131        }
132        
133        match operator {
134            Token::Not(symbol) => {
135                ev_result = Token::from(!opnd1);
136                op_symbol = symbol.into();
137            },
138            Token::Implication(symbol) =>  {
139                let opnd = if !opnd2 {
140                    true
141                }else {
142                    opnd1
143                };
144                ev_result = Token::from(opnd);
145                op_symbol = symbol.into();
146            },
147            Token::Biconditional(symbol) =>  {
148                let opnd = if (opnd1 && opnd2) || (!opnd1 && !opnd2) {
149                    true
150                }else {
151                    false
152                };
153                ev_result = Token::from(opnd);
154                op_symbol = symbol.into();
155            },
156            Token::And(symbol) => {
157                let opnd = opnd1 && opnd2;
158                ev_result = Token::from(opnd);
159                op_symbol = symbol.into();
160            },
161            Token::Or(symbol) => {
162                let opnd = opnd1 || opnd2;
163                ev_result = Token::from(opnd);
164                op_symbol = symbol.into();
165            },
166            Token::XOr(symbol) => {
167                let opnd = (opnd1 && !opnd2) || (!opnd1 && opnd2);
168                ev_result = Token::from(opnd);
169                op_symbol = symbol.into();
170            },
171            Token::Equals(symbol) => {
172                let opnd = (opnd1 && opnd2) || (!opnd1 && !opnd2);
173                ev_result = Token::from(opnd);
174                op_symbol = symbol.to_string();
175            },
176            Token::NotEquals(symbol) => {
177                let opnd = (!opnd1 && opnd2) || (opnd1 && !opnd2);
178                ev_result = Token::from(opnd);
179                op_symbol = symbol.into();
180            },
181            _ => todo!(),
182        }
183        
184        if opnd_count == 2 {
185            if let (Some(nm1),Some(nm2)) = (opnd1_.0,opnd2_.0) {
186                let name = format!("({} {} {})",nm2,op_symbol,nm1);
187                operands_stack.push_front((Some(name),ev_result));
188            }else {
189                operands_stack.push_front((Some("?".into()),ev_result));
190            }
191        }else {
192            if let Some(nm) = opnd1_.0 {
193                let name = format!("{}{}",op_symbol,nm);
194                operands_stack.push_front((Some(name),ev_result));
195            }else {
196                operands_stack.push_front((Some("?".into()),ev_result));
197            }
198        }
199    }
200
201    pub fn evaluate_all(&self)-> Result<EvaluatorResult,EvaluatorError> {
202        let mut result: Vec<IndexMap<String, bool>> = Vec::new();
203        let tokens: &[Token] = &self.tokens;
204        let operands: Vec<char> = tokens.iter().filter_map(|t| {
205            match t {
206                Token::Ident(chr)=> {
207                    return Some(*chr);
208                }
209                _ => None
210            }
211        }).collect::<IndexSet<_>>()
212        .into_iter()
213        .collect();
214        let n = operands.len();
215        let rows: u64 = 1 << n;//2^n
216        for i in 0..rows {
217            let mut row: IndexMap<char,bool> = IndexMap::new();
218            for j in (0..n).rev() {
219                let v = ((i >> j) & 1) != 0;
220                row.insert(operands[n - j - 1], !v);
221            }
222            if let Ok(mut eval) = self.evaluate(&row){
223                for r in row.iter().rev() {
224                    eval.insert_before(0, r.0.to_string(), *r.1);
225                }
226                result.push(eval);
227            }
228        }
229        Ok(EvaluatorResult { result })
230    }
231}
232
233
234fn get_priority(op_token: &Token)-> usize {
235    match op_token {
236        Token::Ident(_) => return usize::MAX,
237        Token::OpenParen | Token::CloseParen |
238        Token::OpenBracket | Token::CloseBracket |
239        Token::OpenCurlyBrace | Token::CloseCurlyBrace => return usize::MAX,
240        Token::Not(_) => return  0,
241        Token::Implication(_) => 3,
242        Token::Biconditional(_) => 3,
243        Token::And(_) => return  1,
244        Token::Or(_) => return  2,
245        Token::XOr(_) => return  2,
246        Token::Equals(_) => 4,
247        Token::NotEquals(_) => 5,
248        Token::False => return usize::MAX,
249        Token::True => return usize::MAX,
250    }
251}
252fn get_operands_count(op_token: &Token)-> usize {
253    match op_token {
254        Token::Ident(_) => return 0,
255        Token::OpenParen | Token::CloseParen |
256        Token::OpenBracket | Token::CloseBracket |
257        Token::OpenCurlyBrace | Token::CloseCurlyBrace => return 0,
258        Token::Not(_) => return  1,
259        Token::Implication(_) => 2,
260        Token::Biconditional(_) => 2,
261        Token::And(_) => return  2,
262        Token::Or(_) => return  2,
263        Token::XOr(_) => return  2,
264        Token::Equals(_) => 2,
265        Token::NotEquals(_) => 2,
266        Token::False => return 0,
267        Token::True => return 0,
268    }
269}
270
271#[cfg(test)]
272mod tests {
273    use crate::tokenizer::Tokens;
274
275    use super::*;
276
277    #[test]
278    fn not() {
279        let symbols = ["not", "¬", "!", "∼"];
280        for s in symbols {
281            let expr = format!("{} a",s);
282            let tokens = Tokens::from_text(&expr);
283            let evaluator = Evaluator::new(tokens).unwrap();
284            let mut values = IndexMap::<char,bool>::new();
285            values.insert('a', true);
286            let result = evaluator.evaluate(&values).unwrap();
287            assert_eq!(
288                result.get("¬a").unwrap(),&false
289            );
290        }
291        
292    }
293
294    fn check(evaluator: &Evaluator, a: bool, b:bool, expect: bool, expr: &str) {
295        let mut values = IndexMap::<char,bool>::new();
296        values.insert('a', a);
297        values.insert('b', b);
298        let result = evaluator.evaluate(&values).unwrap();
299        assert_eq!(
300            result.get(expr).unwrap(),&expect
301        );
302    }
303
304    #[test]
305    fn and() {
306        let symbols = ["and", "&", "&&", "∧"];
307        for s in symbols {
308            let expr = format!("a {} b",s);
309            let tokens = Tokens::from_text(&expr);
310            let evaluator = Evaluator::new(tokens).unwrap();
311            let expr = "(a ∧ b)";
312            check(&evaluator, true, true, true,&expr);
313            check(&evaluator, true, false, false,&expr);
314            check(&evaluator, false, true, false,&expr);
315            check(&evaluator, false, false, false,&expr);
316        }
317    }
318
319    #[test]
320    fn or() {
321        let symbols = ["or", "|", "||", "∨"];
322        for s in symbols {
323            let expr = format!("a {} b",s);
324            let tokens = Tokens::from_text(&expr);
325            let evaluator = Evaluator::new(tokens).unwrap();
326            let expr = "(a ∨ b)";
327            check(&evaluator, true, true, true,&expr);
328            check(&evaluator, true, false, true,&expr);
329            check(&evaluator, false, true, true,&expr);
330            check(&evaluator, false, false, false,&expr);
331        }
332    }
333    #[test]
334    fn xor() {
335        let symbols = ["xor", "⊕"];
336        for s in symbols {
337            let expr = format!("a {} b",s);
338            let tokens = Tokens::from_text(&expr);
339            let evaluator = Evaluator::new(tokens).unwrap();
340            let expr = "(a ⊕ b)";
341            check(&evaluator, true, true, false,&expr);
342            check(&evaluator, true, false, true,&expr);
343            check(&evaluator, false, true, true,&expr);
344            check(&evaluator, false, false, false,&expr);
345        }
346    }
347    #[test]
348    fn implication() {
349        let symbols = ["->", "=>", "⇒", "→", "⊃"];
350        for s in symbols {
351            let expr = format!("a {} b",s);
352            let tokens = Tokens::from_text(&expr);
353            let evaluator = Evaluator::new(tokens).unwrap();
354            let expr = "(a → b)";
355            check(&evaluator, true, true, true,&expr);
356            check(&evaluator, true, false, false,&expr);
357            check(&evaluator, false, true, true,&expr);
358            check(&evaluator, false, false, true,&expr);
359        }
360        
361    }
362
363    #[test]
364    fn biconditional() {
365        let symbols = ["<->", "<=>", "⇔", "↔", "iff", "xnor"];
366        for s in symbols {
367            let expr = format!("a {} b",s);
368            let tokens = Tokens::from_text(&expr);
369            let evaluator = Evaluator::new(tokens).unwrap();
370            let expr = "(a ↔ b)";
371            check(&evaluator, true, true, true,&expr);
372            check(&evaluator, true, false, false,&expr);
373            check(&evaluator, false, true, false,&expr);
374            check(&evaluator, false, false, true,&expr);
375        }
376    }
377}
boolean_logic/evaluator.rs

boolean_logic/
evaluator.rs
