Решение на Логически изрази от Петър Велков
Резултати
- 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)]
enum SimpleState {
Expr,
UnaryOp,
BinOp,
}
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum ParseError {
UnexpectedExpr,
UnexpectedUnaryOp,
UnexpectedBinOp,
UnexpectedParen,
UnexpectedEnd,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
left_expr: Option<Expr>,
last_state: Option<SimpleState>,
current_op: Option<char>,
not_count: usize,
last_err: Option<ParseError>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
left_expr: None,
last_state: None,
current_op: None,
not_count: 0,
last_err: None,
}
}
fn check_broken(&self) -> Result<(), ParseError> {
if let Some(ref err) = self.last_err {
return Err(err.clone());
}
Ok(())
}
fn set_error(&mut self, err: ParseError) -> Result<(), ParseError> {
self.last_err = Some(err.clone());
Err(err)
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.check_broken()?;
if self.last_state == Some(SimpleState::Expr) {
return self.set_error(ParseError::UnexpectedExpr);
}
let mut expr = Expr::Atom(c);
if self.last_state == Some(SimpleState::UnaryOp) {
for _ in 0..self.not_count {
expr = Expr::Not(Box::new(expr));
}
}
self.not_count = 0;
if let Some(op) = self.current_op {
match self.left_expr.take() {
Some(Expr::And(mut v)) if op == '&' => {
v.push(expr);
self.left_expr = Some(Expr::And(v));
}
Some(Expr::And(v)) if op == '|' => {
self.left_expr = Some(Expr::Or(vec![Expr::And(v), expr]));
}
Some(Expr::Or(mut v)) if op == '|' => {
v.push(expr);
self.left_expr = Some(Expr::Or(v));
}
Some(Expr::Or(v)) if op == '&' => {
self.left_expr = Some(Expr::And(vec![Expr::Or(v), expr]));
}
Some(prev_expr) => {
if op == '&' {
self.left_expr = Some(Expr::And(vec![prev_expr, expr]));
} else {
self.left_expr = Some(Expr::Or(vec![prev_expr, expr]));
}
}
None => {
self.left_expr = Some(expr);
}
}
} else {
if self.left_expr.is_some() {
return self.set_error(ParseError::UnexpectedExpr);
} else {
self.left_expr = Some(expr);
}
}
self.last_state = Some(SimpleState::Expr);
Ok(())
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.check_broken()?;
match op {
'!' => {
match self.last_state {
None | Some(SimpleState::BinOp) | Some(SimpleState::UnaryOp) => {
self.not_count += 1;
self.last_state = Some(SimpleState::UnaryOp);
}
Some(SimpleState::Expr) => {
return self.set_error(ParseError::UnexpectedUnaryOp);
}
}
}
'&' | '|' => {
if self.last_state != Some(SimpleState::Expr) {
return self.set_error(ParseError::UnexpectedBinOp);
}
self.current_op = Some(op);
self.last_state = Some(SimpleState::BinOp);
self.not_count = 0;
}
_ => panic!("Unsupported op: {}", op),
}
Ok(())
}
pub fn push_subexpr(&mut self, mut expr: Expr) -> Result<(), ParseError> {
self.check_broken()?;
if self.last_state == Some(SimpleState::Expr) {
return self.set_error(ParseError::UnexpectedExpr);
}
if self.last_state == Some(SimpleState::UnaryOp) {
for _ in 0..self.not_count {
expr = Expr::Not(Box::new(expr));
}
}
self.not_count = 0;
if let Some(op) = self.current_op {
match self.left_expr.take() {
Some(Expr::And(mut v)) if op == '&' => {
v.push(expr);
self.left_expr = Some(Expr::And(v));
}
Some(Expr::And(v)) if op == '|' => {
self.left_expr = Some(Expr::Or(vec![Expr::And(v), expr]));
}
Some(Expr::Or(mut v)) if op == '|' => {
v.push(expr);
self.left_expr = Some(Expr::Or(v));
}
Some(Expr::Or(v)) if op == '&' => {
self.left_expr = Some(Expr::And(vec![Expr::Or(v), expr]));
}
Some(prev_expr) => {
if op == '&' {
self.left_expr = Some(Expr::And(vec![prev_expr, expr]));
} else {
self.left_expr = Some(Expr::Or(vec![prev_expr, expr]));
}
}
None => {
self.left_expr = Some(expr);
}
}
} else {
if self.left_expr.is_none() {
self.left_expr = Some(expr);
} else {
return self.set_error(ParseError::UnexpectedExpr);
}
}
self.last_state = Some(SimpleState::Expr);
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
self.check_broken()?;
if self.last_state != Some(SimpleState::Expr) {
return Err(ParseError::UnexpectedEnd);
}
match self.left_expr {
Some(expr) => Ok(expr),
None => 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 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(e) => {
match eval(e, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(ex) => Value::Expr(Expr::Not(Box::new(ex))),
}
}
Expr::And(es) => {
let mut new_exprs = Vec::new();
for sub in es {
match eval(sub, truthy, falsy) {
Value::True => {
}
Value::False => {
return Value::False;
}
Value::Expr(ex) => {
new_exprs.push(ex);
}
}
}
if new_exprs.is_empty() {
Value::True
} else if new_exprs.len() == 1 {
Value::Expr(new_exprs.pop().unwrap())
} else {
Value::Expr(Expr::And(new_exprs))
}
}
Expr::Or(es) => {
let mut new_exprs = Vec::new();
for sub in es {
match eval(sub, truthy, falsy) {
Value::True => {
return Value::True;
}
Value::False => {
}
Value::Expr(ex) => {
new_exprs.push(ex);
}
}
}
if new_exprs.is_empty() {
Value::False
} else if new_exprs.len() == 1 {
Value::Expr(new_exprs.pop().unwrap())
} else {
Value::Expr(Expr::Or(new_exprs))
}
}
}
}
pub struct ExprParser {
stack: Vec<SimpleExprParser>,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
stack: vec![SimpleExprParser::new()],
}
}
fn top_parser_mut(&mut self) -> &mut SimpleExprParser {
self.stack
.last_mut()
.expect("Stack should never be empty internally")
}
/// Приема атом (единичен char).
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.top_parser_mut().push_atom(c)
}
/// Приема символ за операция (&, |, !).
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.top_parser_mut().push_op(op)
}
/// Приема отваряща скоба '(' – създаваме нов SimpleExprParser и го качваме на стека.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.stack.push(SimpleExprParser::new());
Ok(())
}
/// Приема затваряща скоба ')' – довършваме последния SimpleExprParser,
/// вадим го от стека и го слагаме като под-израз в предишния.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.stack.len() == 1 {
return Err(ParseError::UnexpectedParen);
}
let finished_parser = self.stack.pop().unwrap();
let expr = finished_parser.finish()?;
let top_parser = self.top_parser_mut();
top_parser.push_subexpr(expr)
}
/// Завършваме целия парсинг. Трябва да сме останали само с 1 парсър в стека.
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.stack.len() != 1 {
return Err(ParseError::UnexpectedEnd);
}
self.stack.pop().unwrap().finish()
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-iwf40g/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.73s
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_not ... ok
test solution_test::test_paren_nested ... 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 '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
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`