Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Логически изрази от Иван Панайотов

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

Към профила на Иван Панайотов

Резултати

  • 19 точки от тестове
  • 1 бонус точка
  • 20 точки общо
  • 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 {
full_expression: Option<Expr>,
pending_negation: usize,
current_bin_op: Option<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
full_expression: None,
pending_negation: 0,
current_bin_op: None,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' | '(' | ')' | ' ' => return Err(ParseError::UnexpectedExpr), // Невалидни атоми
_ => (),
}
// Създаваме нов атом, който може да е с отрицание
let mut atom = Expr::Atom(c);
for _ in 0..self.pending_negation {
atom = Expr::Not(Box::new(atom));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
// Ok
None => self.full_expression = Some(atom),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
// Ако нямаме бинарна операция - грешка
return Err(ParseError::UnexpectedExpr);
}
values.push(atom);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
match self.full_expression.as_ref() {
None => self.pending_negation += 1,
Some(Expr::Atom(_)) => return Err(ParseError::UnexpectedUnaryOp),
Some(Expr::Not(_)) => return Err(ParseError::UnexpectedUnaryOp),
Some(Expr::And(_)) | Some(Expr::Or(_)) => {
if self.current_bin_op.is_none() {
// Ако искаме оператор вместо атом или отрицание
return Err(ParseError::UnexpectedUnaryOp);
}
self.pending_negation += 1
}
}
}
'&' | '|' => {
if self.pending_negation > 0 || self.current_bin_op.is_some() {
// Ако има отрицание или вече има бинарна операция - грешка.
return Err(ParseError::UnexpectedBinOp);
}
let expr = self
.full_expression
.take()
.ok_or(ParseError::UnexpectedBinOp)?;
self.full_expression = Some(match expr {
Expr::Atom(_) => {
if op == '&' {
Expr::And(vec![expr])
} else {
Expr::Or(vec![expr])
}
}
Expr::Not(inner) => {
if op == '&' {
Expr::And(vec![Expr::Not(inner)])
} else {
Expr::Or(vec![Expr::Not(inner)])
}
}
Expr::And(values) => {
if op == '&' {
Expr::And(values)
} else {
Expr::Or(vec![Expr::And(values)])
}
}
Expr::Or(values) => {
if op == '|' {
Expr::Or(values)
} else {
Expr::And(vec![Expr::Or(values)])
}
}
});
self.current_bin_op = Some(op);
}
_ => return Err(ParseError::UnexpectedExpr),
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
if self.pending_negation > 0
|| self.full_expression.is_none()
|| self.current_bin_op.is_some()
{
return Err(ParseError::UnexpectedEnd);
}
Ok(self.full_expression.unwrap())
}
// Директно слагаме нов израз в текущия израз. Същото като добавяне на атом
pub fn push_expression(&mut self, mut expr: Expr) -> Result<(), ParseError> {
for _ in 0..self.pending_negation {
expr = Expr::Not(Box::new(expr));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
None => self.full_expression = Some(expr),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
return Err(ParseError::UnexpectedExpr);
}
values.push(expr);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
}
pub struct ExprParser {
expr_stack: Vec<SimpleExprParser>, // Работим със стек
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
expr_stack: vec![SimpleExprParser::new()],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser()?.push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser()?.push_op(op)
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.expr_stack.push(SimpleExprParser::new());
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.expr_stack.len() == 1 {
return Err(ParseError::UnexpectedParen);
}
let finished_expr = self.expr_stack.pop().unwrap().finish()?;
self.current_parser()?.push_expression(finished_expr)?;
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.expr_stack.len() > 1 {
return Err(ParseError::UnexpectedEnd);
}
self.expr_stack.pop().unwrap().finish()
}
fn current_parser(&mut self) -> Result<&mut SimpleExprParser, ParseError> {
self.expr_stack.last_mut().ok_or(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) => {
// Ако е атом, очевидно се връща или True, или False, или самият него
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(Expr::Atom(*c))
}
}
Expr::Not(inner) => match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(e) => Value::Expr(Expr::Not(Box::new(e))), // Връщаме новият израз с отрицание
},
Expr::And(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => continue, // True се поглъща
Value::False => return Value::False,
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::True, // Всички са True
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::And(new_expressions_list)), // Връщаме нов And с останалите
}
}
Expr::Or(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue, // False се поглъща
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::False, // Всички са False
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::Or(new_expressions_list)), // Връщаме нов Or с останалите
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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();
assert_eq!(expr, Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]));
assert_eq!(Value::True, eval(&expr, &['A', 'B'], &[]));
assert_eq!(Value::False, 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']);
assert_eq!(
expr,
Expr::And(vec![
Expr::Atom('A'),
Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])
])
);
assert_eq!(
Value::Expr(Expr::Not(Box::new(Expr::Atom('C')))),
eval(&expr, &['A'], &['B'])
);
assert_eq!(Value::False, eval(&expr, &[], &['A']));
}
#[test]
fn test_advanced_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_op('!');
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();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &['B'], &['A']));
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
}
#[test]
fn test_simple_expr_parser() {
// A
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let expr = full_parser.finish().unwrap();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &[], &['A']));
assert_eq!(Value::Expr(Expr::Atom('A')), eval(&expr, &[], &[]));
}
#[test]
fn test_basic_errors() {
// A & &
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));
// A & B B
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)
);
}
}

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

Compiling solution v0.1.0 (/tmp/d20241224-258381-8c83e8/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.69s
     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_expr_priority ... ok
test solution_test::test_paren_around_expr ... ok
test solution_test::test_paren_nested ... ok
test solution_test::test_paren_not ... ok
test solution_test::test_parser_alternating_ops ... ok
test solution_test::test_paren_surrounded ... ok
test solution_test::test_parser_and_or ... ok
test solution_test::test_parser_error_unexpected_end ... ok
test solution_test::test_parser_atom ... 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`

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

Иван качи първо решение на 22.12.2024 16:39 (преди 9 месеца)

Иван качи решение на 22.12.2024 19:36 (преди 9 месеца)

#[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 {
full_expression: Option<Expr>,
- pending_negation: bool,
+ pending_negation: usize,
current_bin_op: Option<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
full_expression: None,
- pending_negation: false,
+ pending_negation: 0,
current_bin_op: None,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' | '(' | ')' | ' ' => return Err(ParseError::UnexpectedExpr), // Невалидни атоми
_ => (),
}
// Създаваме нов атом, който може да е с отрицание
- let atom = if self.pending_negation {
- self.pending_negation = false;
- Expr::Not(Box::new(Expr::Atom(c)))
- } else {
- Expr::Atom(c)
- };
+ let mut atom = Expr::Atom(c);
+ for _ in 0..self.pending_negation {
+ atom = Expr::Not(Box::new(atom));
+ }
+ self.pending_negation = 0;
+
match self.full_expression.as_mut() {
// Ok
None => self.full_expression = Some(atom),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
// Ако нямаме бинарна операция - грешка
return Err(ParseError::UnexpectedExpr);
}
values.push(atom);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
- if self.pending_negation {
- // Не може да имаме двойно отрицание, поне според условието
+ if self.current_bin_op.is_none() && self.full_expression.is_some() {
return Err(ParseError::UnexpectedUnaryOp);
}
- self.pending_negation = true;
+ self.pending_negation += 1;
}
'&' | '|' => {
- if self.pending_negation || self.current_bin_op.is_some() {
+ if self.pending_negation > 0 || self.current_bin_op.is_some() {
// Ако има отрицание или вече има бинарна операция - грешка.
return Err(ParseError::UnexpectedBinOp);
}
let expr = self
.full_expression
.take()
.ok_or(ParseError::UnexpectedBinOp)?;
self.full_expression = Some(match expr {
Expr::Atom(_) => {
if op == '&' {
Expr::And(vec![expr])
} else {
Expr::Or(vec![expr])
}
}
Expr::Not(inner) => {
if op == '&' {
Expr::And(vec![Expr::Not(inner)])
} else {
Expr::Or(vec![Expr::Not(inner)])
}
}
Expr::And(values) => {
if op == '&' {
Expr::And(values)
} else {
Expr::Or(vec![Expr::And(values)])
}
}
Expr::Or(values) => {
if op == '|' {
Expr::Or(values)
} else {
Expr::And(vec![Expr::Or(values)])
}
}
});
self.current_bin_op = Some(op);
}
_ => return Err(ParseError::UnexpectedExpr),
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
- if self.pending_negation || self.full_expression.is_none() || self.current_bin_op.is_some()
+ if self.pending_negation > 0
+ || self.full_expression.is_none()
+ || self.current_bin_op.is_some()
{
return Err(ParseError::UnexpectedEnd);
}
Ok(self.full_expression.unwrap())
}
// Директно слагаме нов израз в текущия израз. Същото като добавяне на атом
pub fn push_expression(&mut self, mut expr: Expr) -> Result<(), ParseError> {
- if self.pending_negation {
+ for _ in 0..self.pending_negation {
expr = Expr::Not(Box::new(expr));
}
+
+ self.pending_negation = 0;
match self.full_expression.as_mut() {
None => self.full_expression = Some(expr),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
return Err(ParseError::UnexpectedExpr);
}
values.push(expr);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
}
pub struct ExprParser {
expr_stack: Vec<SimpleExprParser>, // Работим със стек
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
expr_stack: vec![SimpleExprParser::new()],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser()?.push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser()?.push_op(op)
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.expr_stack.push(SimpleExprParser::new());
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.expr_stack.len() == 1 {
return Err(ParseError::UnexpectedParen);
}
let finished_expr = self.expr_stack.pop().unwrap().finish()?;
self.current_parser()?.push_expression(finished_expr)?;
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.expr_stack.len() > 1 {
return Err(ParseError::UnexpectedEnd);
}
self.expr_stack.pop().unwrap().finish()
}
fn current_parser(&mut self) -> Result<&mut SimpleExprParser, ParseError> {
self.expr_stack.last_mut().ok_or(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) => {
// Ако е атом, очевидно се връща или True, или False, или самият него
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(Expr::Atom(*c))
}
}
Expr::Not(inner) => match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(e) => Value::Expr(Expr::Not(Box::new(e))), // Връщаме новият израз с отрицание
},
Expr::And(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => continue, // True се поглъща
Value::False => return Value::False,
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::True, // Всички са True
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::And(new_expressions_list)), // Връщаме нов And с останалите
}
}
Expr::Or(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue, // False се поглъща
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::False, // Всички са False
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::Or(new_expressions_list)), // Връщаме нов Or с останалите
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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();
assert_eq!(expr, Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]));
assert_eq!(Value::True, eval(&expr, &['A', 'B'], &[]));
assert_eq!(Value::False, 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']);
assert_eq!(
expr,
Expr::And(vec![
Expr::Atom('A'),
Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])
])
);
assert_eq!(
Value::Expr(Expr::Not(Box::new(Expr::Atom('C')))),
eval(&expr, &['A'], &['B'])
);
assert_eq!(Value::False, eval(&expr, &[], &['A']));
}
#[test]
fn test_advanced_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_op('!');
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();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &['B'], &['A']));
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
}
#[test]
fn test_simple_expr_parser() {
// A
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let expr = full_parser.finish().unwrap();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &[], &['A']));
assert_eq!(Value::Expr(Expr::Atom('A')), eval(&expr, &[], &[]));
}
#[test]
fn test_basic_errors() {
// A & &
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));
// A & B B
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)
);
}
}

Иван качи решение на 22.12.2024 19:45 (преди 9 месеца)

#[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 {
full_expression: Option<Expr>,
pending_negation: usize,
current_bin_op: Option<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
full_expression: None,
pending_negation: 0,
current_bin_op: None,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' | '(' | ')' | ' ' => return Err(ParseError::UnexpectedExpr), // Невалидни атоми
_ => (),
}
// Създаваме нов атом, който може да е с отрицание
let mut atom = Expr::Atom(c);
for _ in 0..self.pending_negation {
atom = Expr::Not(Box::new(atom));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
// Ok
None => self.full_expression = Some(atom),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
// Ако нямаме бинарна операция - грешка
return Err(ParseError::UnexpectedExpr);
}
values.push(atom);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
+ match self.full_expression.as_ref() {
+ None => (),
+ Some(Expr::Atom(_)) => return Err(ParseError::UnexpectedUnaryOp),
+ _ => (),
+ }
+
if self.current_bin_op.is_none() && self.full_expression.is_some() {
return Err(ParseError::UnexpectedUnaryOp);
}
+
self.pending_negation += 1;
}
'&' | '|' => {
if self.pending_negation > 0 || self.current_bin_op.is_some() {
// Ако има отрицание или вече има бинарна операция - грешка.
return Err(ParseError::UnexpectedBinOp);
}
let expr = self
.full_expression
.take()
.ok_or(ParseError::UnexpectedBinOp)?;
self.full_expression = Some(match expr {
Expr::Atom(_) => {
if op == '&' {
Expr::And(vec![expr])
} else {
Expr::Or(vec![expr])
}
}
Expr::Not(inner) => {
if op == '&' {
Expr::And(vec![Expr::Not(inner)])
} else {
Expr::Or(vec![Expr::Not(inner)])
}
}
Expr::And(values) => {
if op == '&' {
Expr::And(values)
} else {
Expr::Or(vec![Expr::And(values)])
}
}
Expr::Or(values) => {
if op == '|' {
Expr::Or(values)
} else {
Expr::And(vec![Expr::Or(values)])
}
}
});
self.current_bin_op = Some(op);
}
_ => return Err(ParseError::UnexpectedExpr),
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
if self.pending_negation > 0
|| self.full_expression.is_none()
|| self.current_bin_op.is_some()
{
return Err(ParseError::UnexpectedEnd);
}
Ok(self.full_expression.unwrap())
}
// Директно слагаме нов израз в текущия израз. Същото като добавяне на атом
pub fn push_expression(&mut self, mut expr: Expr) -> Result<(), ParseError> {
for _ in 0..self.pending_negation {
expr = Expr::Not(Box::new(expr));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
None => self.full_expression = Some(expr),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
return Err(ParseError::UnexpectedExpr);
}
values.push(expr);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
}
pub struct ExprParser {
expr_stack: Vec<SimpleExprParser>, // Работим със стек
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
expr_stack: vec![SimpleExprParser::new()],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser()?.push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser()?.push_op(op)
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.expr_stack.push(SimpleExprParser::new());
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.expr_stack.len() == 1 {
return Err(ParseError::UnexpectedParen);
}
let finished_expr = self.expr_stack.pop().unwrap().finish()?;
self.current_parser()?.push_expression(finished_expr)?;
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.expr_stack.len() > 1 {
return Err(ParseError::UnexpectedEnd);
}
self.expr_stack.pop().unwrap().finish()
}
fn current_parser(&mut self) -> Result<&mut SimpleExprParser, ParseError> {
self.expr_stack.last_mut().ok_or(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) => {
// Ако е атом, очевидно се връща или True, или False, или самият него
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(Expr::Atom(*c))
}
}
Expr::Not(inner) => match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(e) => Value::Expr(Expr::Not(Box::new(e))), // Връщаме новият израз с отрицание
},
Expr::And(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => continue, // True се поглъща
Value::False => return Value::False,
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::True, // Всички са True
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::And(new_expressions_list)), // Връщаме нов And с останалите
}
}
Expr::Or(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue, // False се поглъща
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::False, // Всички са False
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::Or(new_expressions_list)), // Връщаме нов Or с останалите
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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();
assert_eq!(expr, Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]));
assert_eq!(Value::True, eval(&expr, &['A', 'B'], &[]));
assert_eq!(Value::False, 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']);
assert_eq!(
expr,
Expr::And(vec![
Expr::Atom('A'),
Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])
])
);
assert_eq!(
Value::Expr(Expr::Not(Box::new(Expr::Atom('C')))),
eval(&expr, &['A'], &['B'])
);
assert_eq!(Value::False, eval(&expr, &[], &['A']));
}
#[test]
fn test_advanced_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_op('!');
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();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &['B'], &['A']));
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
}
#[test]
fn test_simple_expr_parser() {
// A
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let expr = full_parser.finish().unwrap();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &[], &['A']));
assert_eq!(Value::Expr(Expr::Atom('A')), eval(&expr, &[], &[]));
}
#[test]
fn test_basic_errors() {
// A & &
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));
// A & B B
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)
);
}
}

Иван качи решение на 22.12.2024 19:49 (преди 9 месеца)

#[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 {
full_expression: Option<Expr>,
pending_negation: usize,
current_bin_op: Option<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
full_expression: None,
pending_negation: 0,
current_bin_op: None,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' | '(' | ')' | ' ' => return Err(ParseError::UnexpectedExpr), // Невалидни атоми
_ => (),
}
// Създаваме нов атом, който може да е с отрицание
let mut atom = Expr::Atom(c);
for _ in 0..self.pending_negation {
atom = Expr::Not(Box::new(atom));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
// Ok
None => self.full_expression = Some(atom),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
// Ако нямаме бинарна операция - грешка
return Err(ParseError::UnexpectedExpr);
}
values.push(atom);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
match self.full_expression.as_ref() {
- None => (),
+ None => self.pending_negation += 1,
Some(Expr::Atom(_)) => return Err(ParseError::UnexpectedUnaryOp),
- _ => (),
- }
+ Some(Expr::Not(_)) => self.pending_negation += 1,
+ Some(Expr::And(_)) | Some(Expr::Or(_)) => {
+ if self.current_bin_op.is_none() { // Ако искаме оператор вместо атом или отрицание
+ return Err(ParseError::UnexpectedUnaryOp);
+ }
- if self.current_bin_op.is_none() && self.full_expression.is_some() {
- return Err(ParseError::UnexpectedUnaryOp);
+ self.pending_negation += 1
+ }
}
-
- self.pending_negation += 1;
}
'&' | '|' => {
if self.pending_negation > 0 || self.current_bin_op.is_some() {
// Ако има отрицание или вече има бинарна операция - грешка.
return Err(ParseError::UnexpectedBinOp);
}
let expr = self
.full_expression
.take()
.ok_or(ParseError::UnexpectedBinOp)?;
self.full_expression = Some(match expr {
Expr::Atom(_) => {
if op == '&' {
Expr::And(vec![expr])
} else {
Expr::Or(vec![expr])
}
}
Expr::Not(inner) => {
if op == '&' {
Expr::And(vec![Expr::Not(inner)])
} else {
Expr::Or(vec![Expr::Not(inner)])
}
}
Expr::And(values) => {
if op == '&' {
Expr::And(values)
} else {
Expr::Or(vec![Expr::And(values)])
}
}
Expr::Or(values) => {
if op == '|' {
Expr::Or(values)
} else {
Expr::And(vec![Expr::Or(values)])
}
}
});
self.current_bin_op = Some(op);
}
_ => return Err(ParseError::UnexpectedExpr),
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
if self.pending_negation > 0
|| self.full_expression.is_none()
|| self.current_bin_op.is_some()
{
return Err(ParseError::UnexpectedEnd);
}
Ok(self.full_expression.unwrap())
}
// Директно слагаме нов израз в текущия израз. Същото като добавяне на атом
pub fn push_expression(&mut self, mut expr: Expr) -> Result<(), ParseError> {
for _ in 0..self.pending_negation {
expr = Expr::Not(Box::new(expr));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
None => self.full_expression = Some(expr),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
return Err(ParseError::UnexpectedExpr);
}
values.push(expr);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
}
pub struct ExprParser {
expr_stack: Vec<SimpleExprParser>, // Работим със стек
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
expr_stack: vec![SimpleExprParser::new()],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser()?.push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser()?.push_op(op)
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.expr_stack.push(SimpleExprParser::new());
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.expr_stack.len() == 1 {
return Err(ParseError::UnexpectedParen);
}
let finished_expr = self.expr_stack.pop().unwrap().finish()?;
self.current_parser()?.push_expression(finished_expr)?;
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.expr_stack.len() > 1 {
return Err(ParseError::UnexpectedEnd);
}
self.expr_stack.pop().unwrap().finish()
}
fn current_parser(&mut self) -> Result<&mut SimpleExprParser, ParseError> {
self.expr_stack.last_mut().ok_or(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) => {
// Ако е атом, очевидно се връща или True, или False, или самият него
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(Expr::Atom(*c))
}
}
Expr::Not(inner) => match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(e) => Value::Expr(Expr::Not(Box::new(e))), // Връщаме новият израз с отрицание
},
Expr::And(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => continue, // True се поглъща
Value::False => return Value::False,
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::True, // Всички са True
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::And(new_expressions_list)), // Връщаме нов And с останалите
}
}
Expr::Or(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue, // False се поглъща
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::False, // Всички са False
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::Or(new_expressions_list)), // Връщаме нов Or с останалите
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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();
assert_eq!(expr, Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]));
assert_eq!(Value::True, eval(&expr, &['A', 'B'], &[]));
assert_eq!(Value::False, 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']);
assert_eq!(
expr,
Expr::And(vec![
Expr::Atom('A'),
Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])
])
);
assert_eq!(
Value::Expr(Expr::Not(Box::new(Expr::Atom('C')))),
eval(&expr, &['A'], &['B'])
);
assert_eq!(Value::False, eval(&expr, &[], &['A']));
}
#[test]
fn test_advanced_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_op('!');
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();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &['B'], &['A']));
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
}
#[test]
fn test_simple_expr_parser() {
// A
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let expr = full_parser.finish().unwrap();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &[], &['A']));
assert_eq!(Value::Expr(Expr::Atom('A')), eval(&expr, &[], &[]));
}
#[test]
fn test_basic_errors() {
// A & &
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));
// A & B B
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)
);
}
}

Иван качи решение на 22.12.2024 20:00 (преди 9 месеца)

#[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 {
full_expression: Option<Expr>,
pending_negation: usize,
current_bin_op: Option<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
full_expression: None,
pending_negation: 0,
current_bin_op: None,
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' | '(' | ')' | ' ' => return Err(ParseError::UnexpectedExpr), // Невалидни атоми
_ => (),
}
// Създаваме нов атом, който може да е с отрицание
let mut atom = Expr::Atom(c);
for _ in 0..self.pending_negation {
atom = Expr::Not(Box::new(atom));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
// Ok
None => self.full_expression = Some(atom),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
// Ако нямаме бинарна операция - грешка
return Err(ParseError::UnexpectedExpr);
}
values.push(atom);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
match self.full_expression.as_ref() {
None => self.pending_negation += 1,
Some(Expr::Atom(_)) => return Err(ParseError::UnexpectedUnaryOp),
- Some(Expr::Not(_)) => self.pending_negation += 1,
+ Some(Expr::Not(_)) => return Err(ParseError::UnexpectedUnaryOp),
Some(Expr::And(_)) | Some(Expr::Or(_)) => {
- if self.current_bin_op.is_none() { // Ако искаме оператор вместо атом или отрицание
+ if self.current_bin_op.is_none() {
+ // Ако искаме оператор вместо атом или отрицание
return Err(ParseError::UnexpectedUnaryOp);
}
self.pending_negation += 1
}
}
}
'&' | '|' => {
if self.pending_negation > 0 || self.current_bin_op.is_some() {
// Ако има отрицание или вече има бинарна операция - грешка.
return Err(ParseError::UnexpectedBinOp);
}
let expr = self
.full_expression
.take()
.ok_or(ParseError::UnexpectedBinOp)?;
self.full_expression = Some(match expr {
Expr::Atom(_) => {
if op == '&' {
Expr::And(vec![expr])
} else {
Expr::Or(vec![expr])
}
}
Expr::Not(inner) => {
if op == '&' {
Expr::And(vec![Expr::Not(inner)])
} else {
Expr::Or(vec![Expr::Not(inner)])
}
}
Expr::And(values) => {
if op == '&' {
Expr::And(values)
} else {
Expr::Or(vec![Expr::And(values)])
}
}
Expr::Or(values) => {
if op == '|' {
Expr::Or(values)
} else {
Expr::And(vec![Expr::Or(values)])
}
}
});
self.current_bin_op = Some(op);
}
_ => return Err(ParseError::UnexpectedExpr),
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
if self.pending_negation > 0
|| self.full_expression.is_none()
|| self.current_bin_op.is_some()
{
return Err(ParseError::UnexpectedEnd);
}
Ok(self.full_expression.unwrap())
}
// Директно слагаме нов израз в текущия израз. Същото като добавяне на атом
pub fn push_expression(&mut self, mut expr: Expr) -> Result<(), ParseError> {
for _ in 0..self.pending_negation {
expr = Expr::Not(Box::new(expr));
}
self.pending_negation = 0;
match self.full_expression.as_mut() {
None => self.full_expression = Some(expr),
Some(Expr::And(values)) | Some(Expr::Or(values)) => {
if self.current_bin_op.is_none() {
return Err(ParseError::UnexpectedExpr);
}
values.push(expr);
self.current_bin_op = None;
}
_ => return Err(ParseError::UnexpectedExpr),
};
Ok(())
}
}
pub struct ExprParser {
expr_stack: Vec<SimpleExprParser>, // Работим със стек
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
expr_stack: vec![SimpleExprParser::new()],
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.current_parser()?.push_atom(c)
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.current_parser()?.push_op(op)
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.expr_stack.push(SimpleExprParser::new());
Ok(())
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.expr_stack.len() == 1 {
return Err(ParseError::UnexpectedParen);
}
let finished_expr = self.expr_stack.pop().unwrap().finish()?;
self.current_parser()?.push_expression(finished_expr)?;
Ok(())
}
pub fn finish(mut self) -> Result<Expr, ParseError> {
if self.expr_stack.len() > 1 {
return Err(ParseError::UnexpectedEnd);
}
self.expr_stack.pop().unwrap().finish()
}
fn current_parser(&mut self) -> Result<&mut SimpleExprParser, ParseError> {
self.expr_stack.last_mut().ok_or(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) => {
// Ако е атом, очевидно се връща или True, или False, или самият него
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(Expr::Atom(*c))
}
}
Expr::Not(inner) => match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(e) => Value::Expr(Expr::Not(Box::new(e))), // Връщаме новият израз с отрицание
},
Expr::And(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => continue, // True се поглъща
Value::False => return Value::False,
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::True, // Всички са True
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::And(new_expressions_list)), // Връщаме нов And с останалите
}
}
Expr::Or(list) => {
let mut new_expressions_list = vec![];
for expr in list {
match eval(expr, truthy, falsy) {
Value::True => return Value::True,
Value::False => continue, // False се поглъща
Value::Expr(e) => new_expressions_list.push(e),
}
}
match new_expressions_list.len() {
0 => Value::False, // Всички са False
1 => Value::Expr(new_expressions_list.remove(0)), // Ако е един елемент, връщаме самият него
_ => Value::Expr(Expr::Or(new_expressions_list)), // Връщаме нов Or с останалите
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[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();
assert_eq!(expr, Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]));
assert_eq!(Value::True, eval(&expr, &['A', 'B'], &[]));
assert_eq!(Value::False, 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']);
assert_eq!(
expr,
Expr::And(vec![
Expr::Atom('A'),
Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])
])
);
assert_eq!(
Value::Expr(Expr::Not(Box::new(Expr::Atom('C')))),
eval(&expr, &['A'], &['B'])
);
assert_eq!(Value::False, eval(&expr, &[], &['A']));
}
#[test]
fn test_advanced_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_op('!');
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();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &['B'], &['A']));
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
}
#[test]
fn test_simple_expr_parser() {
// A
let mut full_parser = ExprParser::new();
let _ = full_parser.push_atom('A');
let expr = full_parser.finish().unwrap();
println!("{:?}", expr);
assert_eq!(Value::True, eval(&expr, &['A'], &[]));
assert_eq!(Value::False, eval(&expr, &[], &['A']));
assert_eq!(Value::Expr(Expr::Atom('A')), eval(&expr, &[], &[]));
}
#[test]
fn test_basic_errors() {
// A & &
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));
// A & B B
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)
);
}
}