Решение на Логически изрази от Александър Гуров
Към профила на Александър Гуров
Резултати
- 16 точки от тестове
- 0 бонус точки
- 16 точки общо
- 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 struct SimpleExprParser {
atoms: VecDeque<char>,
operators: VecDeque<char>,
last_was_atom: bool,
}
impl Clone for SimpleExprParser {
fn clone(&self) -> Self {
SimpleExprParser {
atoms: self.atoms.clone(),
operators: self.operators.clone(),
last_was_atom: self.last_was_atom,
}
}
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
atoms: VecDeque::new(),
operators: VecDeque::new(),
last_was_atom: false,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if self.last_was_atom {
return Err(ParseError::UnexpectedExpr);
}
self.atoms.push_back(c);
self.last_was_atom = true;
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' => {
if !self.last_was_atom {
return Err(ParseError::UnexpectedBinOp);
}
self.operators.push_back(op);
self.last_was_atom = false;
}
'!' => {
self.operators.push_back(op);
}
_ => panic!("Unexpected operator: {}", op),
}
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if !self.last_was_atom {
return Err(ParseError::UnexpectedEnd);
}
let mut expr_queue: VecDeque<Expr> = VecDeque::new();
while let Some(atom) = self.atoms.pop_front() {
expr_queue.push_back(Expr::Atom(atom));
}
while let Some(op) = self.operators.pop_front() {
match op {
'&' | '|' => {
let lhs = expr_queue.pop_front().ok_or(ParseError::UnexpectedEnd)?;
let mut rhs = expr_queue.pop_front().ok_or(ParseError::UnexpectedEnd)?;
if let Some('!') = self.operators.front() {
let mut not_count = 0;
while let Some('!') = self.operators.front() {
not_count += 1;
self.operators.pop_front();
}
for _ in 0..not_count {
rhs = Expr::Not(Box::new(rhs));
}
}
let grouped = Self::merge(lhs, rhs, op);
expr_queue.push_front(grouped);
}
'!' => {
let mut not_count = 1;
while let Some('!') = self.operators.front() {
not_count += 1;
self.operators.pop_front();
}
if let Some(next_atom) = expr_queue.pop_front() {
let mut expr = next_atom;
for _ in 0..not_count {
expr = Expr::Not(Box::new(expr));
}
expr_queue.push_front(expr);
} else {
return Err(ParseError::UnexpectedUnaryOp);
}
}
_ => unreachable!(),
}
}
if expr_queue.len() == 1 {
Ok(expr_queue.pop_front().unwrap())
} else {
Err(ParseError::UnexpectedEnd)
}
}
fn merge(lhs: Expr, rhs: Expr, op: char) -> Expr {
match op {
'&' => {
if let Expr::And(mut lhs_vec) = lhs {
lhs_vec.push(rhs);
Expr::And(lhs_vec)
} else if let Expr::And(mut rhs_vec) = rhs {
rhs_vec.push(lhs);
Expr::And(rhs_vec)
} else {
Expr::And(vec![lhs, rhs])
}
}
'|' => {
if let Expr::Or(mut lhs_vec) = lhs {
lhs_vec.push(rhs);
Expr::Or(lhs_vec)
} else if let Expr::Or(mut rhs_vec) = rhs {
rhs_vec.push(lhs);
Expr::Or(rhs_vec)
} else {
Expr::Or(vec![lhs, rhs])
}
}
_ => unreachable!(),
}
}
}
pub struct ExprParser {
queue: VecDeque<(VecDeque<Expr>, VecDeque<char>)>,
current_exprs: VecDeque<Expr>,
current_ops: VecDeque<char>,
last_was_atom: bool,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
queue: VecDeque::new(),
current_exprs: VecDeque::new(),
current_ops: VecDeque::new(),
last_was_atom: false,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if let Some(last_op) = self.current_ops.back() {
if *last_op == '!' {
self.current_ops.pop_back();
self.current_exprs
.push_back(Expr::Not(Box::new(Expr::Atom(c))));
self.last_was_atom = true;
return Ok(());
}
}
if !self.current_exprs.is_empty() && self.current_ops.is_empty() {
return Err(ParseError::UnexpectedExpr);
}
self.current_exprs.push_back(Expr::Atom(c));
self.last_was_atom = true;
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' => {
if self.current_exprs.is_empty() || !self.last_was_atom {
return Err(ParseError::UnexpectedBinOp);
}
self.current_ops.push_back(op);
self.last_was_atom = false;
}
'!' => {
self.current_ops.push_back(op);
}
_ => panic!("Unexpected operator: {}", op),
}
Ok(())
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.queue
.push_back((self.current_exprs.clone(), self.current_ops.clone()));
self.current_exprs.clear();
self.current_ops.clear();
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.queue.is_empty() {
return Err(ParseError::UnexpectedParen);
}
let (mut prev_exprs, prev_ops) = self.queue.pop_back().unwrap();
let grouped_expr = self.finalize_current_expr()?;
prev_exprs.push_back(grouped_expr);
self.current_exprs = prev_exprs;
self.current_ops = prev_ops;
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
if !self.queue.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
self.finalize_current_expr()
}
fn finalize_current_expr(&self) -> Result<Expr, ParseError> {
if self.current_exprs.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
let mut expr_queue = self.current_exprs.clone();
let mut ops_queue = self.current_ops.clone();
while let Some(op) = ops_queue.pop_front() {
if op == '!' {
let operand = expr_queue
.pop_front()
.ok_or(ParseError::UnexpectedUnaryOp)?;
expr_queue.push_front(Expr::Not(Box::new(operand)));
} else {
let lhs = expr_queue.pop_front().ok_or(ParseError::UnexpectedEnd)?;
let rhs = expr_queue.pop_front().ok_or(ParseError::UnexpectedEnd)?;
expr_queue.push_front(Self::merge(lhs, rhs, op));
}
}
if expr_queue.len() == 1 {
Ok(expr_queue.pop_front().unwrap())
} else {
Err(ParseError::UnexpectedEnd)
}
}
fn merge(lhs: Expr, rhs: Expr, op: char) -> Expr {
match op {
'&' => {
if let Expr::And(mut lhs_vec) = lhs {
lhs_vec.push(rhs);
Expr::And(lhs_vec)
} else if let Expr::And(mut rhs_vec) = rhs {
rhs_vec.push(lhs);
Expr::And(rhs_vec)
} else {
Expr::And(vec![lhs, rhs])
}
}
'|' => {
if let Expr::Or(mut lhs_vec) = lhs {
lhs_vec.push(rhs);
Expr::Or(lhs_vec)
} else if let Expr::Or(mut rhs_vec) = rhs {
rhs_vec.push(lhs);
Expr::Or(rhs_vec)
} else {
Expr::Or(vec![lhs, rhs])
}
}
_ => unreachable!(),
}
}
}
#[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 op in operands {
match eval(op, truthy, falsy) {
Value::True => continue,
Value::False => return Value::False,
Value::Expr(e) => simplified.push(e),
}
}
if simplified.is_empty() {
Value::True
} else if simplified.len() == 1 {
Value::Expr(simplified.pop().unwrap())
} else {
Value::Expr(Expr::And(simplified))
}
}
Expr::Or(operands) => {
let mut simplified = Vec::new();
for op in operands {
match eval(op, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue,
Value::Expr(e) => simplified.push(e),
}
}
if simplified.is_empty() {
Value::False
} else if simplified.len() == 1 {
Value::Expr(simplified.pop().unwrap())
} else {
Value::Expr(Expr::Or(simplified))
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-1jbz2m4/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.86s
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 ... FAILED
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_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_and_or ... ok
test solution_test::test_parser_alternating_ops ... 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 ... ok
test solution_test::test_parser_not ... 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('C'), Atom('D'), Atom('B')]))])))`,
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('C'), Atom('D'), Atom('B')]))])))`,
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
failures:
solution_test::test_error_paren_mismatched
solution_test::test_paren_nested
solution_test::test_paren_not
solution_test::test_parser_errors_basic
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`