Решение на Логически изрази от Венцислав Монев
Към профила на Венцислав Монев
Резултати
- 16 точки от тестове
- 1 бонус точка
- 17 точки общо
- 16 успешни тест(а)
- 4 неуспешни тест(а)
Код
use std::collections::VecDeque;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
Atom(char),
Not(Box<Expr>),
And(Vec<Expr>),
Or(Vec<Expr>),
}
#[derive(Debug, PartialEq, Eq)]
pub enum ParseError {
UnexpectedExpr,
UnexpectedUnaryOp,
UnexpectedBinOp,
UnexpectedParen,
UnexpectedEnd,
}
pub fn process_operations_and_atoms(
operations: &mut VecDeque<char>,
atoms: &mut VecDeque<Expr>,
) -> Expr {
let mut last_operation: Option<char> = None;
while let Some(operation) = operations.pop_front() {
let mut first_atom = atoms.pop_front().unwrap();
let second_atom = atoms.pop_front().unwrap();
match (operation, last_operation) {
('&', Some('&')) => {
if let Expr::And(mut vec) = first_atom {
vec.push(second_atom);
first_atom = Expr::And(vec);
}
}
('|', Some('|')) => {
if let Expr::Or(mut vec) = first_atom {
vec.push(second_atom);
first_atom = Expr::Or(vec);
}
}
('&', _) => {
first_atom = Expr::And(vec![first_atom, second_atom]);
}
('|', _) => {
first_atom = Expr::Or(vec![first_atom, second_atom]);
}
(_, _) => {
panic!("Unexpected operation or state!");
}
}
last_operation = Some(operation);
atoms.push_front(first_atom.clone());
}
atoms.pop_front().unwrap()
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
atom_queue:VecDeque<Expr>,
operation_queue:VecDeque<char>,
exl_counter:u32,
exp_atom:bool
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { atom_queue:VecDeque::new(), operation_queue:VecDeque::new(), exl_counter:0, exp_atom:true, }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
// проверявам дали масива с атоми е празен, ако той е празен и няма бинарен оператор добавям
// или ако има само един атом и бинарен оператор пак добавям
// всички други случай връщам грешка
if c.is_whitespace() || c == '&' || c == '|' || c == '!' {
panic!("White spaces can`t be used for atoms or any of the operators !, & or |")
}
if !self.exp_atom {
return Err(ParseError::UnexpectedExpr)
}
else if self.exl_counter%2 == 0 {
self.atom_queue.push_back(Expr::Atom(c));
self.exl_counter = 0;
}
else if self.exl_counter%2 == 1 {
self.atom_queue.push_back(Expr::Not(Box::new(Expr::Atom(c))));
self.exl_counter = 0;
}
self.exp_atom = false;
Ok(())
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
match self.exp_atom {
true => {self.exl_counter+=1;}
_ => {return Err(ParseError::UnexpectedUnaryOp)}
}
}
'&' | '|' => {
match self.exp_atom {
true => {return Err(ParseError::UnexpectedBinOp)}
_ => {
self.operation_queue.push_back(op);
self.exp_atom=true;
}
}
}
_ => {panic!("Invalid operator: {}", op);}
}
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.atom_queue.len() != self.operation_queue.len() + 1 {
return Err(ParseError::UnexpectedEnd)
}
let mut atoms = self.atom_queue;
let mut operations = self.operation_queue;
let x = process_operations_and_atoms(&mut operations,&mut atoms);
Ok(x.clone())
}
}
/// Парсър за пълния израз
pub struct ExprParser {
atom_queue:VecDeque<Expr>,
operation_queue:VecDeque<char>,
opening_parenthesis_count:i32,
exp_atom:bool
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { atom_queue:VecDeque::new(), operation_queue: VecDeque::new(), opening_parenthesis_count: 0, exp_atom:true }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if c.is_whitespace() || c == '&' || c == '|' || c == '!' {
panic!("White spaces can`t be used for atoms or any of the operators !, & or |")
}
if !self.exp_atom {
return Err(ParseError::UnexpectedExpr)
}
else {
self.atom_queue.push_back(Expr::Atom(c));
}
self.exp_atom = false;
Ok(())
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
match self.exp_atom {
true => {self.operation_queue.push_back(op);}
false => {return Err(ParseError::UnexpectedUnaryOp)}
}
}
'&' | '|' => {
match self.exp_atom {
true => {return Err(ParseError::UnexpectedBinOp)}
false => {
self.operation_queue.push_back(op);
self.exp_atom=true;
}
}
}
_ => {panic!("Invalid operator: {}", op);}
}
Ok(())
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
match self.exp_atom {
true => {
self.operation_queue.push_back('(');
self.opening_parenthesis_count+=1;
},
false => {
return Err(ParseError::UnexpectedParen)
}
}
Ok(())
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.opening_parenthesis_count<=0 || self.exp_atom{
return Err(ParseError::UnexpectedParen)
}
let mut inner_atoms_queue:VecDeque<Expr> = VecDeque::new();
let mut inner_operations_queue:VecDeque<char> = VecDeque::new();
while let Some(op) = self.operation_queue.pop_back() {
match op {
'(' => {
let x = process_operations_and_atoms(&mut inner_operations_queue, &mut inner_atoms_queue);
self.atom_queue.push_back(x);
if self.operation_queue.back() == Some(&'!'){
let x = self.atom_queue.pop_back();
match x {
Some(x) => self.atom_queue.push_back(Expr::Not(Box::new(x))),
None => return Err(ParseError::UnexpectedParen),
}
}
self.opening_parenthesis_count-=1;
break;
}
'!' => {
let mut exl_counter = 1;
while self.operation_queue.back() == Some(&'!') {
self.operation_queue.pop_back();
exl_counter+=1;
}
let x;
if exl_counter%2 == 0 {
x = self.atom_queue.pop_back().unwrap();
}
else {
x = Expr::Not(Box::new(self.atom_queue.pop_back().unwrap()));
}
self.atom_queue.push_back(x);
}
'&' | '|' => {
inner_atoms_queue.push_front(self.atom_queue.pop_back().unwrap());
inner_atoms_queue.push_front(self.atom_queue.pop_back().unwrap());
inner_operations_queue.push_front(op);
}
_ => panic!("Something went wrong"),
}
}
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.atom_queue.len() != self.operation_queue.len() + 1 || self.opening_parenthesis_count !=0{
return Err(ParseError::UnexpectedEnd)
}
let mut atoms = self.atom_queue;
let mut operations = self.operation_queue;
let x = process_operations_and_atoms(&mut operations,&mut atoms);
Ok(x.clone())
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
True,
False,
Expr(Expr),
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
match expr {
Expr::Atom(c) => {
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(expr.clone())
}
}
Expr::Not(inner) => match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(e) => Value::Expr(Expr::Not(Box::new(e))),
},
Expr::And(operands) => {
let mut simplified = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::False => return Value::False,
Value::True => continue,
Value::Expr(e) => simplified.push(e),
}
}
match simplified.len() {
0 => Value::True,
1 => Value::Expr(simplified.into_iter().next().unwrap()),
_ => Value::Expr(Expr::And(simplified)),
}
}
Expr::Or(operands) => {
let mut simplified = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue,
Value::Expr(e) => simplified.push(e),
}
}
match simplified.len() {
0 => Value::False,
1 => Value::Expr(simplified.into_iter().next().unwrap()),
_ => Value::Expr(Expr::Or(simplified)),
}
}
}
}
#[test]
fn simple_parser() {
let mut parser = SimpleExprParser::new();
assert_eq!(Ok(()), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_atom('G'));
assert_eq!(Ok(()), parser.push_op('&'));
assert_eq!(Ok(()), parser.push_atom('E'));
assert_eq!(Ok(()), parser.push_op('|'));
assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('&'));
assert_eq!(Ok(()), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_atom('H'));
assert_eq!(Err(ParseError::UnexpectedUnaryOp), parser.push_op('!'));
assert_eq!(Err(ParseError::UnexpectedUnaryOp), parser.push_op('!'));
assert_eq!(Ok(()), parser.push_op('&'));
assert_eq!(Ok(()), parser.push_atom('H'));
assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('I'));
assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('I'));
assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('I'));
assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('I'));
assert_eq!(Ok(()), parser.push_op('|'));
assert_eq!(Ok(()), parser.push_atom('H'));
//assert_eq!(Ok(()), parser.push_op('|'));
//assert_eq!(Err(ParseError::UnexpectedEnd), parser.finish());
let x = parser.finish().unwrap();
assert_eq!(Value::False, eval(&x, &['G','I'], &['H']));
}
#[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));
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-1yn6lki/solution)
warning: variable does not need to be mutable
--> tests/solution_test.rs:306:13
|
306 | let mut parser = SimpleExprParser::new();
| ----^^^^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: `solution` (test "solution_test") generated 1 warning
Finished test [unoptimized + debuginfo] target(s) in 1.75s
Running tests/solution_test.rs (target/debug/deps/solution_test-1428e1090729d165)
running 20 tests
test solution_test::test_eval_full ... ok
test solution_test::test_error_paren_mismatched ... ok
test solution_test::test_eval_not_and_or ... ok
test solution_test::test_eval_partial ... ok
test solution_test::test_eval_unwrap_and_or ... ok
test solution_test::test_eval_unwrap_nested ... ok
test solution_test::test_paren_expr_priority ... ok
test solution_test::test_paren_around_expr ... FAILED
test solution_test::test_paren_nested ... FAILED
test solution_test::test_paren_not ... FAILED
test solution_test::test_paren_surrounded ... ok
test solution_test::test_parser_alternating_ops ... ok
test solution_test::test_parser_and_or ... ok
test solution_test::test_parser_atom ... ok
test solution_test::test_parser_error_unexpected_end ... ok
test solution_test::test_parser_errors_basic ... ok
test solution_test::test_parser_expr_and_not ... ok
test solution_test::test_parser_multiple_atoms_same_op ... ok
test solution_test::test_parser_multiple_not ... FAILED
test solution_test::test_parser_not ... ok
failures:
---- solution_test::test_paren_around_expr stdout ----
thread '<unnamed>' panicked at 'called `Option::unwrap()` on a `None` value', src/lib.rs:58:23
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'solution_test::test_paren_around_expr' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:176:5
---- solution_test::test_paren_nested stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedEnd', tests/solution_test.rs:256:29
thread 'solution_test::test_paren_nested' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedEnd', tests/solution_test.rs:252:5
---- solution_test::test_paren_not stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedEnd', tests/solution_test.rs:220:29
thread 'solution_test::test_paren_not' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedEnd', tests/solution_test.rs:216:5
---- solution_test::test_parser_multiple_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(Atom('B'))`,
right: `Not(Not(Not(Atom('B'))))`', tests/solution_test.rs:143:9
thread 'solution_test::test_parser_multiple_not' panicked at 'assertion failed: `(left == right)`
left: `Not(Atom('B'))`,
right: `Not(Not(Not(Atom('B'))))`', tests/solution_test.rs:140:5
failures:
solution_test::test_paren_around_expr
solution_test::test_paren_nested
solution_test::test_paren_not
solution_test::test_parser_multiple_not
test result: FAILED. 16 passed; 4 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`