Решение на Логически изрази от Ангел Пенчев
Резултати
- 12 точки от тестове
- 1 бонус точка
- 13 точки общо
- 12 успешни тест(а)
- 8 неуспешни тест(а)
Код
#[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,
}
/// Parser for a simple expression, which does not contain parentheses.
#[derive(Clone)]
pub struct SimpleExprParser {
atom_stack: Vec<Expr>,
operator_stack: Vec<char>,
next_is_atom: bool,
}
impl Default for SimpleExprParser {
fn default() -> Self {
Self::new()
}
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
Self {
atom_stack: vec![],
operator_stack: vec![],
next_is_atom: true,
}
}
/// Accepts an atom.
///
/// `c` should be a valid atom character, i.e. 'A'-'Z'.
/// Otherwise the function will panic.
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
// Check if the next token should be an atom
if !self.next_is_atom {
return Err(ParseError::UnexpectedExpr);
}
// Check if the atom is a valid character
if !('A'..).contains(&c) {
return Err(ParseError::UnexpectedExpr);
}
// Add the atom to the stack and set the next token to be an operator
self.atom_stack.push(Expr::Atom(c));
self.next_is_atom = false;
Ok(())
}
/// Accepts an operator.
///
/// `op` should be one of '&', '|', '!'.
/// Otherwise the function will panic.
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
// Check if the next token should be an operator
if self.next_is_atom && op != '!' {
return Err(ParseError::UnexpectedBinOp);
}
if !self.next_is_atom && op == '!' {
return Err(ParseError::UnexpectedUnaryOp);
}
// Check if the operator is valid
if !['&', '|', '!'].contains(&op) {
return Err(ParseError::UnexpectedBinOp);
}
// Add the operator to the operator stack
match op {
'!' => {
if !self.next_is_atom {
return Err(ParseError::UnexpectedUnaryOp);
}
self.operator_stack.push('!');
}
'&' | '|' => {
if self.next_is_atom {
return Err(ParseError::UnexpectedBinOp);
}
while let Some(&prev_op) = self.operator_stack.last() {
if prev_op == '&' || prev_op == '|' {
self.pop_operator()?;
} else {
break;
}
}
self.operator_stack.push(op);
self.next_is_atom = true;
}
_ => panic!("Invalid operator"),
}
Ok(())
}
/// Pushes an entire expression as if it were an atom.
/// Required for handling parentheses in the full expression parser.
pub fn push_atom_expr(&mut self, expr: Expr) -> Result<(), ParseError> {
if !self.next_is_atom {
return Err(ParseError::UnexpectedExpr);
}
self.atom_stack.push(expr);
self.next_is_atom = false;
Ok(())
}
/// Completes the parsing and returns the built expression.
pub fn finish(&mut self) -> Result<Expr, ParseError> {
while self.operator_stack.last().is_some() {
let _ = self.pop_operator();
}
if self.atom_stack.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
Ok(self.atom_stack.pop().unwrap())
}
/// Pops the top operator from the operator stack and applies it to the top atoms.
fn pop_operator(&mut self) -> Result<(), ParseError> {
let op = self.operator_stack.pop().unwrap();
match op {
'!' => {
if let Some(expr) = self.atom_stack.pop() {
self.atom_stack.push(Expr::Not(Box::new(expr)));
} else {
return Err(ParseError::UnexpectedUnaryOp);
}
}
'&' | '|' => {
let mut args = Vec::new();
while let Some(expr) = self.atom_stack.pop() {
args.push(expr);
if matches!(self.operator_stack.last(), Some(&next_op) if next_op != op) {
break;
}
}
if args.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
args.reverse();
let combined = if op == '&' {
Expr::And(args)
} else {
Expr::Or(args)
};
self.atom_stack.push(combined);
}
_ => panic!("Invalid operator"),
}
Ok(())
}
}
/// Parser for a full expression, which may contain parentheses.
pub struct ExprParser {
simple_parsers: Vec<SimpleExprParser>,
current_parser: SimpleExprParser,
}
impl Default for ExprParser {
fn default() -> Self {
Self::new()
}
}
impl ExprParser {
pub fn new() -> ExprParser {
Self {
simple_parsers: vec![],
current_parser: SimpleExprParser::new(),
}
}
/// Accepts an atom.
///
/// `c` should be a valid atom character, i.e. 'A'-'Z'.
/// Otherwise the function will panic.
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser.push_atom(c)
}
/// Accepts an operator.
///
/// `op` should be one of '&', '|', '!'.
/// Otherwise the function will panic.
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser.push_op(op)
}
/// Accepts a starting parenthesis.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
// Save the current parser state and start a new one for the expression with-in the parentheses.
let new_parser = SimpleExprParser::new();
let old_parser_clone = self.current_parser.clone();
self.simple_parsers.push(old_parser_clone);
self.current_parser = new_parser;
Ok(())
}
/// Accepts a closing parenthesis.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
// Check if there is an open parenthesis to close.
if self.simple_parsers.is_empty() {
return Err(ParseError::UnexpectedParen);
}
// Check if the current parser has anything within the parentheses.
if self.current_parser.atom_stack.is_empty() {
return Err(ParseError::UnexpectedParen);
}
// Finish the current parser to get the inner expression.
let inner_expr = self.current_parser.finish()?; // propagate the error
// Restore the previous parser state.
match self.simple_parsers.pop() {
Some(previous_parser) => {
self.current_parser = previous_parser;
let _ = self.current_parser.push_atom_expr(inner_expr);
}
None => {
return Err(ParseError::UnexpectedParen);
}
}
Ok(())
}
/// Accepts an expression that is already parsed.
pub fn finish(mut self) -> Result<Expr, ParseError> {
// Close parentheses if there are any left open.
if self.simple_parsers.pop().is_some() {
return Err(ParseError::UnexpectedEnd);
}
// Complete the current parser and return the expression.
self.current_parser.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(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(args) => {
let mut expressions = Vec::new();
for arg in args {
match eval(arg, truthy, falsy) {
Value::True => {} // True doesn't affect the result of an AND expression
Value::False => return Value::False, // If any of the expressions is false, the result is false
Value::Expr(inner_expr) => expressions.push(inner_expr),
}
}
if expressions.is_empty() {
// All of the expressions were evaluated to true
Value::True
} else {
Value::Expr(Expr::And(expressions))
}
}
Expr::Or(args) => {
let mut expressions = Vec::new();
for arg in args {
match eval(arg, truthy, falsy) {
Value::True => return Value::True, // If any of the expressions is true, the result is true
Value::False => {} // False doesn't affect the result of an OR expression
Value::Expr(inner_expr) => expressions.push(inner_expr),
}
}
if expressions.is_empty() {
// All of the expressions were evaluated to false
Value::False
} else {
Value::Expr(Expr::Or(expressions))
}
}
}
}
#[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_parentheses() {
// A & (B | !C) | D
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 _ = full_parser.push_op('|');
let _ = full_parser.push_atom('D');
let expr = full_parser.finish().unwrap();
let result = eval(&expr, &['A', 'C', 'D'], &['B']);
assert_eq!(result, Value::True);
}
#[test]
fn test_triple_negation() {
// !!!A
let mut full_parser = ExprParser::new();
let _ = full_parser.push_op('!');
let _ = full_parser.push_op('!');
let _ = full_parser.push_op('!');
let _ = full_parser.push_atom('A');
let expr = full_parser.finish().unwrap();
let result = eval(&expr, &['A'], &['B']);
assert_eq!(result, Value::False);
}
#[test]
fn test_empty_paranteses() {
// A & ()
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let _ = full_parser.push_op('&');
let _ = full_parser.open_paren();
let err = full_parser.close_paren();
assert_eq!(err, Err(ParseError::UnexpectedParen));
}
#[test]
fn test_no_opening_paranteses() {
// A & B)
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('B');
let err = full_parser.close_paren();
assert_eq!(err, Err(ParseError::UnexpectedParen));
}
#[test]
fn test_nested_paranteses_left() {
// A & (B & (C & (D & (E & F))))
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.open_paren();
let _ = full_parser.push_atom('C');
let _ = full_parser.push_op('&');
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('D');
let _ = full_parser.push_op('&');
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('E');
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('F');
let _ = full_parser.close_paren();
let _ = full_parser.close_paren();
let _ = full_parser.close_paren();
let _ = full_parser.close_paren();
let expr = full_parser.finish().unwrap();
let result1 = eval(&expr, &['A', 'B', 'C', 'D', 'E', 'F'], &[]);
assert_eq!(result1, Value::True);
let result2 = eval(&expr, &['A', 'B', 'C', 'D', 'E'], &['F']);
assert_eq!(result2, Value::False);
}
#[test]
fn test_nested_paranteses_right() {
// (((((A & B) & C) & D) & E) & F)
let mut full_parser = ExprParser::new();
let _ = full_parser.open_paren();
let _ = full_parser.open_paren();
let _ = full_parser.open_paren();
let _ = full_parser.open_paren();
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('A');
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('B');
let _ = full_parser.close_paren();
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('C');
let _ = full_parser.close_paren();
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('D');
let _ = full_parser.close_paren();
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('E');
let _ = full_parser.close_paren();
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('F');
let _ = full_parser.close_paren();
let expr = full_parser.finish().unwrap();
let result1 = eval(&expr, &['A', 'B', 'C', 'D', 'E', 'F'], &[]);
assert_eq!(result1, Value::True);
let result2 = eval(&expr, &['A', 'B', 'C', 'D', 'E'], &['F']);
assert_eq!(result2, Value::False);
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-2mq559/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.73s
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 ... FAILED
test solution_test::test_eval_unwrap_and_or ... FAILED
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 ... FAILED
test solution_test::test_paren_surrounded ... FAILED
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 ... FAILED
test solution_test::test_parser_multiple_atoms_same_op ... FAILED
test solution_test::test_parser_multiple_not ... FAILED
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_eval_unwrap_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Expr(Or([Atom('X'), And([Atom('B')]), Not(And([Atom('D')])), Atom('Y')]))`,
right: `Expr(Or([Atom('X'), Atom('B'), Not(Atom('D')), Atom('Y')]))`', tests/solution_test.rs:480:9
thread 'solution_test::test_eval_unwrap_nested' panicked at 'assertion failed: `(left == right)`
left: `Expr(Or([Atom('X'), And([Atom('B')]), Not(And([Atom('D')])), Atom('Y')]))`,
right: `Expr(Or([Atom('X'), Atom('B'), Not(Atom('D')), Atom('Y')]))`', tests/solution_test.rs:479:5
---- solution_test::test_eval_unwrap_and_or stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Expr(And([Atom('B')]))`,
right: `Expr(Atom('B'))`', tests/solution_test.rs:457:9
thread 'solution_test::test_eval_unwrap_and_or' panicked at 'assertion failed: `(left == right)`
left: `Expr(And([Atom('B')]))`,
right: `Expr(Atom('B'))`', tests/solution_test.rs:456:5
---- solution_test::test_paren_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(Or([Atom('A'), Atom('B')]))`,
right: `Or([Not(Or([Atom('A'), Atom('B')])), Atom('X')])`', tests/solution_test.rs:226:9
thread 'solution_test::test_paren_not' panicked at 'assertion failed: `(left == right)`
left: `Not(Or([Atom('A'), Atom('B')]))`,
right: `Or([Not(Or([Atom('A'), Atom('B')])), Atom('X')])`', tests/solution_test.rs:216:5
---- solution_test::test_paren_surrounded stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Or([Or([Or([Atom('X'), 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([Or([Or([Atom('X'), 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_expr_and_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(Atom('A'))`,
right: `Or([Not(Atom('A')), Atom('B')])`', tests/solution_test.rs:114:9
thread 'solution_test::test_parser_expr_and_not' panicked at 'assertion failed: `(left == right)`
left: `Not(Atom('A'))`,
right: `Or([Not(Atom('A')), Atom('B')])`', tests/solution_test.rs:107:5
---- solution_test::test_parser_multiple_atoms_same_op stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `And([And([Atom('A'), 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([And([Atom('A'), Atom('B')]), Atom('C')])`,
right: `And([Atom('A'), Atom('B'), Atom('C')])`', tests/solution_test.rs:124:5
---- solution_test::test_parser_multiple_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Not(Not(Atom('A')))`,
right: `Or([Not(Not(Atom('A'))), Atom('B')])`', tests/solution_test.rs:151:9
thread 'solution_test::test_parser_multiple_not' panicked at 'assertion failed: `(left == right)`
left: `Not(Not(Atom('A')))`,
right: `Or([Not(Not(Atom('A'))), Atom('B')])`', tests/solution_test.rs:140:5
failures:
solution_test::test_error_paren_mismatched
solution_test::test_eval_unwrap_and_or
solution_test::test_eval_unwrap_nested
solution_test::test_paren_not
solution_test::test_paren_surrounded
solution_test::test_parser_expr_and_not
solution_test::test_parser_multiple_atoms_same_op
solution_test::test_parser_multiple_not
test result: FAILED. 12 passed; 8 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`