Решение на Логически изрази от Александър Асенов
Към профила на Александър Асенов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 5 неуспешни тест(а)
Код
use std::{collections::VecDeque, vec};
#[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,
}
#[derive(Clone)]
pub struct SimpleExprParser {
pub expr: VecDeque<Expr>,
pub op: VecDeque<char>,
last_op: bool
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { expr: VecDeque::new(), op: VecDeque::new(), last_op: true }
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if !self.last_op {
return Err(ParseError::UnexpectedExpr);
}
if !self.op.is_empty() && self.op.back() == Some(&'!') {
self.op.pop_back();
self.expr.push_back(Expr::Not(Box::new(Expr::Atom(c))));
} else {
self.expr.push_back(Expr::Atom(c));
}
self.toggle_las_op();
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
if op != '!' && self.last_op {
return Err(ParseError::UnexpectedBinOp);
}
match op {
'!' => {
self.op.push_back(op);
}
'&' | '|' => {
if self.expr.is_empty() {
return Err(ParseError::UnexpectedBinOp);
}
self.op.push_back(op);
self.toggle_las_op();
}
_ => panic!("Unknown operation"),
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
let mut expr_queue = self.expr.clone();
let mut op_queue = self.op.clone();
if expr_queue.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
while let Some(op) = op_queue.pop_front() {
if expr_queue.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
match op {
'!' => {
let expr = expr_queue.pop_front().unwrap();
let negated = Expr::Not(Box::new(expr));
expr_queue.push_front(negated);
}
'&' | '|' => {
if expr_queue.len() < 2 {
return Err(ParseError::UnexpectedEnd);
}
let left = expr_queue.pop_front().unwrap();
let right = expr_queue.pop_front().unwrap();
let combined = match op {
'&' => match left {
Expr::And(mut vec) => {
vec.push(right);
Expr::And(vec)
}
_ => Expr::And(vec![left, right]),
},
'|' => match left {
Expr::Or(mut vec) => {
vec.push(right);
Expr::Or(vec)
}
_ => Expr::Or(vec![left, right]),
},
_ => unreachable!(),
};
expr_queue.push_front(combined);
}
_ => panic!("Unknown operation"),
}
}
if expr_queue.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
Ok(expr_queue.pop_front().unwrap())
}
pub fn toggle_las_op(&mut self) {
self.last_op = !self.last_op;
}
}
pub struct ExprParser {
exprs: VecDeque<SimpleExprParser>,
open_paren: i32
}
impl ExprParser {
pub fn new() -> ExprParser {
let mut vecq = VecDeque::new();
vecq.push_back(SimpleExprParser::new());
ExprParser { exprs: vecq, open_paren: 0 }
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match self.exprs.back_mut() {
Some(parser) => parser.push_atom(c),
None => Err(ParseError::UnexpectedExpr),
}
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match self.exprs.back_mut() {
Some(parser) => parser.push_op(op),
None => Err(ParseError::UnexpectedExpr),
}
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.exprs.push_back(SimpleExprParser::new());
self.open_paren += 1;
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_paren <= 0 {
return Err(ParseError::UnexpectedParen);
}
let expr = self.exprs.pop_back().ok_or(ParseError::UnexpectedParen).unwrap().finish()?;
self.open_paren -= 1;
match self.exprs.back_mut() {
Some(parent_expr) => {
if !parent_expr.last_op {
return Err(ParseError::UnexpectedExpr);
}
parent_expr.expr.push_back(expr);
parent_expr.toggle_las_op();
Ok(())
},
None => {
let mut new_parser = SimpleExprParser::new();
new_parser.expr.push_back(expr);
new_parser.toggle_las_op();
self.exprs.push_back(new_parser);
Ok(())
},
}
}
pub fn finish(self) -> Result<Expr, ParseError> {
if self.exprs.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
self.exprs.clone().pop_back().unwrap().finish()
}
}
#[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(atom) => {
if truthy.contains(atom) {
Value::True
} else if falsy.contains(atom) {
Value::False
} else {
Value::Expr(Expr::Atom(*atom))
}
}
Expr::Not(inner_expr) => match eval(inner_expr, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(expr) => Value::Expr(Expr::Not(Box::new(expr))),
},
Expr::And(inner_expr) => {
let mut values = Vec::new();
for sub_expr in inner_expr {
match eval(sub_expr, truthy, falsy) {
Value::False => return Value::False,
Value::Expr(e) => values.push(e),
_ => (),
}
}
if values.is_empty() {
Value::True
} else if values.len() == 1 {
let value = values.get(0).unwrap();
Value::Expr(value.to_owned())
} else {
Value::Expr(Expr::And(values))
}
}
Expr::Or(inner_expr) => {
let mut values = Vec::new();
for sub_expr in inner_expr {
match eval(sub_expr, truthy, falsy) {
Value::True => return Value::True,
Value::Expr(e) => values.push(e),
_ => (),
}
}
if values.is_empty() {
Value::False
} else if values.len() == 1 {
let value = values.get(0).unwrap();
Value::Expr(value.to_owned())
} else {
Value::Expr(Expr::Or(values))
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-2rc8jk/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 2.01s
Running tests/solution_test.rs (target/debug/deps/solution_test-1428e1090729d165)
running 20 tests
test solution_test::test_error_paren_mismatched ... FAILED
test solution_test::test_eval_full ... 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_around_expr ... ok
test solution_test::test_paren_expr_priority ... ok
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 ... FAILED
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
test solution_test::test_eval_not_and_or ... ok
failures:
---- solution_test::test_error_paren_mismatched stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.open_paren(), Err(_))', tests/solution_test.rs:355:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'solution_test::test_error_paren_mismatched' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:325:5
---- solution_test::test_paren_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(Not(And([Atom('A'), Not(And([Atom('B'), And([Atom('C'), Atom('D')])]))])))`,
right: `Not(And([Atom('A'), Not(And([Atom('B'), Not(And([Atom('C'), Atom('D')]))]))]))`', tests/solution_test.rs:255:9
thread 'solution_test::test_paren_nested' panicked at 'assertion failed: `(left == right)`
left: `Not(Not(And([Atom('A'), Not(And([Atom('B'), And([Atom('C'), Atom('D')])]))])))`,
right: `Not(And([Atom('A'), Not(And([Atom('B'), Not(And([Atom('C'), Atom('D')]))]))]))`', tests/solution_test.rs:252:5
---- solution_test::test_paren_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(And([Atom('X'), Or([Atom('A'), Atom('B')])]))`,
right: `And([Atom('X'), Not(Or([Atom('A'), Atom('B')]))])`', tests/solution_test.rs:219:9
thread 'solution_test::test_paren_not' panicked at 'assertion failed: `(left == right)`
left: `Not(And([Atom('X'), Or([Atom('A'), Atom('B')])]))`,
right: `And([Atom('X'), Not(Or([Atom('A'), Atom('B')]))])`', tests/solution_test.rs:216:5
---- solution_test::test_parser_errors_basic stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.push_op(\'!\'), Err(_))', tests/solution_test.rs:278:9
thread 'solution_test::test_parser_errors_basic' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:265:5
---- solution_test::test_parser_multiple_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(Or([Atom('A'), Not(Atom('B'))]))`,
right: `Or([Atom('A'), Not(Not(Atom('B')))])`', tests/solution_test.rs:147:9
thread 'solution_test::test_parser_multiple_not' panicked at 'assertion failed: `(left == right)`
left: `Not(Or([Atom('A'), Not(Atom('B'))]))`,
right: `Or([Atom('A'), Not(Not(Atom('B')))])`', tests/solution_test.rs:140:5
failures:
solution_test::test_error_paren_mismatched
solution_test::test_paren_nested
solution_test::test_paren_not
solution_test::test_parser_errors_basic
solution_test::test_parser_multiple_not
test result: FAILED. 15 passed; 5 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s
error: test failed, to rerun pass `--test solution_test`