Решение на Логически изрази от Васил Тодоров
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 6 неуспешни тест(а)
Код
#[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 {
stack: Vec<Expr>,
pending_op: Option<char>,
negate_count: usize,
next_atom: bool,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
stack: Vec::new(),
pending_op: None,
negate_count: 0,
next_atom: true,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if !self.next_atom {
return Err(ParseError::UnexpectedExpr);
}
self.next_atom = false;
let mut new_expr = Expr::Atom(c);
for _ in 0..self.negate_count {
new_expr = Expr::Not(Box::new(new_expr));
}
self.negate_count = 0;
if let Some(op) = self.pending_op.take() {
if self.stack.is_empty() {
return Err(ParseError::UnexpectedBinOp);
}
let left = self.stack.pop().unwrap();
let combined_expr = match op {
'&' => Expr::And(vec![left, new_expr]),
'|' => Expr::Or(vec![left, new_expr]),
_ => unreachable!(),
};
self.stack.push(combined_expr);
} else {
self.stack.push(new_expr);
}
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
self.negate_count += 1;
Ok(())
}
'&' | '|' => {
self.next_atom = true;
if self.pending_op.is_some() {
return Err(ParseError::UnexpectedBinOp);
}
if self.negate_count > 0 {
return Err(ParseError::UnexpectedUnaryOp);
}
self.pending_op = Some(op);
Ok(())
}
_ => Err(ParseError::UnexpectedExpr),
}
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.pending_op.is_some() || self.negate_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
if self.stack.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
let expr = self.stack.pop().unwrap();
Ok(Self::simplify(expr))
}
fn simplify(expr: Expr) -> Expr {
match expr {
Expr::And(mut items) => {
let mut simplified = Vec::new();
for item in items.drain(..) {
match Self::simplify(item) {
Expr::And(inner) => simplified.extend(inner),
other => simplified.push(other),
}
}
Expr::And(simplified)
}
Expr::Or(mut items) => {
let mut simplified = Vec::new();
for item in items.drain(..) {
match Self::simplify(item) {
Expr::Or(inner) => simplified.extend(inner),
other => simplified.push(other),
}
}
Expr::Or(simplified)
}
Expr::Not(inner) => Expr::Not(Box::new(Self::simplify(*inner))),
other => other,
}
}
}
//имплементирах този парсер по различен начин от симпл, защото смених логиката,
//не успях да имплементирам го по същия начин. Сега работи със два стека(за атоми и операции)
//(нареках ги опашки, после разбрах че е по-скоро стек който обръщам)
pub struct ExprParser {
atom_queue: Vec<Expr>,
op_queue: Vec<char>,
paren_balance: i32,
expect_atom: bool,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
atom_queue: Vec::new(),
op_queue: Vec::new(),
paren_balance: 0,
expect_atom: true,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if !self.expect_atom {
return Err(ParseError::UnexpectedExpr);
}
if c == '|' || c == '&' || c == '(' || c == ')' || c == ' '{
return Err(ParseError::UnexpectedExpr);
}
self.atom_queue.push(Expr::Atom(c));
self.expect_atom = false;
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
if op == '(' || op == ')' {
return Err(ParseError::UnexpectedParen);
}
if self.expect_atom && op != '!' {
return Err(ParseError::UnexpectedBinOp);
}
if !self.expect_atom && op == '!' {
return Err(ParseError::UnexpectedUnaryOp);
}
self.op_queue.push(op);
if op != '!' {
self.expect_atom = true;
}
Ok(())
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if !self.expect_atom{
return Err(ParseError::UnexpectedParen);
}
self.op_queue.push('(');
self.paren_balance += 1;
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.paren_balance <= 0 {
return Err(ParseError::UnexpectedParen);
}
self.op_queue.push(')');
self.paren_balance -= 1;
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.paren_balance != 0 {
return Err(ParseError::UnexpectedEnd);
}
Self::finish_help(&mut self.atom_queue, &mut self.op_queue)
}
fn finish_help(atom_queue: &mut Vec<Expr>, op_queue: &mut Vec<char>) -> Result<Expr, ParseError> {
while let Some(op) = op_queue.first() {
match *op {
'!' => {
op_queue.remove(0);
if let Some(atom) = atom_queue.pop() {
let expr = Expr::Not(Box::new(atom));
atom_queue.push(expr);
}
}
'&' | '|' => {
let is_and = if *op == '&' {
1
} else {
0
};
let mut count = 0;
while op_queue.get(count) == Some(&op) {
count += 1;
}
let mut exprs: Vec<Expr> = atom_queue.drain(0..=(count - 1)).collect();
while let Some(next_op) = op_queue.first() {
match *next_op {
'!' => {
op_queue.remove(0);
if let Some(atom) = atom_queue.pop() {
let expr = Expr::Not(Box::new(atom));
atom_queue.push(expr);
}
}
'&' | '|' => {
if count > 0 {
op_queue.remove(0);
count -= 1;
} else {
break;
}
}
'(' => {
op_queue.remove(0);
let mut sub_atoms = Vec::new();
let mut sub_ops = Vec::new();
let mut balance = 1;
while balance > 0 {
if let Some(op1) = op_queue.first() {
match *op1 {
'(' => {
balance += 1;
sub_ops.push(op_queue.remove(0));
}
')' => {
balance -= 1;
if balance > 0 {
sub_ops.push(op_queue.remove(0));
} else {
op_queue.remove(0);
}
}
_ => sub_ops.push(op_queue.remove(0)),
}
}
if let Some(_atom) = atom_queue.first() {
sub_atoms.push(atom_queue.remove(0));
}
}
let sub_expr = Self::finish_help(&mut sub_atoms, &mut sub_ops)?;
atom_queue.push(sub_expr);
}
_ => {}
}
}
exprs.push(atom_queue.remove(0));
let combined_expr = if is_and == 1 {
Expr::And(exprs)
} else {
Expr::Or(exprs)
};
atom_queue.insert(0, combined_expr);
}
'(' => {
op_queue.remove(0);
let mut sub_atoms = Vec::new();
let mut sub_ops = Vec::new();
let mut balance = 1;
while balance > 0 {
if let Some(op) = op_queue.first() {
match *op {
'(' => {
balance += 1;
sub_ops.push(op_queue.remove(0));
}
')' => {
balance -= 1;
if balance > 0 {
sub_ops.push(op_queue.remove(0));
} else {
op_queue.remove(0);
}
}
_ => sub_ops.push(op_queue.remove(0)),
}
}
if let Some(_atom) = atom_queue.first() {
sub_atoms.push(atom_queue.remove(0));
}
}
let sub_expr = Self::finish_help(&mut sub_atoms, &mut sub_ops)?;
atom_queue.push(sub_expr);
}
_ => {}
}
}
if atom_queue.len() == 1 {
Ok(atom_queue.remove(0))
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
True,
False,
Expr(Expr),
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
match eval_help(expr, truthy, falsy) {
Value::Expr(e) => Value::Expr(e),
other => other,
}
}
fn eval_help(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::Atom(*c))
}
}
Expr::Not(inner) => match eval_help(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(inner_expr) => {
let mut depth = 1;
let mut current = inner_expr;
while let Expr::Not(next_inner) = current {
depth += 1;
current = *next_inner;
}
if depth % 2 == 0 {
eval_help(¤t, truthy, falsy)
} else {
Value::Expr(Expr::Not(Box::new(current.clone())))
}
}
},
Expr::Or(items) => {
let mut new_items = Vec::new();
for item in items {
match eval_help(item, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue,
Value::Expr(e) => new_items.push(e),
}
}
match new_items.len() {
0 => Value::False,
1 => eval_help(&new_items[0], truthy, falsy),
_ => Value::Expr(Expr::Or(new_items)),
}
}
Expr::And(items) => {
let mut new_items = Vec::new();
for item in items {
match eval_help(item, truthy, falsy) {
Value::False => return Value::False,
Value::True => continue,
Value::Expr(e) => new_items.push(e),
}
}
match new_items.len() {
0 => Value::True,
1 => eval_help(&new_items[0], truthy, falsy),
_ => Value::Expr(Expr::And(new_items)),
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-hz6yt8/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.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 ... 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 ... FAILED
test solution_test::test_paren_nested ... FAILED
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 ... 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.close_paren(), Err(_))', tests/solution_test.rs:331: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_expr_priority stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `And([Atom('X'), Or([Atom('A'), Atom('B')])])`,
right: `And([Or([Atom('A'), Atom('B')]), Atom('X')])`', tests/solution_test.rs:207:9
thread 'solution_test::test_paren_expr_priority' panicked at 'assertion failed: `(left == right)`
left: `And([Atom('X'), Or([Atom('A'), Atom('B')])])`,
right: `And([Or([Atom('A'), Atom('B')]), Atom('X')])`', tests/solution_test.rs:197:5
---- solution_test::test_paren_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `And([Atom('A'), And([Atom('B'), And([Atom('C'), Not(Not(Not(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([Atom('A'), And([Atom('B'), And([Atom('C'), Not(Not(Not(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([Atom('A'), Not(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([Atom('A'), Not(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([Or([Or([Atom('X'), Atom('C')]), And([Atom('A'), Atom('B')])]), And([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'), Atom('C')]), And([Atom('A'), Atom('B')])]), And([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_errors_basic stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.push_op(\'&\'), Err(_))', tests/solution_test.rs:267: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_expr_priority
solution_test::test_paren_nested
solution_test::test_paren_not
solution_test::test_paren_surrounded
solution_test::test_parser_errors_basic
test result: FAILED. 14 passed; 6 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`