Решение на Логически изрази от Стоян Генчев
Резултати
- 19 точки от тестове
- 0 бонус точки
- 19 точки общо
- 19 успешни тест(а)
- 1 неуспешни тест(а)
Код
#[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 {
cur_expr: Option<Expr>,
cur_ops: Vec<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
cur_expr: None,
cur_ops: vec![], // allows for either '&' or '|' and consecutive '!'
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
let cur_expr = self.cur_expr.take();
self.cur_expr = match self.cur_ops.len() {
0 => match cur_expr {
Some(_) => return Err(ParseError::UnexpectedExpr),
None => Some(Expr::Atom(c)),
},
_ => {
let mut expr = Expr::Atom(c);
while self.cur_ops.len() > 1 {
expr = Expr::Not(Box::new(expr));
self.cur_ops.pop();
}
match self.cur_ops.pop().unwrap() {
'&' => match cur_expr {
Some(Expr::And(mut vec)) => {
vec.push(expr);
Some(Expr::And(vec))
}
Some(_) => Some(Expr::And(vec![cur_expr.unwrap(), expr])),
None => panic!(),
},
'|' => match cur_expr {
Some(Expr::Or(mut vec)) => {
vec.push(expr);
Some(Expr::Or(vec))
}
Some(_) => Some(Expr::Or(vec![cur_expr.unwrap(), expr])),
None => panic!(),
},
'!' => match cur_expr {
Some(_) => panic!(),
None => Some(Expr::Not(Box::new(expr)))
},
_ => panic!(),
}
}
};
Ok(())
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' => if self.cur_expr.is_none() || self.cur_ops.len() > 0 {
return Err(ParseError::UnexpectedBinOp)
},
'!' => if self.cur_expr.is_some() && self.cur_ops.len() == 0 {
return Err(ParseError::UnexpectedBinOp)
},
_ => panic!()
}
self.cur_ops.push(op);
Ok(())
}
/// Приема expression
fn push_expr(&mut self, expr: Expr) -> Result<(), ParseError> {
let cur_expr = self.cur_expr.take();
self.cur_expr = match self.cur_ops.len() {
0 => match cur_expr {
Some(_) => return Err(ParseError::UnexpectedExpr),
None => Some(expr),
},
_ => {
let mut expr = expr;
while self.cur_ops.len() > 1 {
expr = Expr::Not(Box::new(expr));
self.cur_ops.pop();
}
match self.cur_ops.pop().unwrap() {
'&' => match cur_expr {
Some(Expr::And(mut vec)) => {
vec.push(expr);
Some(Expr::And(vec))
}
Some(_) => Some(Expr::And(vec![cur_expr.unwrap(), expr])),
None => panic!(),
},
'|' => match cur_expr {
Some(Expr::Or(mut vec)) => {
vec.push(expr);
Some(Expr::Or(vec))
}
Some(_) => Some(Expr::Or(vec![cur_expr.unwrap(), expr])),
None => panic!(),
},
'!' => match cur_expr {
Some(_) => panic!(),
None => Some(Expr::Not(Box::new(expr)))
},
_ => panic!(),
}
}
};
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.cur_ops.len() > 0 || self.cur_expr.is_none() {
return Err(ParseError::UnexpectedEnd);
}
Ok(self.cur_expr.unwrap())
}
}
/// Парсър за пълния израз
pub struct ExprParser {
simple_expr_parser: SimpleExprParser,
open_parentheses: usize,
ongoing_expr: Vec<char>,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
simple_expr_parser: SimpleExprParser::new(),
open_parentheses: 0,
ongoing_expr: Vec::new(),
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if self.ongoing_expr.len() > 0 {
match self.ongoing_expr.last().unwrap() {
'&' | '|' | '!' | '(' => (),
_ => return Err(ParseError::UnexpectedExpr),
}
self.ongoing_expr.push(c);
return Ok(());
}
self.simple_expr_parser.push_atom(c)
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
if self.ongoing_expr.len() > 0 {
match self.ongoing_expr.last().unwrap() {
'&' | '|' => match op {
'&' | '|' => return Err(ParseError::UnexpectedBinOp),
_ => (),
},
'!' => match op {
'!' => (),
_ => return Err(ParseError::UnexpectedBinOp)
},
')' => match op {
'!' => return Err(ParseError::UnexpectedUnaryOp),
_ => ()
},
'(' => match op {
'!' => (),
_ => return Err(ParseError::UnexpectedBinOp)
},
_ => match op {
'!' => return Err(ParseError::UnexpectedUnaryOp),
_ => ()
}
}
self.ongoing_expr.push(op);
return Ok(())
}
self.simple_expr_parser.push_op(op)
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if self.ongoing_expr.len() > 0 {
match self.ongoing_expr.last().unwrap() {
')' => return Err(ParseError::UnexpectedParen),
'(' | '&' | '|' | '!' => (),
_ => return Err(ParseError::UnexpectedParen),
}
} else if self.simple_expr_parser.cur_ops.len() == 0
&& self.simple_expr_parser.cur_expr.is_some() {
return Err(ParseError::UnexpectedParen);
}
self.ongoing_expr.push('(');
self.open_parentheses += 1;
Ok(())
}
fn evaluate_expr(&mut self, from: usize, to: usize) -> Result<Expr, ParseError> {
let mut simple_expr_parser = SimpleExprParser::new();
let mut i = from;
while i < to {
match self.ongoing_expr[i] {
'&' | '|' | '!' => simple_expr_parser.push_op(self.ongoing_expr[i])?,
'(' => {
let mut y = i;
let mut open_paren_count = 1;
while y < to {
y += 1;
if self.ongoing_expr[y] == '(' {
open_paren_count += 1;
} else if self.ongoing_expr[y] == ')' {
open_paren_count -= 1;
if open_paren_count == 0 {
simple_expr_parser.push_expr(self.evaluate_expr(i + 1, y)?)?;
i = y;
break;
}
}
}
},
ch => simple_expr_parser.push_atom(ch)?,
}
i += 1;
}
simple_expr_parser.finish()
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.ongoing_expr.len() > 0 {
match self.ongoing_expr.last().unwrap() {
'&' | '|' | '!' | '(' => return Err(ParseError::UnexpectedParen),
_ => ()
}
} else if self.simple_expr_parser.cur_ops.len() > 0 {
return Err(ParseError::UnexpectedParen)
}
self.ongoing_expr.push(')');
self.open_parentheses -= 1;
if self.open_parentheses > 0 {
return Ok(())
}
let expr = self.evaluate_expr(1, self.ongoing_expr.len() - 1)?;
self.simple_expr_parser.push_expr(expr)?;
self.ongoing_expr.clear();
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parentheses != 0 || self.ongoing_expr.len() != 0 {
return Err(ParseError::UnexpectedEnd);
}
self.simple_expr_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(ch) =>
if truthy.contains(ch) { Value::True }
else if falsy.contains(ch) { Value::False }
else { Value::Expr(expr.clone()) },
Expr::Not(expr) => match eval(expr, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(value_expr) => Value::Expr(Expr::Not(Box::new(value_expr))),
},
Expr::And(vec) => {
let mut results = Vec::new();
let mut i = 0;
while i < vec.len() {
let result = eval(&vec.get(i).unwrap(), truthy, falsy);
if let Value::False = result {
return Value::False;
} else if let Value::Expr(e) = result {
results.push(e)
}
i += 1;
}
if results.len() == 0 {
Value::True
} else if results.len() == 1 {
Value::Expr(results.pop().unwrap())
} else {
Value::Expr(Expr::And(results))
}
},
Expr::Or(vec) => {
let mut results = Vec::new();
let mut i = 0;
while i < vec.len() {
let result = eval(&vec.get(i).unwrap(), truthy, falsy);
if let Value::True = result {
return Value::True;
} else if let Value::Expr(e) = result {
results.push(e)
}
i += 1;
}
if results.len() == 0 {
Value::False
} else if results.len() == 1 {
Value::Expr(results.pop().unwrap())
} else {
Value::Expr(Expr::Or(results))
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-11hgfh4/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.71s
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 'attempt to subtract with overflow', src/lib.rs:284: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`