Решение на Логически изрази от Теодор Каракашев
Към профила на Теодор Каракашев
Резултати
- 19 точки от тестове
- 2 бонус точки
- 21 точки общо
- 19 успешни тест(а)
- 1 неуспешни тест(а)
Код
use std::collections::VecDeque;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
Atom(char),
Not(Box<Expr>),
And(Vec<Expr>),
Or(Vec<Expr>),
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
True,
False,
Expr(Expr),
}
#[derive(Debug, PartialEq, Eq)]
pub enum ParseError {
UnexpectedExpr,
UnexpectedUnaryOp,
UnexpectedBinOp,
UnexpectedParen,
UnexpectedEnd,
}
pub struct SimpleExprParser {
stack: VecDeque<Expr>,
op_stack: Vec<char>,
expecting: Expecting,
}
#[derive(PartialEq, Debug)]
enum Expecting {
AtomOrUnary,
BinOpOrEnd,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
stack: VecDeque::new(),
op_stack: Vec::new(),
expecting: Expecting::AtomOrUnary,
}
}
pub fn push_atom_expr(&mut self, expr: Expr) -> Result<(), ParseError> {
if self.expecting != Expecting::AtomOrUnary {
return Err(ParseError::UnexpectedExpr);
}
self.stack.push_back(expr);
self.expecting = Expecting::BinOpOrEnd;
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if self.expecting != Expecting::AtomOrUnary {
return Err(ParseError::UnexpectedUnaryOp);
}
self.op_stack.push(op);
self.expecting = Expecting::AtomOrUnary;
}
'&' | '|' => {
if self.expecting != Expecting::BinOpOrEnd {
return Err(ParseError::UnexpectedBinOp);
}
while let Some(&last_op) = self.op_stack.last() {
if last_op == '&' || last_op == '|' {
self.apply_op()?;
} else {
break;
}
}
self.op_stack.push(op);
self.expecting = Expecting::AtomOrUnary;
}
_ => panic!("Invalid operator: {}", op),
}
Ok(())
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if self.expecting != Expecting::AtomOrUnary {
return Err(ParseError::UnexpectedExpr);
}
let mut expr = Expr::Atom(c);
while let Some('!') = self.op_stack.last() {
self.op_stack.pop();
expr = Expr::Not(Box::new(expr));
}
self.stack.push_back(expr);
self.expecting = Expecting::BinOpOrEnd;
Ok(())
}
fn apply_op(&mut self) -> Result<(), ParseError> {
if let Some(op) = self.op_stack.pop() {
match op {
'&' => {
let right = self.stack.pop_back().ok_or(ParseError::UnexpectedEnd)?;
let left = self.stack.pop_back().ok_or(ParseError::UnexpectedEnd)?;
self.stack.push_back(match (left, right) {
(Expr::And(mut left_vec), Expr::And(mut right_vec)) => {
left_vec.append(&mut right_vec);
Expr::And(left_vec)
}
(Expr::And(mut left_vec), right) => {
left_vec.push(right);
Expr::And(left_vec)
}
(left, Expr::And(mut right_vec)) => {
let mut new_vec = vec![left];
new_vec.append(&mut right_vec);
Expr::And(new_vec)
}
(left, right) => Expr::And(vec![left, right]),
});
}
'|' => {
let right = self.stack.pop_back().ok_or(ParseError::UnexpectedEnd)?;
let left = self.stack.pop_back().ok_or(ParseError::UnexpectedEnd)?;
self.stack.push_back(match (left, right) {
(Expr::Or(mut left_vec), Expr::Or(mut right_vec)) => {
left_vec.append(&mut right_vec);
Expr::Or(left_vec)
}
(Expr::Or(mut left_vec), right) => {
left_vec.push(right);
Expr::Or(left_vec)
}
(left, Expr::Or(mut right_vec)) => {
let mut new_vec = vec![left];
new_vec.append(&mut right_vec);
Expr::Or(new_vec)
}
(Expr::Or(mut left_vec), Expr::Atom(atom)) => {
left_vec.push(Expr::Atom(atom));
Expr::Or(left_vec)
}
(left, right) => Expr::Or(vec![left, right]),
});
}
'!' => {
let expr = self.stack.pop_back().ok_or(ParseError::UnexpectedEnd)?;
self.stack.push_back(Expr::Not(Box::new(expr)));
}
_ => return Err(ParseError::UnexpectedBinOp),
}
}
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
while !self.op_stack.is_empty() {
self.apply_op()?;
}
if self.stack.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
Ok(self.stack.pop_back().unwrap())
}
}
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(inner_expr) => Value::Expr(Expr::Not(Box::new(inner_expr))),
},
Expr::And(operands) => {
let mut new_operands = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::True => continue,
Value::False => return Value::False,
Value::Expr(inner_expr) => new_operands.push(inner_expr),
}
}
if new_operands.is_empty() {
Value::True
} else if new_operands.len() == 1 {
Value::Expr(new_operands.pop().unwrap())
} else {
Value::Expr(Expr::And(new_operands))
}
}
Expr::Or(operands) => {
let mut new_operands = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue,
Value::Expr(inner_expr) => new_operands.push(inner_expr),
}
}
if new_operands.is_empty() {
Value::False
} else if new_operands.len() == 1 {
Value::Expr(new_operands.pop().unwrap())
} else {
Value::Expr(Expr::Or(new_operands))
}
}
}
}
pub struct ExprParser {
expr_stack: Vec<SimpleExprParser>,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
expr_stack: vec![SimpleExprParser::new()],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser()?.push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser()?.push_op(op)
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.expr_stack.push(SimpleExprParser::new());
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
let nested_expr = self
.expr_stack
.pop()
.ok_or(ParseError::UnexpectedParen)?
.finish()?;
let parent_parser = self.current_parser()?;
parent_parser.push_atom_expr(nested_expr)?;
while let Some('!') = parent_parser.op_stack.last() {
parent_parser.op_stack.pop();
let expr = parent_parser.stack.pop_back().ok_or(ParseError::UnexpectedEnd)?;
parent_parser.stack.push_back(Expr::Not(Box::new(expr)));
}
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.expr_stack.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
self.expr_stack.pop().unwrap().finish()
}
fn current_parser(&mut self) -> Result<&mut SimpleExprParser, ParseError> {
self.expr_stack.last_mut().ok_or(ParseError::UnexpectedEnd)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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));
}
#[test]
fn test_double_negation() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_op('!');
let _ = parser.push_op('!');
let _ = parser.push_atom('A');
let expr = parser.finish().unwrap();
assert_eq!(expr, Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('A'))))));
}
#[test]
fn test_negated_and_expression() {
let mut parser = ExprParser::new();
let _ = parser.push_op('!');
let _ = parser.open_paren();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.close_paren();
let expr = parser.finish().unwrap();
assert_eq!(expr, Expr::Not(Box::new(Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]))));
}
#[test]
fn test_complex_nested_expression() {
//A | (!(B & C) | D)
let mut parser = ExprParser::new();
let _ = parser.push_atom('A');
let _ = parser.push_op('|');
let _ = parser.open_paren();
let _ = parser.push_op('!');
let _ = parser.open_paren();
let _ = parser.push_atom('B');
let _ = parser.push_op('&');
let _ = parser.push_atom('C');
let _ = parser.close_paren();
let _ = parser.push_op('|');
let _ = parser.push_atom('D');
let _ = parser.close_paren();
let expr = parser.finish().unwrap();
assert_eq!(
expr,
Expr::Or(vec![
Expr::Atom('A'),
Expr::Not(Box::new(Expr::And(vec![Expr::Atom('B'), Expr::Atom('C')]))),
Expr::Atom('D')
])
);
}
#[test]
fn test_unexpected_binary_op() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_op('&');
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
}
#[test]
fn test_unexpected_atom() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_atom('A');
assert_eq!(parser.push_atom('B'), Err(ParseError::UnexpectedExpr));
}
#[test]
fn test_unclosed_parentheses() {
let mut parser = ExprParser::new();
let _ = parser.open_paren();
let _ = parser.push_atom('A');
assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
}
#[test]
fn test_empty_expression() {
let mut parser = SimpleExprParser::new();
assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
}
#[test]
fn test_single_atom_expression() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_atom('A');
let expr = parser.finish().unwrap();
assert_eq!(expr, Expr::Atom('A'));
}
#[test]
fn test_single_negation_expression() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_op('!');
let _ = parser.push_atom('A');
let expr = parser.finish().unwrap();
assert_eq!(expr, Expr::Not(Box::new(Expr::Atom('A'))));
}
#[test]
fn test_large_nested_expression() {
let mut parser = ExprParser::new();
let _ = parser.push_op('!');
let _ = parser.open_paren();
let _ = parser.push_atom('A');
let _ = parser.push_op('|');
let _ = parser.push_atom('B');
let _ = parser.close_paren();
let _ = parser.push_op('&');
let _ = parser.open_paren();
let _ = parser.push_atom('C');
let _ = parser.push_op('|');
let _ = parser.push_atom('D');
let _ = parser.close_paren();
let expr = parser.finish().unwrap();
assert_eq!(
expr,
Expr::And(vec![
Expr::Not(Box::new(Expr::Or(vec![Expr::Atom('A'), Expr::Atom('B')]))),
Expr::Or(vec![Expr::Atom('C'), Expr::Atom('D')])
])
);
}
#[test]
fn test_same_operators_between_atoms() {
let mut parser = ExprParser::new();
let _ = parser.push_atom('A');
let _ = parser.push_op('|');
let _ = parser.push_atom('B');
let _ = parser.push_op('|');
let _ = parser.push_atom('C');
let _ = parser.push_op('|');
let _ = parser.push_atom('D');
let expr = parser.finish().unwrap();
assert_eq!(
expr,
Expr::Or(vec![Expr::Atom('A'), Expr::Atom('B'), Expr::Atom('C'), Expr::Atom('D')
])
);
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-rwhdtl/solution)
warning: unreachable pattern
--> src/lib.rs:144:25
|
144 | (Expr::Or(mut left_vec), Expr::Atom(atom)) => {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unreachable_patterns)]` on by default
warning: `solution` (lib) generated 1 warning
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.72s
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 ... ok
test solution_test::test_paren_not ... ok
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 ... 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
failures:
solution_test::test_error_paren_mismatched
test result: FAILED. 19 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`