Решение на Логически изрази от Валентин Каров
Резултати
- 10 точки от тестове
- 0 бонус точки
- 10 точки общо
- 10 успешни тест(а)
- 10 неуспешни тест(а)
Код
#[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),
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Token {
Atom(char),
Negation,
Conjunction,
Disjunction,
OpeningBracket,
ClosingBracket,
}
pub struct Tokenizer {
tokens: Vec<Token>,
}
impl Tokenizer {
pub fn new() -> Tokenizer {
Tokenizer { tokens: Vec::new() }
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if !c.is_ascii_uppercase() {
return Err(ParseError::UnexpectedExpr);
}
if self.tokens.last() != None {
match self.tokens.last().unwrap() {
Token::Atom(_) => return Err(ParseError::UnexpectedExpr),
Token::ClosingBracket => return Err(ParseError::UnexpectedExpr),
_ => (),
}
}
self.tokens.push(Token::Atom(c));
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' => {
if self.tokens.is_empty()
|| !matches!(
self.tokens.last(),
Some(Token::Atom(_) | Token::ClosingBracket)
)
{
return Err(ParseError::UnexpectedBinOp);
}
self.tokens.push(Token::Conjunction);
}
'|' => {
if self.tokens.is_empty()
|| !matches!(
self.tokens.last(),
Some(Token::Atom(_) | Token::ClosingBracket)
)
{
return Err(ParseError::UnexpectedBinOp);
}
self.tokens.push(Token::Disjunction);
}
'!' => {
self.tokens.push(Token::Negation);
}
_ => panic!("Invalid operator"),
}
Ok(())
}
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
tokenizer: Tokenizer,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
tokenizer: Tokenizer::new(),
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
return self.tokenizer.push_atom(c);
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
return self.tokenizer.push_op(op);
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
let mut expr_stack: Vec<Expr> = Vec::new();
let mut operator_stack: Vec<Token> = Vec::new();
let mut should_apply_negation = false;
for token in self.tokenizer.tokens {
match token {
Token::Atom(c) => {
let atom_expr = Expr::Atom(c);
if should_apply_negation {
expr_stack.push(Expr::Not(Box::new(atom_expr)));
should_apply_negation = false;
} else {
expr_stack.push(atom_expr);
}
}
Token::Negation => {
should_apply_negation = true;
}
Token::Conjunction | Token::Disjunction => {
while !operator_stack.is_empty() {
if expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
let op = operator_stack.pop().unwrap();
let combined_expr = match op {
Token::Conjunction => Expr::And(vec![left, right]),
Token::Disjunction => Expr::Or(vec![left, right]),
_ => unreachable!(),
};
expr_stack.push(combined_expr);
}
operator_stack.push(token);
}
_ => return Err(ParseError::UnexpectedExpr),
}
}
while !operator_stack.is_empty() {
if expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
let op = operator_stack.pop().unwrap();
let combined_expr = match op {
Token::Conjunction => Expr::And(vec![left, right]),
Token::Disjunction => Expr::Or(vec![left, right]),
_ => unreachable!(),
};
expr_stack.push(combined_expr);
}
if expr_stack.len() == 1 {
Ok(expr_stack.pop().unwrap())
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
tokenizer: Tokenizer,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
tokenizer: Tokenizer::new(),
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.tokenizer.push_atom(c)
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.tokenizer.push_op(op)
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if let Some(Token::Atom(_) | Token::ClosingBracket) = self.tokenizer.tokens.last() {
return Err(ParseError::UnexpectedParen);
}
self.tokenizer.tokens.push(Token::OpeningBracket);
Ok(())
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.tokenizer.tokens.is_empty() {
return Err(ParseError::UnexpectedParen);
}
if !self.tokenizer.tokens.contains(&Token::OpeningBracket) {
return Err(ParseError::UnexpectedParen);
}
self.tokenizer.tokens.push(Token::ClosingBracket);
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
let mut expr_stack: Vec<Expr> = Vec::new();
let mut operator_stack: Vec<Token> = Vec::new();
let mut bracket_stack: Vec<(Vec<Expr>, Vec<Token>)> = Vec::new();
let mut should_apply_negation = false;
for token in self.tokenizer.tokens {
match token {
Token::Atom(value) => {
let atom = Expr::Atom(value);
if should_apply_negation {
expr_stack.push(Expr::Not(Box::new(atom)));
should_apply_negation = false;
} else {
expr_stack.push(atom);
}
}
Token::Negation => {
should_apply_negation = true;
}
Token::Conjunction | Token::Disjunction => {
while !operator_stack.is_empty() {
if expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
let operator = operator_stack.pop().unwrap();
let combined_expr = match operator {
Token::Conjunction => Expr::And(vec![left, right]),
Token::Disjunction => Expr::Or(vec![left, right]),
_ => return Err(ParseError::UnexpectedBinOp),
};
expr_stack.push(combined_expr);
}
operator_stack.push(token);
}
Token::OpeningBracket => {
bracket_stack.push((expr_stack.clone(), operator_stack.clone()));
expr_stack.clear();
operator_stack.clear();
}
Token::ClosingBracket => {
while !operator_stack.is_empty() {
if expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
let operator = operator_stack.pop().unwrap();
let combined_expr = match operator {
Token::Conjunction => Expr::And(vec![left, right]),
Token::Disjunction => Expr::Or(vec![left, right]),
_ => return Err(ParseError::UnexpectedBinOp),
};
expr_stack.push(combined_expr);
}
if expr_stack.len() != 1 {
return Err(ParseError::UnexpectedParen);
}
let grouped_expr = expr_stack.pop().unwrap();
let (mut previous_expr_stack, mut previous_operator_stack) =
bracket_stack.pop().unwrap();
previous_expr_stack.push(grouped_expr);
while !previous_operator_stack.is_empty() {
if previous_expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = previous_expr_stack.pop().unwrap();
let left = previous_expr_stack.pop().unwrap();
let operator = previous_operator_stack.pop().unwrap();
let combined_expr = match operator {
Token::Conjunction => Expr::And(vec![left, right]),
Token::Disjunction => Expr::Or(vec![left, right]),
_ => return Err(ParseError::UnexpectedBinOp),
};
previous_expr_stack.push(combined_expr);
}
expr_stack = previous_expr_stack;
operator_stack = previous_operator_stack;
}
}
}
while !operator_stack.is_empty() {
if expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
let operator = operator_stack.pop().unwrap();
let combined_expr = match operator {
Token::Conjunction => Expr::And(vec![left, right]),
Token::Disjunction => Expr::Or(vec![left, right]),
_ => return Err(ParseError::UnexpectedBinOp),
};
expr_stack.push(combined_expr);
}
if expr_stack.len() == 1 {
Ok(expr_stack.pop().unwrap())
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
match expr {
Expr::Atom(atom) => {
if truthy.contains(&atom) {
Value::True
} else if falsy.contains(&atom) {
Value::False
} else {
Value::Expr(expr.clone())
}
}
Expr::Not(inner_expr) => match eval(inner_expr, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
other => other,
},
Expr::And(exprs) => {
let evaluated_exprs: Vec<Value> =
exprs.iter().map(|e| eval(e, truthy, falsy)).collect();
if evaluated_exprs.iter().all(|v| *v == Value::True) {
Value::True
} else if evaluated_exprs.iter().any(|v| *v == Value::False) {
Value::False
} else {
Value::Expr(Expr::And(exprs.clone()))
}
}
Expr::Or(exprs) => {
let evaluated_exprs: Vec<Value> =
exprs.iter().map(|e| eval(e, truthy, falsy)).collect();
if evaluated_exprs.iter().any(|v| *v == Value::True) {
Value::True
} else if evaluated_exprs.iter().all(|v| *v == Value::False) {
Value::False
} else {
Value::Expr(Expr::Or(exprs.clone()))
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-1fnroe0/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.83s
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 ... ok
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 ... 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.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_eval_partial stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Expr(Atom('B'))`,
right: `Expr(Not(Atom('B')))`', tests/solution_test.rs:411:9
thread 'solution_test::test_eval_partial' panicked at 'assertion failed: `(left == right)`
left: `Expr(Atom('B'))`,
right: `Expr(Not(Atom('B')))`', 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_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([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_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
---- 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(Atom('B'))`,
right: `Not(Not(Not(Atom('B'))))`', tests/solution_test.rs:143:9
thread 'solution_test::test_parser_multiple_not' panicked at 'assertion failed: `(left == right)`
left: `Not(Atom('B'))`,
right: `Not(Not(Not(Atom('B'))))`', tests/solution_test.rs:140: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_nested
solution_test::test_paren_not
solution_test::test_paren_surrounded
solution_test::test_parser_errors_basic
solution_test::test_parser_multiple_atoms_same_op
solution_test::test_parser_multiple_not
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`