hw(3/Rust): Add half-working solution to simple parser

3 files changed, 324 insertions, 0 deletions

diff --git a/Year 4/Programming with Rust/hw03/Cargo.lock b/Year 4/Programming with Rust/hw03/Cargo.lock
new file mode 100644
index 0000000..c3f708d
--- /dev/null
+++ b/Year 4/Programming with Rust/hw03/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "hw03"
+version = "0.1.0"
diff --git a/Year 4/Programming with Rust/hw03/Cargo.toml b/Year 4/Programming with Rust/hw03/Cargo.toml
new file mode 100644
index 0000000..5bb81d6
--- /dev/null
+++ b/Year 4/Programming with Rust/hw03/Cargo.toml
@@ -0,0 +1,6 @@
+[package]
+name = "hw03"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
diff --git a/Year 4/Programming with Rust/hw03/src/main.rs b/Year 4/Programming with Rust/hw03/src/main.rs
new file mode 100644
index 0000000..c533e4e
--- /dev/null
+++ b/Year 4/Programming with Rust/hw03/src/main.rs
@@ -0,0 +1,311 @@
+#![allow(warnings)]
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum Expr {
+    Atom(char),
+    Not(Box<Expr>),
+    And(Vec<Expr>),
+    Or(Vec<Expr>),
+}
+
+macro_rules! expr {
+    (atom ( $c:literal ) ) => {
+        Expr::Atom($c)
+    };
+    (not ( $name:tt $e:tt ) ) => {
+        Expr::Not(Box::new( expr!($name$e) ))
+    };
+    (and ( $($name:tt $e:tt),* ) ) => {
+        Expr::And(vec![$( expr!($name$e) ),*])
+    };
+    (or ( $($name:tt $e:tt),* ) ) => {
+        Expr::Or(vec![$( expr!($name$e) ),*])
+    };
+}
+
+#[derive(Debug, PartialEq, Eq)]
+pub enum ParseError {
+    UnexpectedExpr,
+    UnexpectedUnaryOp,
+    UnexpectedBinOp,
+    UnexpectedParen,
+    UnexpectedEnd,
+}
+
+/// Парсър за прост израз, който не съдържа скоби
+pub struct SimpleExprParser {
+    top_atom: Option<Expr>,
+    top_op: Option<Expr>,
+    top_op_char: char,
+    bot_op: Option<Expr>,
+    bot_op_char: char,
+}
+
+impl SimpleExprParser {
+    pub fn new() -> SimpleExprParser {
+        SimpleExprParser {
+            top_atom: None,
+            top_op: None,
+            top_op_char: '_',
+            bot_op: None,
+            bot_op_char: '_',
+        }
+    }
+
+    /// Приема атом.
+    ///
+    /// `c` ще бъде валиден символ за атом.
+    /// В противен случай можете да panic-нете (няма да се тества)
+    pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
+        if (self.top_op_char == '!' || self.top_op_char == '_') && self.top_atom.is_some() {
+            return Err(ParseError::UnexpectedExpr);
+        }
+
+        if self.top_op_char == '!' {
+            let Expr::Not(ptr) = self.top_op.as_mut().unwrap() else { unreachable!() };
+            *(*ptr) = Expr::Atom(c);
+
+            if self.bot_op.is_some() {
+                match self.bot_op.as_mut().unwrap() {
+                    Expr::And(vec) | Expr::Or(vec) => vec.push(self.top_op.take().unwrap()),
+                    Expr::Not(ptr) => {
+                        let mut ptr = ptr;
+                        loop {
+                            if let Expr::Atom(_) = **ptr {
+                                **ptr = self.top_op.take().unwrap();
+                                break;
+                            }
+                            match ptr.as_mut() {
+                                Expr::Not(ptro) => ptr = ptro,
+                                _ => unreachable!(),
+                            }
+                        }
+                    },
+                    _ => unreachable!(),
+                }
+                self.top_op = self.bot_op.take();
+                self.top_op_char = self.bot_op_char;
+            }
+        }
+        else if self.top_op.is_some() {
+            match self.top_op.as_mut().unwrap() {
+                Expr::And(vec) | Expr::Or(vec) => vec.push(Expr::Atom(c)),
+                _ => unreachable!(),
+            }
+        }
+
+        self.top_atom = Some(Expr::Atom(c));
+        Ok(())
+    }
+
+    fn take_single_expr(&mut self) -> Expr {
+        if self.bot_op.is_some() {
+            self.bot_op_char = '_';
+            self.bot_op.take().unwrap()
+        }
+        else {
+            self.top_atom.take().unwrap()
+        }
+    }
+
+    /// Приема символ за операция.
+    ///
+    /// `op` ще бъде едно от '&', '|', '!'.
+    /// В противен случай можете да panic-нете (няма да се тества)
+    pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
+        if op != '!' && self.top_atom.is_none() {
+            return Err(ParseError::UnexpectedBinOp);
+        }
+        if self.top_op_char == op && self.top_atom.is_some() {
+            return Ok(());
+        }
+
+        if self.bot_op.is_some() {
+            match self.bot_op.as_mut().unwrap() {
+                Expr::And(vec) | Expr::Or(vec) => vec.push(self.top_op.take().unwrap()),
+                Expr::Not(ptr) => *(*ptr) = self.top_op.take().unwrap(),
+                _ => unreachable!(),
+            }
+        }
+        else {
+            self.bot_op = self.top_op.take();
+            self.bot_op_char = self.top_op_char;
+        }
+
+        self.top_op = Some(match op {
+            '&' => Expr::And(vec![self.take_single_expr()]),
+            '|' => Expr::Or(vec![self.take_single_expr()]),
+            '!' => Expr::Not(Box::new(Expr::Atom('_'))),
+            _ => unreachable!(),
+        });
+        self.top_op_char = op;
+        self.top_atom = None;
+        Ok(())
+    }
+
+    /// Завършва парсването и връща построения израз.
+    pub fn finish(self) -> Result<Expr, ParseError> {
+        if self.bot_op.is_some() || self.top_atom.is_none() {
+            Err(ParseError::UnexpectedEnd)
+        }
+        else {
+            self.top_op.or(self.top_atom).ok_or(ParseError::UnexpectedEnd)
+        }
+    }
+}
+
+macro_rules! test_sep {
+    ( $( $call:tt $args:tt ).+ , $acall:tt $aargs:tt ) => {
+        {
+            let mut sep = SimpleExprParser::new();
+            $(
+                let _ = sep.$call$args.unwrap();
+            )+
+            let res = sep.finish().unwrap();
+            assert_eq!(res, expr!($acall$aargs));
+        }
+    };
+    ( ! $( $call:tt $args:tt ).+ ) => {
+        'fails: {
+            let mut sep = SimpleExprParser::new();
+            $(
+                if sep.$call$args.is_err() {
+                    break 'fails;
+                }
+            )+
+            sep.finish().expect_err("Invalid expression was passed, but it was successfully parsed");
+        }
+    };
+}
+
+#[test]
+fn simple_parser() {
+    test_sep!(push_atom('A'), atom('A'));
+    test_sep!(push_op('!').push_atom('A'), not(atom('A')));
+    test_sep!(push_op('!').push_op('!').push_atom('A'), not(not(atom('A'))));
+    test_sep!(push_op('!').push_op('!').push_op('!').push_atom('A'), not(not(not(atom('A')))));
+    test_sep!(push_op('!').push_op('!').push_op('!').push_atom('A').push_op('&').push_op('!').push_op('!').push_op('!').push_atom('B'), and(not(not(not(atom('A')))), not(not(not(atom('B'))))));
+    test_sep!(push_atom('A').push_op('&').push_atom('B'), and(atom('A'), atom('B')));
+    test_sep!(push_atom('A').push_op('|').push_atom('B'), or(atom('A'), atom('B')));
+    test_sep!(push_atom('A').push_op('&').push_atom('B').push_op('&').push_atom('C'), and(atom('A'), atom('B'), atom('C')));
+    test_sep!(push_atom('A').push_op('|').push_atom('B').push_op('|').push_atom('C'), or(atom('A'), atom('B'), atom('C')));
+    test_sep!(push_op('!').push_atom('A').push_op('&').push_atom('B').push_op('&').push_op('!').push_atom('C'), and(not(atom('A')), atom('B'), not(atom('C'))));
+    test_sep!(push_op('!').push_atom('A').push_op('|').push_atom('B').push_op('|').push_op('!').push_atom('C'), or(not(atom('A')), atom('B'), not(atom('C'))));
+
+    test_sep!(!push_op('!'));
+    test_sep!(!push_op('&'));
+    test_sep!(!push_op('|'));
+    test_sep!(!push_atom('A').push_atom('B'));
+    test_sep!(!push_op('!').push_op('!'));
+    test_sep!(!push_op('!').push_op('&'));
+    test_sep!(!push_op('!').push_op('|'));
+    test_sep!(!push_op('&').push_op('&'));
+    test_sep!(!push_op('|').push_op('|'));
+    test_sep!(!push_op('&').push_op('|'));
+    test_sep!(!push_op('|').push_op('&'));
+    test_sep!(!push_op('&').push_op('|'));
+
+    test_sep!(!push_op('!').push_atom('A').push_atom('B'));
+    test_sep!(!push_op('&').push_atom('A').push_atom('B'));
+    test_sep!(!push_op('|').push_atom('A').push_atom('B'));
+    test_sep!(!push_atom('A').push_op('&'));
+    test_sep!(!push_atom('A').push_op('|'));
+}
+
+/// Парсър за пълния израз
+pub struct ExprParser {
+    // ...
+}
+
+impl ExprParser {
+    pub fn new() -> ExprParser {
+        todo!();
+    }
+
+    /// Приема атом.
+    ///
+    /// `c` ще бъде валиден символ за атом.
+    /// В противен случай можете да panic-нете (няма да се тества)
+    pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
+        todo!()
+    }
+
+    /// Приема символ за операция.
+    ///
+    /// `op` ще бъде едно от '&', '|', '!'.
+    /// В противен случай можете да panic-нете (няма да се тества)
+    pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
+        todo!()
+    }
+
+    /// Приема отваряща скоба.
+    pub fn open_paren(&mut self) -> Result<(), ParseError> {
+        todo!()
+    }
+
+    /// Приема затваряща скоба.
+    pub fn close_paren(&mut self) -> Result<(), ParseError> {
+        todo!()
+    }
+
+    /// Завършва парсването и връща построения израз.
+    pub fn finish(self) -> Result<Expr, ParseError> {
+        todo!()
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum Value {
+    True,
+    False,
+    Expr(Expr),
+}
+
+pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
+    todo!()
+}
+
+fn main() {
+    println!("Hello, world!");
+}
+
+#[test]
+fn expr_macro() {
+    assert_eq!(
+        expr!(atom('m')),
+        Expr::Atom('m')
+    );
+    assert_eq!(
+        expr!(not(atom('a'))),
+        Expr::Not(Box::new(Expr::Atom('a')))
+    );
+    assert_eq!(
+        expr!(and(atom('a'), not(atom('b')), atom('c'))),
+        Expr::And(vec![
+            Expr::Atom('a'),
+            Expr::Not(Box::new(Expr::Atom('b'))),
+            Expr::Atom('c'),
+        ])
+    );
+    assert_eq!(
+        expr!(or(atom('a'), not(atom('b')), atom('c'))),
+        Expr::Or(vec![
+            Expr::Atom('a'),
+            Expr::Not(Box::new(Expr::Atom('b'))),
+            Expr::Atom('c'),
+        ])
+    );
+    assert_eq!(
+        expr!(or(and(atom('A'), not(atom('B'))), not(and(atom('C'), atom('D'))))),
+        Expr::Or(vec![
+            Expr::And(vec![
+                Expr::Atom('A'),
+                Expr::Not(Box::new(Expr::Atom('B'))),
+            ]),
+            Expr::Not(Box::new(Expr::And(vec![
+                    Expr::Atom('C'),
+                    Expr::Atom('D'),
+            ]))),
+        ])
+    );
+}