Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Логически изрази

Предадени решения

Краен срок:
22.12.2024 23:59
Точки:
20

Срокът за предаване на решения е отминал

use solution::*;
macro_rules! timeout {
($time:expr, $body:block) => {
use std::panic::catch_unwind;
let (sender, receiver) = std::sync::mpsc::channel();
std::thread::spawn(move || {
if let Err(e) = catch_unwind(|| $body) {
sender.send(Err(e)).unwrap();
return;
}
match sender.send(Ok(())) {
Ok(()) => {}, // everything good
Err(_) => {}, // we have been released, don't panic
}
});
if let Err(any) = receiver.recv_timeout(std::time::Duration::from_millis($time)).unwrap() {
panic!("{}", any.downcast_ref::<String>().unwrap());
}
}
}
macro_rules! expr {
( atom($c:expr) ) => {
Expr::Atom($c)
};
( not( $tag:ident ( $($e:tt)* ) ) ) => {
Expr::Not(Box::new(expr!( $tag($( $e )*) )))
};
( and( $( $tag:ident ( $($e:tt)* ) ),* ) ) => {
Expr::And(vec![$( expr!($tag($( $e )*)) ),*])
};
( or( $( $tag:ident ( $($e:tt)* ) ),* ) ) => {
Expr::Or(vec![$( expr!($tag($( $e )*)) ),*])
};
}
// помощна функция
fn feed_simple(parser: &mut SimpleExprParser, text: &str) -> Result<(), ParseError> {
for c in text.chars() {
match c {
' ' => {}
'&' | '|' | '!' => parser.push_op(c)?,
_ => parser.push_atom(c)?,
}
}
Ok(())
}
// помощна функция
fn feed_full(parser: &mut ExprParser, text: &str) -> Result<(), ParseError> {
for c in text.chars() {
match c {
' ' => {}
'&' | '|' | '!' => parser.push_op(c)?,
'(' => parser.open_paren()?,
')' => parser.close_paren()?,
_ => parser.push_atom(c)?,
}
}
Ok(())
}
#[test]
fn test_parser_atom() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(atom('A')));
});
}
#[test]
fn test_parser_and_or() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A & B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(and(atom('A'), atom('B'))));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A | B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(or(atom('A'), atom('B'))));
});
}
#[test]
fn test_parser_not() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "!B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(not(atom('B'))));
});
}
#[test]
fn test_parser_expr_and_not() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A & !B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(and(atom('A'), not(atom('B')))));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "!A | B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(or(not(atom('A')), atom('B'))));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "!A & !B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(and(not(atom('A')), not(atom('B')))));
});
}
#[test]
fn test_parser_multiple_atoms_same_op() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A & B & C").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(and(atom('A'), atom('B'), atom('C'))));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "X | Y | Z | W").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(or(atom('X'), atom('Y'), atom('Z'), atom('W')))
);
});
}
#[test]
fn test_parser_multiple_not() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "!!!B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(not(not(not(atom('B'))))));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A | !!B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(or(atom('A'), not(not(atom('B'))))));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "!!A | B").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(or(not(not(atom('A'))), atom('B'))));
});
}
#[test]
fn test_parser_alternating_ops() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A & B | C & D").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(and(or(and(atom('A'), atom('B')), atom('C')), atom('D')))
);
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A | B & C | D").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(or(and(or(atom('A'), atom('B')), atom('C')), atom('D')))
);
});
}
#[test]
fn test_paren_around_expr() {
timeout!(1000, {
let mut parser = ExprParser::new();
feed_full(&mut parser, "(A)").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(atom('A')));
let mut parser = ExprParser::new();
feed_full(&mut parser, "(A & B)").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(and(atom('A'), atom('B'))));
let mut parser = ExprParser::new();
feed_full(&mut parser, "(A | B)").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(or(atom('A'), atom('B'))));
let mut parser = ExprParser::new();
feed_full(&mut parser, "(!A)").unwrap();
assert_eq!(parser.finish().unwrap(), expr!(not(atom('A'))));
});
}
#[test]
fn test_paren_expr_priority() {
timeout!(1000, {
let mut parser = ExprParser::new();
feed_full(&mut parser, "X | (A & B)").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(or(atom('X'), and(atom('A'), atom('B'))))
);
let mut parser = ExprParser::new();
feed_full(&mut parser, "(A | B) & X").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(and(or(atom('A'), atom('B')), atom('X')))
);
});
}
#[test]
fn test_paren_not() {
timeout!(1000, {
let mut parser = ExprParser::new();
feed_full(&mut parser, "X & !(A | B)").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(and(atom('X'), not(or(atom('A'), atom('B')))))
);
let mut parser = ExprParser::new();
feed_full(&mut parser, "!(A | B) | X").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(or(not(or(atom('A'), atom('B'))), atom('X')))
);
});
}
#[test]
fn test_paren_surrounded() {
timeout!(1000, {
let mut parser = ExprParser::new();
feed_full(&mut parser, "X | (A & B) | (C & D) | Y").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(or(
atom('X'),
and(atom('A'), atom('B')),
and(atom('C'), atom('D')),
atom('Y')
))
);
});
}
#[test]
fn test_paren_nested() {
timeout!(1000, {
let mut parser = ExprParser::new();
feed_full(&mut parser, "!(A & !(B & !(C & D)))").unwrap();
assert_eq!(
parser.finish().unwrap(),
expr!(not(and(atom('A'), not(and(atom('B'), not(and(atom('C'), atom('D'))))))))
);
});
}
#[test]
fn test_parser_errors_basic() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
assert!(matches!(parser.push_op('&'), Err(_)));
let mut parser = SimpleExprParser::new();
assert!(matches!(parser.push_op('|'), Err(_)));
let mut parser = SimpleExprParser::new();
parser.push_atom('A').unwrap();
assert!(matches!(parser.push_atom('B'), Err(_)));
let mut parser = SimpleExprParser::new();
parser.push_atom('A').unwrap();
assert!(matches!(parser.push_op('!'), Err(_)));
let mut parser = SimpleExprParser::new();
parser.push_op('!').unwrap();
parser.push_atom('A').unwrap();
assert!(matches!(parser.push_atom('B'), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A &").unwrap();
assert!(matches!(parser.push_op('&'), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A &").unwrap();
assert!(matches!(parser.push_op('|'), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A |").unwrap();
assert!(matches!(parser.push_op('&'), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A |").unwrap();
assert!(matches!(parser.push_op('|'), Err(_)));
});
}
#[test]
fn test_parser_error_unexpected_end() {
timeout!(1000, {
let mut parser = SimpleExprParser::new();
assert!(matches!(parser.finish(), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A &").unwrap();
assert!(matches!(parser.finish(), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "A |").unwrap();
assert!(matches!(parser.finish(), Err(_)));
let mut parser = SimpleExprParser::new();
feed_simple(&mut parser, "!").unwrap();
assert!(matches!(parser.finish(), Err(_)));
});
}
#[test]
fn test_error_paren_mismatched() {
timeout!(1000, {
let mut parser = ExprParser::new();
assert!(matches!(parser.close_paren(), Err(_)));
let mut parser = ExprParser::new();
parser.open_paren().unwrap();
assert!(matches!(parser.close_paren(), Err(_)));
let mut parser = ExprParser::new();
parser.open_paren().unwrap();
parser.push_atom('A').unwrap();
parser.push_op('&').unwrap();
assert!(matches!(parser.close_paren(), Err(_)));
let mut parser = ExprParser::new();
parser.open_paren().unwrap();
parser.push_op('!').unwrap();
assert!(matches!(parser.close_paren(), Err(_)));
let mut parser = ExprParser::new();
parser.open_paren().unwrap();
assert!(matches!(parser.finish(), Err(_)));
let mut parser = ExprParser::new();
parser.open_paren().unwrap();
parser.push_atom('A').unwrap();
assert!(matches!(parser.finish(), Err(_)));
let mut parser = ExprParser::new();
parser.push_atom('A').unwrap();
assert!(matches!(
parser.open_paren(),
Err(_)
));
let mut parser = ExprParser::new();
feed_full(&mut parser, "(A & B)").unwrap();
assert!(matches!(
parser.open_paren(),
Err(_)
));
});
}
#[test]
fn test_eval_full() {
timeout!(1000, {
assert_eq!(eval(&expr!(atom('A')), &['A'], &[]), Value::True);
assert_eq!(eval(&expr!(atom('A')), &[], &['A']), Value::False);
assert_eq!(eval(&expr!(not(atom('B'))), &['A'], &['B']), Value::True);
assert_eq!(eval(&expr!(not(atom('B'))), &['B'], &['A']), Value::False);
assert_eq!(eval(&expr!(and(atom('A'), atom('B'))), &['A', 'B'], &[]), Value::True);
assert_eq!(eval(&expr!(and(atom('A'), atom('B'))), &['A'], &['B']), Value::False);
assert_eq!(eval(&expr!(or(atom('A'), atom('B'))), &['A'], &['B']), Value::True);
assert_eq!(eval(&expr!(or(atom('A'), atom('B'))), &[], &['A', 'B']), Value::False);
});
}
#[test]
fn test_eval_not_and_or() {
timeout!(1000, {
assert_eq!(
eval(&expr!(not(and(atom('A'), atom('B')))), &['A', 'B'], &[]),
Value::False
);
assert_eq!(
eval(&expr!(not(and(atom('A'), atom('B')))), &['A'], &['B']),
Value::True
);
assert_eq!(
eval(&expr!(not(or(atom('A'), atom('B')))), &['A'], &['B']),
Value::False
);
assert_eq!(
eval(&expr!(not(or(atom('A'), atom('B')))), &[], &['A', 'B']),
Value::True
);
});
}
#[test]
fn test_eval_partial() {
timeout!(1000, {
assert_eq!(eval(&expr!(atom('A')), &[], &[]), Value::Expr(expr!(atom('A'))));
assert_eq!(
eval(&expr!(not(atom('B'))), &[], &[]),
Value::Expr(expr!(not(atom('B'))))
);
assert_eq!(
eval(&expr!(and(atom('A'), atom('B'), atom('C'))), &['B'], &[]),
Value::Expr(expr!(and(atom('A'), atom('C'))))
);
assert_eq!(
eval(&expr!(and(atom('A'), atom('B'), atom('C'))), &[], &['B']),
Value::False
);
assert_eq!(
eval(&expr!(or(atom('A'), atom('B'), atom('C'))), &['B'], &[]),
Value::True
);
assert_eq!(
eval(&expr!(or(atom('A'), atom('B'), atom('C'))), &[], &['B']),
Value::Expr(expr!(or(atom('A'), atom('C'))))
);
assert_eq!(
eval(&expr!(and(atom('A'), not(atom('B')), atom('C'))), &[], &['B']),
Value::Expr(expr!(and(atom('A'), atom('C'))))
);
assert_eq!(
eval(&expr!(and(atom('A'), not(atom('B')), atom('C'))), &['B'], &[]),
Value::False
);
assert_eq!(
eval(&expr!(or(atom('A'), not(atom('B')), atom('C'))), &[], &['B']),
Value::True
);
assert_eq!(
eval(&expr!(or(atom('A'), not(atom('B')), atom('C'))), &['B'], &[]),
Value::Expr(expr!(or(atom('A'), atom('C'))))
);
});
}
#[test]
fn test_eval_unwrap_and_or() {
timeout!(1000, {
assert_eq!(
eval(&expr!(and(atom('A'), atom('B'), atom('C'))), &['A', 'C'], &[]),
Value::Expr(expr!(atom('B')))
);
assert_eq!(
eval(&expr!(or(atom('A'), atom('B'), atom('C'))), &[], &['A', 'C']),
Value::Expr(expr!(atom('B')))
);
assert_eq!(
eval(&expr!(and(atom('A'), not(atom('B')), atom('C'))), &['A', 'C'], &[]),
Value::Expr(expr!(not(atom('B'))))
);
assert_eq!(
eval(&expr!(or(atom('A'), not(atom('B')), atom('C'))), &[], &['A', 'C']),
Value::Expr(expr!(not(atom('B'))))
);
});
}
#[test]
fn test_eval_unwrap_nested() {
timeout!(1000, {
assert_eq!(
eval(
&expr!(or(
atom('X'),
and(atom('A'), atom('B')),
not(and(atom('C'), atom('D'))),
atom('Y')
)),
&['A', 'C'],
&[]
),
Value::Expr(expr!(or(atom('X'), atom('B'), not(atom('D')), atom('Y'))))
);
});
}

Ще напишем програма, която работи с логически изрази от вида

A & !B & (C | D)

Изразът ще съдържа следните символи:

  • атом - еднобуквено име на променлива. Може да е всичко освен whitespace символи и специалните символи, използвани отдолу
  • оператор:
    • & - бинарната операция конюнкция
    • | - бинарната операции дизюнкция
    • ! - унарната операция отрицание
  • ( ) - скоби, указващи приоритет

Правила за парсене.
Следват се нормалните правила за групиране и приоритет, с едно изключение. В нашия израз операциите конюнкция и дизюнкция ще имат еднакъв приоритет. Групирането между тях се случва просто от ляво надясно.

A & B & C & D  =  ((A & B) & C) & D
A & B | C & D  =  ((A & B) | C) & D   // а не (A & B) | (C & D)

Целта е изразът да се разпарси до стойност от типа Expr.

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
    Atom(char),
    Not(Box<Expr>),
    And(Vec<Expr>),
    Or(Vec<Expr>),
}

За да направим нещата по-интересни (и някой би казал по-оптимални), ако има няколко поредни операции конюнкция или дизюнкция, те се обединяват в един списък.
Т.е. A & B & C става And(['А', 'B', 'C']).

Някой може да се запита, не можем ли да ползваме по-опримално представяне и на вложени отрицания? Може, но това не е толкова интересно, затова няма да го правим.

Напишете парсър за описания израз. Парсъра ще получава символите от израза един по един чрез извикване на съответния метод, така че ще трябва да си пази някакво междинно състояние.
Ако подадения символ води до невалиден израз, трябва да се върне ParseError. Например невалидно е да има два поредни бинарни оператора (А & &) или два поредни атома (A & B B).

#[derive(Debug, PartialEq, Eq)]
pub enum ParseError {
    UnexpectedExpr,
    UnexpectedUnaryOp,
    UnexpectedBinOp,
    UnexpectedParen,
    UnexpectedEnd,
}

/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
    // ...
}

impl SimpleExprParser {
    pub fn new() -> SimpleExprParser {
        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 finish(self) -> Result<Expr, ParseError> {
        todo!()
    }
}

И след това още един парсър, който приема и скоби.

/// Парсър за пълния израз
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!()
    }
}

След като имаме разпарсен израз, можем да свършим някаква работа с него, а именно да го оценим.
Напишете функция eval, която приема израз и два масива от атоми - такива, които се оценяват до истина и такива, които се оценяват до лъжа. Можете да приемете, че двата масива нямат общи елементи (не е нужно да правите проверка). Не е нужно всички използвани атоми от израза да присъстват в масивите.

Ако израза може да се оцени напълно, трябва да се върне True или False. Иначе трябва да се върне израз Expr, където всички срещания на атоми с известна стойност за заместени с тази стойност и опростени доколкото може:

  • A & True = A; True & A = A
  • A & False = False; False & A = False
  • A | True = True; True | A = True
  • A | False = A; False | A = A

В резутата не трябва да се връщат Expr::And или Expr::Or с 0 или 1 елемента - те трябва да се опростят.
Не трябва, обаче, да се прави разкриване на скоби - "!(A & B)" си остава "!(A & B)".

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
    True,
    False,
    Expr(Expr),
}

pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
    todo!()
}

Забележка: за по-лесно тестване можете да си направите функция parse, която приема низ и го подава символ по символ на съответния метод push_atom/push_op/open_paren/close_paren. Но трябва да имплементирате отделните методи, защото тестовете ще проверяват тях.

Вижте и придизвикателството за още една идея, която може да ви улесни тестването - https://fmi.rust-lang.bg/challenges/3.

Задължително прочетете (или си припомнете): Указания за предаване на домашни

Погрижете се решението ви да се компилира с базовия тест:

use solution::*;
#[test]
fn test_basic_simple_parser() {
// A & B
let mut simple_parser = SimpleExprParser::new();
let _ = simple_parser.push_atom('A');
let _ = simple_parser.push_op('&');
let _ = simple_parser.push_atom('B');
let expr = simple_parser.finish().unwrap();
eval(&expr, &['A'], &['B']);
}
#[test]
fn test_basic_expr_parser() {
// A & (B | !C)
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let _ = full_parser.push_op('&');
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('B');
let _ = full_parser.push_op('|');
let _ = full_parser.push_op('!');
let _ = full_parser.push_atom('C');
let _ = full_parser.close_paren();
let expr = full_parser.finish().unwrap();
eval(&expr, &['A'], &['B']);
}
#[test]
fn test_basic_errors() {
let mut simple_parser = SimpleExprParser::new();
let _ = simple_parser.push_atom('A');
let _ = simple_parser.push_op('&');
assert_eq!(simple_parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
let mut simple_parser = SimpleExprParser::new();
let _ = simple_parser.push_atom('A');
let _ = simple_parser.push_op('&');
let _ = simple_parser.push_atom('B');
assert_eq!(simple_parser.push_atom('B'), Err(ParseError::UnexpectedExpr));
}