Решение на Логически изрази от Юлиян Палов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 5 неуспешни тест(а)
Код
#[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, Debug, PartialEq, Eq)]
pub enum Value
{
True,
False,
Expr(Expr),
}
fn simplify_expr(e: Expr) -> Expr
{
match e
{
Expr::And(mut v) =>
{
if v.is_empty()
{
return Expr::Atom('T');
}
if v.len() == 1
{
return v.remove(0);
}
Expr::And(v.into_iter().map(simplify_expr).collect())
}
Expr::Or(mut v) =>
{
if v.is_empty()
{
return Expr::Atom('F');
}
if v.len() == 1
{
return v.remove(0);
}
Expr::Or(v.into_iter().map(simplify_expr).collect())
}
Expr::Not(e2) => Expr::Not(Box::new(simplify_expr(*e2))),
Expr::Atom(_) => e,
}
}
pub struct SimpleExprParser
{
expect_term: bool,
pending_nots: usize,
blocks: Vec<(Option<char>, Vec<Expr>)>,
}
impl SimpleExprParser
{
pub fn new() -> SimpleExprParser
{
SimpleExprParser
{
expect_term: true,
pending_nots: 0,
blocks: vec![],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError>
{
if !self.expect_term
{
return Err(ParseError::UnexpectedExpr);
}
let mut expr = Expr::Atom(c);
for _ in 0..self.pending_nots
{
expr = Expr::Not(Box::new(expr));
}
self.pending_nots = 0;
if self.blocks.is_empty()
{
self.blocks.push((None, vec![expr]));
}
else
{
let last = self.blocks.last_mut().unwrap();
last.1.push(expr);
}
self.expect_term = false;
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError>
{
match op
{
'!' =>
{
if !self.expect_term
{
return Err(ParseError::UnexpectedUnaryOp);
}
self.pending_nots += 1;
Ok(())
}
'&' | '|' =>
{
if self.expect_term
{
return Err(ParseError::UnexpectedBinOp);
}
let current_op = if self.blocks.is_empty()
{
None
}
else
{
self.blocks.last().unwrap().0
};
if current_op == Some(op) {
}
else
{
self.blocks.push((Some(op), vec![]));
}
self.expect_term = true;
Ok(())
}
_ => panic!("Unsupported operator"),
}
}
pub fn finish(self) -> Result<Expr, ParseError>
{
if self.expect_term
{
return Err(ParseError::UnexpectedEnd);
}
let mut iter = self.blocks.into_iter();
let (first_op, mut first_args) = iter.next().unwrap();
if first_op.is_some()
{
return Err(ParseError::UnexpectedExpr);
}
let mut current_expr = if first_args.len() == 1
{
first_args.pop().unwrap()
}
else if first_args.len() > 1
{
return Err(ParseError::UnexpectedExpr);
}
else
{
return Err(ParseError::UnexpectedEnd);
};
for (op, args) in iter
{
let op = op.ok_or(ParseError::UnexpectedExpr)?;
if args.is_empty()
{
return Err(ParseError::UnexpectedEnd);
}
let block_expr = if args.len() == 1
{
args[0].clone()
}
else
{
if op == '&'
{
Expr::And(args)
}
else
{
Expr::Or(args)
}
};
let new_expr = match op
{
'&' => {
let and_args = match current_expr
{
Expr::And(mut v) =>
{
v.push(block_expr);
v
}
_ => vec![current_expr, block_expr],
};
Expr::And(and_args)
}
'|' => {
let or_args = match current_expr
{
Expr::Or(mut v) =>
{
v.push(block_expr);
v
}
_ => vec![current_expr, block_expr],
};
Expr::Or(or_args)
}
_ => unreachable!(),
};
current_expr = new_expr;
}
Ok(simplify_expr(current_expr))
}
}
pub struct ExprParser
{
stack: Vec<SimpleExprParser>,
pending_nots: usize,
}
impl ExprParser
{
pub fn new() -> ExprParser
{
ExprParser
{
stack: vec![SimpleExprParser::new()],
pending_nots: 0,
}
}
fn top(&mut self) -> &mut SimpleExprParser
{
self.stack.last_mut().unwrap()
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError>
{
for _ in 0..self.pending_nots
{
self.top().push_op('!')?;
}
self.pending_nots = 0;
self.top().push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError>
{
if op == '!' {
self.pending_nots += 1;
Ok(())
}
else
{
if self.pending_nots > 0
{
return Err(ParseError::UnexpectedUnaryOp);
}
self.top().push_op(op)
}
}
pub fn open_paren(&mut self) -> Result<(), ParseError>
{
let mut new_parser = SimpleExprParser::new();
for _ in 0..self.pending_nots
{
new_parser.push_op('!')?;
}
self.pending_nots = 0;
self.stack.push(new_parser);
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError>
{
if self.stack.len() == 1
{
return Err(ParseError::UnexpectedParen);
}
if self.pending_nots > 0
{
return Err(ParseError::UnexpectedUnaryOp);
}
let done_parser = self.stack.pop().unwrap();
let expr = done_parser.finish()?;
let expr = simplify_expr(expr);
self.push_expr_direct(expr)
}
fn push_expr_direct(&mut self, expr: Expr) -> Result<(), ParseError>
{
self.push_expr_as_term(expr)
}
fn push_expr_as_term(&mut self, expr: Expr) -> Result<(), ParseError>
{
let top = self.top();
if !top.expect_term
{
return Err(ParseError::UnexpectedExpr);
}
self.top().push_prepared_expr(expr)
}
pub fn finish(self) -> Result<Expr, ParseError>
{
if self.pending_nots > 0
{
return Err(ParseError::UnexpectedUnaryOp);
}
if self.stack.len() != 1
{
return Err(ParseError::UnexpectedEnd);
}
self.stack.into_iter().next().unwrap().finish()
}
}
impl SimpleExprParser
{
fn push_prepared_expr(&mut self, expr: Expr) -> Result<(), ParseError>
{
if !self.expect_term
{
return Err(ParseError::UnexpectedExpr);
}
for _ in 0..self.pending_nots
{
let expr2 = Expr::Not(Box::new(expr.clone()));
return self.push_prepared_expr(expr2);
}
self.pending_nots = 0;
if self.blocks.is_empty()
{
self.blocks.push((None, vec![expr]));
}
else
{
let last = self.blocks.last_mut().unwrap();
last.1.push(expr);
}
self.expect_term = false;
Ok(())
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value
{
fn eval_inner(e: &Expr, truthy: &[char], falsy: &[char]) -> Value
{
match e
{
Expr::Atom(c) =>
{
if *c == 'T'
{
Value::True
}
else if *c == 'F'
{
Value::False
}
else if truthy.contains(c)
{
Value::True
}
else if falsy.contains(c)
{
Value::False
}
else
{
Value::Expr(Expr::Atom(*c))
}
}
Expr::Not(e2) =>
{
let v = eval_inner(e2, truthy, falsy);
match v
{
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(expr2) => Value::Expr(Expr::Not(Box::new(expr2))),
}
}
Expr::And(es) =>
{
let mut new_args = Vec::new();
for sub in es
{
let v = eval_inner(sub, truthy, falsy);
match v
{
Value::False => return Value::False,
Value::True =>
{
}
Value::Expr(expr2) =>
{
new_args.push(expr2);
}
}
}
if new_args.is_empty()
{
Value::True
}
else if new_args.len() == 1
{
Value::Expr(new_args.pop().unwrap())
}
else
{
Value::Expr(Expr::And(new_args))
}
}
Expr::Or(es) =>
{
let mut new_args = Vec::new();
for sub in es
{
let v = eval_inner(sub, truthy, falsy);
match v
{
Value::True => return Value::True,
Value::False =>{
}
Value::Expr(expr2) =>
{
new_args.push(expr2);
}
}
}
if new_args.is_empty()
{
Value::False
}
else if new_args.len() == 1
{
Value::Expr(new_args.pop().unwrap())
}
else
{
Value::Expr(Expr::Or(new_args))
}
}
}
}
eval_inner(expr, truthy, falsy)
}
#[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-vqavf1/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.00s
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_not_and_or ... ok
test solution_test::test_eval_partial ... ok
test solution_test::test_eval_unwrap_nested ... ok
test solution_test::test_eval_unwrap_and_or ... 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_parser_alternating_ops ... ok
test solution_test::test_paren_surrounded ... FAILED
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 ... FAILED
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: `And([Not(Atom('A')), And([Not(Atom('B')), And([Not(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: `And([Not(Atom('A')), And([Not(Atom('B')), And([Not(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: `And([Atom('X'), Or([Not(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: `And([Atom('X'), Or([Not(Atom('A')), Atom('B')])])`,
right: `And([Atom('X'), Not(Or([Atom('A'), Atom('B')]))])`', tests/solution_test.rs:216:5
---- solution_test::test_paren_surrounded stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Or([Atom('X'), Or([And([Atom('A'), Atom('B')]), And([Atom('C'), Atom('D')]), Atom('Y')])])`,
right: `Or([Atom('X'), And([Atom('A'), Atom('B')]), And([Atom('C'), Atom('D')]), Atom('Y')])`', tests/solution_test.rs:238:9
thread 'solution_test::test_paren_surrounded' panicked at 'assertion failed: `(left == right)`
left: `Or([Atom('X'), Or([And([Atom('A'), Atom('B')]), And([Atom('C'), Atom('D')]), Atom('Y')])])`,
right: `Or([Atom('X'), And([Atom('A'), Atom('B')]), And([Atom('C'), Atom('D')]), Atom('Y')])`', tests/solution_test.rs:235:5
---- solution_test::test_parser_multiple_atoms_same_op stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `And([Atom('A'), And([Atom('B'), Atom('C')])])`,
right: `And([Atom('A'), Atom('B'), Atom('C')])`', tests/solution_test.rs:127:9
thread 'solution_test::test_parser_multiple_atoms_same_op' panicked at 'assertion failed: `(left == right)`
left: `And([Atom('A'), And([Atom('B'), Atom('C')])])`,
right: `And([Atom('A'), Atom('B'), Atom('C')])`', tests/solution_test.rs:124:5
failures:
solution_test::test_error_paren_mismatched
solution_test::test_paren_nested
solution_test::test_paren_not
solution_test::test_paren_surrounded
solution_test::test_parser_multiple_atoms_same_op
test result: FAILED. 15 passed; 5 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`