Решение на Логически изрази от Габриела Димитрова

Обратно към всички решения

Към профила на Габриела Димитрова

Код

#[derive(Clone, Debug, PartialEq, Eq)]

pub enum Expr {

Atom(char),

Not(Box<Expr>),

And(Vec<Expr>),

Or(Vec<Expr>),

}

impl Expr {

fn to_string(&self) -> String {

format!("{:?}", self)

}

fn flatten(self) -> Expr {

match self {

Expr::And(mut sub_exprs) => {

let mut flattened = Vec::new();

for sub_expr in sub_exprs.drain(..) {

match sub_expr.flatten() {

Expr::And(mut inner) => flattened.extend(inner.drain(..)),

other => flattened.push(other),

}

}

Expr::And(flattened)

}

Expr::Or(mut sub_exprs) => {

let mut flattened = Vec::new();

for sub_expr in sub_exprs.drain(..) {

match sub_expr.flatten() {

Expr::Or(mut inner) => flattened.extend(inner.drain(..)),

other => flattened.push(other),

}

}

Expr::Or(flattened)

}

other => other,

}

}

}

#[derive(Debug, PartialEq, Eq)]

pub enum ParseError {

UnexpectedExpr,

UnexpectedUnaryOp,

UnexpectedBinOp,

UnexpectedParen,

UnexpectedEnd,

}

pub struct SimpleExprParser {

current_expr: Option<Expr>,

current_op: Option<char>,

negation_stack: usize,

}

impl SimpleExprParser {

pub fn new() -> SimpleExprParser {

SimpleExprParser {

current_expr: None,

current_op: None,

negation_stack: 0,

}

}

pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {

if self.current_op.is_none() && self.current_expr.is_some() {

return Err(ParseError::UnexpectedExpr);

}

let mut expr = Expr::Atom(c);

for _ in 0..self.negation_stack {

expr = Expr::Not(Box::new(expr));

}

if let Some(op) = self.current_op.take() {

match op {

'&' => {

if let Some(existing_expr) = self.current_expr.take() {

let and_expr = vec![existing_expr, expr];

self.current_expr = Some(Expr::And(and_expr));

} else {

return Err(ParseError::UnexpectedExpr);

}

}

'|' => {

if let Some(existing_expr) = self.current_expr.take() {

let or_expr = vec![existing_expr, expr];

self.current_expr = Some(Expr::Or(or_expr));

} else {

return Err(ParseError::UnexpectedExpr);

}

}

_ => return Err(ParseError::UnexpectedBinOp),

}

} else {

self.current_expr = Some(expr);

}

self.negation_stack = 0;

Ok(())

}

pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {

match op {

'&' | '|' => {

if self.current_op.is_some() {

return Err(ParseError::UnexpectedBinOp);

}

if self.current_expr.is_none() {

return Err(ParseError::UnexpectedBinOp);

}

self.current_op = Some(op);

}

'!' => {

self.negation_stack += 1;

}

_ => panic!("Unsupported operator: {}", op),

}

Ok(())

}

pub fn finish(self) -> Result<Expr, ParseError> {

if let Some(expr) = self.current_expr {

Ok(expr.flatten())

} else {

Err(ParseError::UnexpectedEnd)

}

}

}

pub struct ExprParser {

stack: Vec<Expr>,

operators: Vec<char>,

parens: Vec<usize>,

}

impl ExprParser {

pub fn new() -> ExprParser {

ExprParser {

stack: Vec::new(),

operators: Vec::new(),

parens: Vec::new(),

}

}

pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {

if !c.is_alphabetic() {

panic!("Invalid atom: {}", c);

}

if let Some('!') = self.operators.last() {

// Apply negation on the atom (we push it with negation)

self.operators.pop();

self.stack.push(Expr::Not(Box::new(Expr::Atom(c))));

} else {

// Just push the atom normally

self.stack.push(Expr::Atom(c));

}

Ok(())

}

pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {

if !matches!(op, '&' | '|' | '!') {

panic!("Invalid operator: {}", op);

}

// Handling negation (highest precedence) operator

if op == '!' {

self.operators.push(op);

} else {

// For '&' and '|', resolve operators based on precedence

while let Some(&top_op) = self.operators.last() {

if top_op == '!' || top_op == op {

break;

}

self.resolve_operator()?; // Resolve the operator

}

self.operators.push(op);

}

Ok(())

}

pub fn open_paren(&mut self) -> Result<(), ParseError> {

self.parens.push(self.operators.len());

self.parens.push(self.stack.len());

Ok(())

}

pub fn close_paren(&mut self) -> Result<(), ParseError> {

if self.parens.is_empty() {

return Err(ParseError::UnexpectedParen);

}

let stack_start = self.parens.pop().unwrap();

let operator_start = self.parens.pop().unwrap();

while self.operators.len() > operator_start {

self.resolve_operator()?;

}

let group = self.stack.split_off(stack_start);

if group.len() == 1 {

self.stack.push(group.into_iter().next().unwrap());

} else {

return Err(ParseError::UnexpectedExpr);

}

Ok(())

}

pub fn finish(mut self) -> Result<Expr, ParseError> {

while !self.operators.is_empty() {

self.resolve_operator()?;

}

if self.stack.len() != 1 {

return Err(ParseError::UnexpectedEnd);

}

Ok(self.stack.pop().unwrap().flatten())

}

fn resolve_operator(&mut self) -> Result<(), ParseError> {

if let Some(op) = self.operators.pop() {

if op == '!' {

// Apply negation to the last expression in the stack

let expr = self.stack.pop().ok_or(ParseError::UnexpectedUnaryOp)?;

self.stack.push(Expr::Not(Box::new(expr)));

} else {

// For binary operators ('&', '|'), we pop two expressions and combine them

let right = self.stack.pop().ok_or(ParseError::UnexpectedBinOp)?;

let left = self.stack.pop().ok_or(ParseError::UnexpectedBinOp)?;

let expr = match op {

'&' => Expr::And(vec![left, right]),

'|' => Expr::Or(vec![left, right]),

_ => unreachable!(),

};

self.stack.push(expr);

}

} else {

unreachable!("resolve_operator called with no operators left");

}

Ok(())

}

}

#[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::And(exprs) => {

for sub_expr in exprs {

match eval(sub_expr, truthy, falsy) {

Value::False => return Value::False,

Value::Expr(_) => return Value::Expr(Expr::And(exprs.clone())),

_ => continue,

}

}

Value::True

}

Expr::Or(exprs) => {

for sub_expr in exprs {

match eval(sub_expr, truthy, falsy) {

Value::True => return Value::True,

Value::Expr(_) => return Value::Expr(Expr::Or(exprs.clone())),

_ => continue,

}

}

Value::False

}

Expr::Not(sub_expr) => match eval(sub_expr, truthy, falsy) {

Value::True => Value::False,

Value::False => Value::True,

Value::Expr(_) => Value::Expr(expr.clone()),

},

}

}

//

// expr!(atom('A')),

// expr!(not(atom('A'))),

// expr!(and(atom('A'), atom('B'), atom('C'))),

// expr!(or(atom('A'), atom('B'), atom('C'))),

// expr!(not(and(atom('A'), atom('B')))),

// expr!(not(or(atom('A'), atom('B')))),

// expr!(or(and(atom('A'), atom('B')), and(atom('C'), atom('D')))),

// // и т.н.

#[cfg(test)]

mod tests {

use super::*; //

/*#[test]

fn invalid_expression() {

todo!();

}*/

#[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_simple_parser_priority() {

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 expr = parser.finish().unwrap();

assert_eq!(expr.to_string(), "And([Or([Atom('A'), Atom('B')]), Atom('C')])");

println!("{:?}", expr);

}

#[test]

fn test_expr_parser_priority() {

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 expr = parser.finish().unwrap();

assert_eq!(expr.to_string(), "And([Or([Atom('A'), Atom('B')]), Atom('C')])");

println!("{:?}", expr);

}

#[test]

fn test_simple_parser_correct() {

let mut simple_parser = SimpleExprParser::new();

let _ = simple_parser.push_op('!');

let _ = simple_parser.push_op('!');

let _ = simple_parser.push_op('!');

let _ = simple_parser.push_atom('A');

let _ = simple_parser.push_op('&');

let _ = simple_parser.push_atom('B');

let expr = simple_parser.finish().unwrap();

println!("{:?}", expr);

}

#[test]

fn test_expr_parser_correct() {

let mut parser = ExprParser::new();

// let _ = parser.push_op('!');

// let _ = parser.push_op('!');

// let _ = parser.push_op('!');

let _ = parser.push_atom('γ');

let _ = parser.push_op('|');

let _ = parser.open_paren();

let _ = parser.push_atom('α');

let _ = parser.push_op('|');

let _ = parser.push_atom('ß');

let _ = parser.close_paren();

let expr = parser.finish().unwrap();

println!("{:?}", expr);

}

#[test]

fn test_expr_brackets() {

let mut parser = ExprParser::new();

let _ = parser.push_atom('γ');

let _ = parser.push_op('|');

let _ = parser.open_paren();

let _ = parser.push_atom('α');

let _ = parser.push_op('&');

let _ = parser.push_atom('ß');

let _ = parser.close_paren();

let expr = parser.finish().unwrap();

assert_eq!(expr.to_string(), "And([Or([Atom('γ'), Atom('α')]), Atom('ß')])");

println!("{:?}", expr);

}

#[test]

fn test_simple_parser_flatten() {

// A | B & C & D

// And([Or([Atom('A'), Atom('B')]), Atom('C'), Atom('D')])

let mut simple_parser = SimpleExprParser::new();

let _ = simple_parser.push_atom('A');

let _ = simple_parser.push_op('|');

let _ = simple_parser.push_atom('B');

let _ = simple_parser.push_op('&');

let _ = simple_parser.push_atom('C');

let _ = simple_parser.push_op('&');

let _ = simple_parser.push_atom('D');

let expr = simple_parser.finish().unwrap();

println!("{:?}", expr);

}

#[test]

fn test_expr_parser_flatten() {

// A | B & C & D

// And([Or([Atom('A'), Atom('B')]), Atom('C'), Atom('D')])

let mut simple_parser = SimpleExprParser::new();

let _ = simple_parser.push_atom('A');

let _ = simple_parser.push_op('|');

let _ = simple_parser.push_atom('B');

let _ = simple_parser.push_op('&');

let _ = simple_parser.push_atom('C');

let _ = simple_parser.push_op('&');

let _ = simple_parser.push_atom('D');

let expr = simple_parser.finish().unwrap();

println!("{:?}", expr);

}

#[test]

fn test_eval() {

// A & B | !C

// (((A & B) | (!C)) | D)

// Or([And([Atom('A'), Atom('B')]), Not(Atom('C')), Atom('D')])

let mut simple_parser = SimpleExprParser::new();

let _ = simple_parser.push_atom('A');

let _ = simple_parser.push_op('&');

let _ = simple_parser.push_atom('B');

let _ = simple_parser.push_op('|');

let _ = simple_parser.push_op('!');

let _ = simple_parser.push_atom('C');

let _ = simple_parser.push_op('|');

let _ = simple_parser.push_atom('D');

let expr = simple_parser.finish().unwrap();

let val = eval(&expr, &['A', 'C'], &['B', 'D']); // False

println!("{:?}", expr);

println!("{:?}", val);

}

#[test]

fn test_eval_brackets() {

let mut parser = ExprParser::new();

let _ = parser.push_atom('A');

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 expr = parser.finish().unwrap();

let val = eval(&expr, &['A', 'B', 'C'], &[]); // True

println!("{:?}", expr);

println!("{:?}", val);

}

#[test]

fn test_expr_parser_negation() {

let mut parser = ExprParser::new();

let _ = parser.push_atom('B');

let _ = parser.push_op('|');

let _ = parser.push_op('!');

let _ = parser.push_op('!');

let _ = parser.push_atom('A');

let expr = parser.finish().unwrap();

println!("{:?}", expr);

}

}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20241224-258381-13dl3u8/solution)
warning: associated function `to_string` is never used
  --> src/lib.rs:10:8
   |
10 |     fn to_string(&self) -> String {
   |        ^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` 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.78s
     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 ... FAILED
test solution_test::test_eval_unwrap_and_or ... FAILED
test solution_test::test_eval_unwrap_nested ... FAILED
test solution_test::test_paren_around_expr ... ok
test solution_test::test_paren_expr_priority ... FAILED
test solution_test::test_paren_not ... FAILED
test solution_test::test_paren_nested ... FAILED
test solution_test::test_paren_surrounded ... FAILED
test solution_test::test_parser_alternating_ops ... ok
test solution_test::test_parser_atom ... ok
test solution_test::test_parser_and_or ... ok
test solution_test::test_parser_error_unexpected_end ... FAILED
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.finish(), Err(_))', tests/solution_test.rs:351: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_partial stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(And([Atom('A'), Atom('B'), Atom('C')]))`,
 right: `Expr(And([Atom('A'), Atom('C')]))`', tests/solution_test.rs:416:9
thread 'solution_test::test_eval_partial' panicked at 'assertion failed: `(left == right)`
  left: `Expr(And([Atom('A'), Atom('B'), Atom('C')]))`,
 right: `Expr(And([Atom('A'), Atom('C')]))`', tests/solution_test.rs:409:5

---- solution_test::test_eval_unwrap_and_or stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(And([Atom('A'), Atom('B'), Atom('C')]))`,
 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('A'), Atom('B'), Atom('C')]))`,
 right: `Expr(Atom('B'))`', tests/solution_test.rs:456:5

---- solution_test::test_eval_unwrap_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Or([Atom('X'), And([Atom('A'), Atom('B')]), Not(And([Atom('C'), 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('A'), Atom('B')]), Not(And([Atom('C'), 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_paren_expr_priority stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `And([Or([Atom('X'), Atom('A')]), Atom('B')])`,
 right: `Or([Atom('X'), And([Atom('A'), Atom('B')])])`', tests/solution_test.rs:200:9
thread 'solution_test::test_paren_expr_priority' panicked at 'assertion failed: `(left == right)`
  left: `And([Or([Atom('X'), Atom('A')]), Atom('B')])`,
 right: `Or([Atom('X'), And([Atom('A'), Atom('B')])])`', tests/solution_test.rs:197:5

---- solution_test::test_paren_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Or([And([Atom('X'), 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: `Or([And([Atom('X'), 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_nested stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedExpr', tests/solution_test.rs:254:58
thread 'solution_test::test_paren_nested' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedExpr', tests/solution_test.rs:252:5

---- solution_test::test_paren_surrounded stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Or([And([Or([And([Or([Atom('X'), Atom('A')]), Atom('B')]), 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([And([Or([And([Or([Atom('X'), Atom('A')]), Atom('B')]), 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_error_unexpected_end stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.finish(), Err(_))', tests/solution_test.rs:311:9
thread 'solution_test::test_parser_error_unexpected_end' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:305: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_eval_partial
    solution_test::test_eval_unwrap_and_or
    solution_test::test_eval_unwrap_nested
    solution_test::test_paren_expr_priority
    solution_test::test_paren_nested
    solution_test::test_paren_not
    solution_test::test_paren_surrounded
    solution_test::test_parser_error_unexpected_end
    solution_test::test_parser_errors_basic

test result: FAILED. 10 passed; 10 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

error: test failed, to rerun pass `--test solution_test`

История (6 версии и 0 коментара)