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

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

Решение на Логически изрази от Калоян Рибаров

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

Към профила на Калоян Рибаров

Резултати

  • 14 точки от тестове
  • 2 бонус точки
  • 16 точки общо
  • 14 успешни тест(а)
  • 6 неуспешни тест(а)

Код

use std::vec;
#[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),
}
#[macro_export]
macro_rules! not {
($a: expr) => {
Expr::Not(Box::new($a))
};
}
#[macro_export]
macro_rules! atom {
($a:literal) => {
Expr::Atom($a)
};
}
#[macro_export]
macro_rules! or {
{
$($a: expr),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::Or(acc)
}
};
}
#[macro_export]
macro_rules! and {
{
$( $a:expr ),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::And(acc)
}
}
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
/// Парсър за прост израз, който не съдържа скоби
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SimpleExprParser {
current_expr: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { current_expr: vec![] }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
_ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
'&' | '|' | '!' => panic!("Invalid atom provided"),
_ => Ok(self.current_expr.push(c))
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.current_expr.last().is_some() && {
let token = self.current_expr.last().unwrap();
token == &'&' || token == &'|'
} => Err(ParseError::UnexpectedBinOp),
'!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
'&' | '|' | '!' => Ok(self.current_expr.push(op)),
_ => panic!("Invalid operation provided")
}
}
fn build_expr_tree(&self) -> Result<Expr, ParseError> {
let mut acc: Option<Expr> = None;
let mut is_negated = false;
for token in &self.current_expr {
match token {
x if *x == '!' => {
is_negated = !is_negated;
},
x if is_atom(*x) => {
if let Some(Expr::And(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else if let Some(Expr::Or(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else {
if is_negated {
acc = Some(Expr::Not(Box::new(Expr::Atom(*x))));
is_negated = false;
} else {
acc = Some(Expr::Atom(*x))
}
}
},
x if acc.is_some() && !is_atom(*x) => {
let expr = acc.clone().unwrap();
if let Some(Expr::And(_)) = acc {
if *x == '|' {
acc = Some(Expr::Or(vec![expr]));
}
} else if let Some(Expr::Or(_)) = acc {
if *x == '&' {
acc = Some(Expr::And(vec![expr]));
}
} else {
acc = if *x == '&' {
Some(Expr::And(vec![expr]))
} else {
Some(Expr::Or(vec![expr]))
}
}
},
x if !is_atom(*x) => {
if let Some(existing_acc) = acc {
acc = Some(SimpleExprParser::gen_op(*x, existing_acc)?);
}
},
_ => {
return Err(ParseError::UnexpectedEnd)
}
}
}
acc.ok_or_else(||ParseError::UnexpectedEnd)
}
fn gen_op(char: char, curr_expr: Expr) -> Result<Expr, ParseError> {
match char {
'&' => Ok(Expr::And(vec![curr_expr])),
'|' => Ok(Expr::Or(vec![curr_expr])),
_ => Err(ParseError::UnexpectedUnaryOp)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
self.build_expr_tree()
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
/// Парсър за пълния израз
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}
#[test]
fn test_simple_expr_parser() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_atom('C');
let _ = parser.push_op('&');
let _ = parser.push_op('!');
let _ = parser.push_atom('C');
let expr = parser.finish().unwrap();
assert_eq!(expr, and!(atom!('C'), not!(atom!('C'))));
let value = eval(&expr, &[], &[]);
let value_expr = Value::Expr(and!(atom!('C'), not!(atom!('C'))));
assert_eq!(value, value_expr);
}
#[test]
fn test_simple_expr_parser_neg_at_start() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_op('!');
let _ = parser.push_atom('C');
let res_expr = parser.finish().unwrap();
let expr = not!(atom!('C'));
assert_eq!(res_expr, expr);
}
#[test]
fn test_simple_expr_parser_correct_errors() {
let mut parser = SimpleExprParser::new();
assert_eq!(Ok(()), parser.push_atom('A'));
assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('A'));
assert_eq!(Err(ParseError::UnexpectedUnaryOp), parser.push_op('!'));
let _ = parser.push_op('&');
assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('&'));
assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('|'));
assert_eq!(Ok(()), parser.push_op('!'));
}
#[test]
fn test_simple_expr_parser_empty_expr_does_not_panic() {
let parser = SimpleExprParser::new();
println!("{:?}", parser.finish());
}
#[test]
fn test_simple_expr_parser_correct_op_order() {
// !C & B | !A
let mut parser = SimpleExprParser::new();
let _ = parser.push_op('!');
let _ = parser.push_atom('C');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.push_op('|');
let _ = parser.push_op('!');
let _ = parser.push_atom('A');
let res_expr = parser.finish().unwrap();
let expr = or!(and!(not!(atom!('C')), atom!('B')), not!(atom!('A')));
assert_eq!(res_expr, expr);
}
#[test]
fn test_simple_expr_parser_correct_appending_multiple_ands() {
let mut parser = SimpleExprParser::new();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.push_op('&');
let _ = parser.push_atom('C');
let res_expr = parser.finish();
let expr = and!(atom!('A'), atom!('B'), atom!('C'));
assert_eq!(res_expr.unwrap(), expr);
}
#[test]
fn test_expr_parser() {
// !(A & B & !(C | B) )
let mut parser = ExprParser::new();
let _ = parser.push_op('!');
let _ = parser.open_paren();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.push_op('&');
let _ = parser.push_op('!');
let _ = parser.open_paren();
let _ = parser.push_atom('C');
let _ = parser.push_op('|');
let _ = parser.push_atom('B');
let _ = parser.close_paren();
let _ = parser.close_paren();
let expr = not!(and!(atom!('A'), atom!('B'), not!(or!(atom!('C'), atom!('B')))));
let result = parser.finish().unwrap();
assert_eq!(expr, result);
assert_eq!(eval(&result, &['C'], &[]), Value::True);
}
#[test]
fn test_expr_parser_multiple_negation() {
let mut parser = ExprParser::new();
let _ = parser.push_op('!');
let _ = parser.push_op('!');
let _ = parser.push_atom('B');
let result1 = parser.finish();
assert_eq!(result1.unwrap(), atom!('B'));
}
#[test]
fn test_expr_parser_correct_append_multiple_ands() {
// A & B & C & (C & A & B)
let mut parser = ExprParser::new();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.push_op('&');
let _ = parser.push_atom('C');
let _ = parser.push_op('&');
let _ = parser.open_paren();
let _ = parser.push_atom('C');
let _ = parser.push_op('&');
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.close_paren();
let res_expr = parser.finish();
let expr = and!(atom!('A'), atom!('B'), atom!('C'), and!(atom!('C'), atom!('A'), atom!('B')));
assert_eq!(res_expr.unwrap(), expr);
}
#[test]
fn test_eval_parans() {
let mut parser = ExprParser::new();
let _ = parser.push_op('!');
let _ = parser.open_paren();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('B');
let _ = parser.close_paren();
let expr = parser.finish().unwrap();
assert_eq!(eval(&expr, &[], &[]), Value::Expr(not!(and!(atom!('A'), atom!('B')))));
}
#[test]
fn test_expr_parser_multiple_negations_odd() {
let mut parser = ExprParser::new();
let _ = parser.push_op('!');
let _ = parser.push_op('!');
let _ = parser.push_op('!');
let _ = parser.push_atom('B');
let result2 = parser.finish();
assert_eq!(result2.unwrap(), not!(atom!('B')));
}
#[test]
fn test_expr_parser_empty_expr() {
let mut parser = ExprParser::new();
let _ = parser.open_paren();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.open_paren();
let _ = parser.close_paren();
let _ = parser.push_atom('B');
let _ = parser.close_paren();
let res = parser.finish();
assert_eq!(res.unwrap_err(), ParseError::UnexpectedEnd)
}
#[test]
fn test_expr_parser_open_parans_fewer_than_closing() {
let mut parser = ExprParser::new();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('C');
let _ = parser.push_op('&');
let _ = parser.open_paren();
let _ = parser.open_paren();
let _ = parser.push_atom('B');
let _ = parser.push_op('&');
let _ = parser.push_atom('A');
let _ = parser.close_paren();
assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
}
#[test]
fn test_expr_parser_open_parans_more_than_closing() {
let mut parser = ExprParser::new();
let _ = parser.push_atom('A');
let _ = parser.push_op('&');
let _ = parser.push_atom('C');
let _ = parser.push_op('&');
let _ = parser.open_paren();
let _ = parser.open_paren();
let _ = parser.push_atom('B');
let _ = parser.push_op('&');
let _ = parser.push_atom('A');
let _ = parser.close_paren();
let _ = parser.close_paren();
assert_eq!(parser.close_paren(), Err(ParseError::UnexpectedParen));
}
#[test]
fn test_expr_parser_basic_expr() {
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();
assert_eq!(expr, Ok(Expr::And(vec![Expr::Atom('A'), Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])])))
}
#[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();
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']);
}
#[test]
fn test_basic_errors() {
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));
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-1kv2psg/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.87s
     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 ... FAILED
test solution_test::test_paren_expr_priority ... ok
test solution_test::test_paren_around_expr ... FAILED
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_atom ... ok
test solution_test::test_parser_errors_basic ... FAILED
test solution_test::test_parser_error_unexpected_end ... 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 ... 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_unwrap_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Or([Atom('X'), 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'), 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_around_expr stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedUnaryOp', tests/solution_test.rs:190:40
thread 'solution_test::test_paren_around_expr' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedUnaryOp', tests/solution_test.rs:176: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

---- solution_test::test_parser_error_unexpected_end stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.finish(), Err(_))', tests/solution_test.rs:311:9
thread 'solution_test::test_parser_error_unexpected_end' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:305: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_unwrap_nested
    solution_test::test_paren_around_expr
    solution_test::test_parser_error_unexpected_end
    solution_test::test_parser_errors_basic
    solution_test::test_parser_multiple_not

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`

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

Калоян качи първо решение на 22.12.2024 23:03 (преди 9 месеца)

Калоян качи решение на 22.12.2024 23:03 (преди 9 месеца)

use std::vec;
#[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),
-}
+}
+
+impl Expr {
+ fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
+ match self {
+ Expr::Atom(x) => {
+ if truthy.contains(&x) {
+ Value::True
+ } else if falsy.contains(&x) {
+ Value::False
+ } else {
+ Value::Expr(Expr::Atom(x.clone()))
+ }
+ },
+ Expr::Not(inner) => {
+ let inner_value = inner.clone().eval_helper(truthy, falsy);
+ match inner_value {
+ Value::True => Value::False,
+ Value::False => Value::True,
+ Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
+ }
+ },
+ Expr::And(subexprs) => {
+ let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
+ if v.iter().all(|x| matches!(*x, Value::True)) {
+ return Value::True;
+ } else if v.iter().any(|x| matches!(*x, Value::False)) {
+ return Value::False;
+ } else {
+ let filtered: Vec<_> = v.into_iter().filter_map(|x| {
+ if let Value::Expr(expr) = x {
+ Some(expr)
+ } else {
+ None
+ }
+ }) // Extract the `Expr` value from `Value::Expr`
+ .collect();
+
+ if filtered.len() == 1 {
+ return Value::Expr(filtered.last().unwrap().clone());
+ }
+
+ Value::Expr(Expr::And(filtered))
+ }
+ },
+
+ Expr::Or(subexprs) => {
+ let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
+ if v.iter().all(|x| matches!(*x, Value::False)) {
+ return Value::False;
+ } else if v.iter().any(|x| matches!(*x, Value::True)) {
+ return Value::True;
+ } else {
+ let filtered: Vec<_> = v.into_iter()
+ .filter_map(|x| {
+ if let Value::Expr(expr) = x {
+ Some(expr)
+ } else {
+ None
+ }
+ }) // Extract the `Expr` value from `Value::Expr`
+ .collect();
+
+ if filtered.len() == 1 {
+ return Value::Expr(filtered.last().unwrap().clone());
+ }
+
+ return Value::Expr(Expr::Or(filtered));
+ }
+ },
+ }
+ }
+}

Калоян качи решение на 22.12.2024 23:04 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
+
+pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
+ expr.eval_helper(truthy, falsy)
+}

Калоян качи решение на 22.12.2024 23:06 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
+fn not(expr: Expr, is_negated: &mut bool) -> Expr {
+ if *is_negated {
+ *is_negated = !(*is_negated);
+ return Expr::Not(Box::new(expr));
+ }
+
+ expr
+}
+
+fn is_atom(ch: char) -> bool {
+ ch != '&' && ch != '|' && ch != '!'
+}
+
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:11 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
+pub struct ExprParser {
+ tokens: Vec<char>,
+ open_parans_count: usize
+}
+
+impl ExprParser {
+ pub fn new() -> ExprParser {
+ ExprParser { tokens: vec![], open_parans_count: 0}
+ }
+/// Приема атом.
+ ///
+ /// `c` ще бъде валиден символ за атом.
+ /// В противен случай можете да panic-нете (няма да се тества)
+ pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
+ match c {
+ '&' | '|' | '!' | '(' | ')' => {
+ Err(ParseError::UnexpectedExpr)
+ }
+ _ => {
+ Ok(self.tokens.push(c))
+ }
+ }
+ }
+}
+
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:18 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
+
+ /// Приема символ за операция.
+ ///
+ /// `op` ще бъде едно от '&', '|', '!'.
+ /// В противен случай можете да panic-нете (няма да се тества)
+ pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
+ match op {
+ '&' | '|' if self.tokens.last().is_some() && {
+ let token = self.tokens.last().unwrap();
+ token != &'|' && token != &'&' && token != &'('
+ } => {
+ Ok(self.tokens.push(op))
+ },
+ '!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
+ Ok(self.tokens.push(op))
+ },
+ '!' => {
+ Err(ParseError::UnexpectedUnaryOp)
+ }
+ _ => Err(ParseError::UnexpectedBinOp)
+ }
+ }
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:20 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
+
+ /// Приема отваряща скоба.
+ pub fn open_paren(&mut self) -> Result<(), ParseError> {
+ self.open_parans_count += 1;
+ Ok(self.tokens.push('('))
+ }
+
+ /// Приема затваряща скоба.
+ pub fn close_paren(&mut self) -> Result<(), ParseError> {
+ if self.open_parans_count < 1 {
+ return Err(ParseError::UnexpectedParen);
+ }
+
+ if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
+ return Err(ParseError::UnexpectedEnd);
+ }
+
+ self.open_parans_count -= 1;
+ Ok(self.tokens.push(')'))
+
+ }
+
+ fn is_op(ch: &char) -> bool {
+ ch == &'&' || ch == &'|' || ch == &'!'
+ }
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:20 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
+ pub fn parse_expr(&self) -> Result<Expr, ParseError> {
+ let mut iter = self.tokens.clone().into_iter();
+ ExprParser::parse_expr_helper(&mut iter, None, false)
+ }
+
+ fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
+ if let Some(ch) = iter.next() {
+ match ch {
+ '&' => {
+ if let Some(expr) = curr_expr {
+ curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
+ return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
+ } else {
+ return Err(ParseError::UnexpectedBinOp);
+ }
+ },
+ '|' => {
+ if let Some(expr) = curr_expr {
+ curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
+ return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
+
+ } else {
+ return Err(ParseError::UnexpectedBinOp);
+ }
+ },
+ '(' => {
+ let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
+ match curr_expr {
+
+ Some(Expr::And(ref mut v)) => {
+ v.push(not(sub_expr, &mut is_negated));
+ return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
+ },
+ Some(Expr::Or(ref mut v)) => {
+ v.push(not(sub_expr, &mut is_negated));
+
+ return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
+ },
+ Some(Expr::Not(expr)) => {
+ let unwrapped = ExprParser::unwrap_recur(*expr);
+ match unwrapped {
+ Expr::Atom(ch) => {
+ return Ok(Expr::Atom(ch));
+ },
+ Expr::And(mut subexprs) => {
+ subexprs.push(not(sub_expr, &mut is_negated));
+ return Ok(Expr::And(subexprs));
+ },
+ Expr::Or(mut subexprs) => {
+ subexprs.push(not(sub_expr, &mut is_negated));
+ return Ok(Expr::Or(subexprs));
+ },
+
+ _ => {
+ return Err(ParseError::UnexpectedBinOp);
+ }
+ }
+
+ },
+ Some(Expr::Atom(_)) => {
+ return Err(ParseError::UnexpectedExpr)
+ },
+ None => {
+ return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
+ }
+ }
+ },
+ ')' => {
+ // Handle closing parenthesis if needed
+ if curr_expr.is_some() {
+ return Ok(curr_expr.unwrap());
+ } else {
+ return Err(ParseError::UnexpectedEnd);
+ }
+ },
+ '!' => {
+ is_negated = !is_negated;
+ return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
+ },
+ ch => {
+ let new_atom = Expr::Atom(ch);
+ let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
+ return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
+ },
+ }
+ }
+
+ curr_expr.ok_or(ParseError::UnexpectedEnd)
+ }
+
+
+ fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
+ match curr_expr {
+ a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
+ n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
+ a@Expr::And(_) => Ok(not(a, is_negated)),
+ o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
+ }
+ }
+
+ fn unwrap_recur(expr: Expr) -> Expr {
+ match expr {
+ Expr::Not(inner_box) => {
+ ExprParser::unwrap_recur(*inner_box)
+ },
+ inner_expr => inner_expr
+ }
+ }
+
+ fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
+ match curr_expr {
+ Some(Expr::And(mut v)) => {
+ v.push(not(atom, is_negated));
+ Ok(Expr::And(v))
+ }
+ Some(Expr::Atom(_)) => {
+ Err(ParseError::UnexpectedExpr)
+ },
+ Some(Expr::Not(expr)) => {
+ let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
+ match first_not_boxed_expr {
+ Expr::And(v) => {
+ let mut cpy = v.clone();
+ cpy.push(not(atom, is_negated));
+ Ok(Expr::And(cpy))
+ },
+ Expr::Or(v) => {
+ let mut cpy = v.clone();
+ cpy.push(not(atom, is_negated));
+ Ok(Expr::Or(cpy))
+ }
+ _ => Err(ParseError::UnexpectedExpr)
+ }
+ },
+ Some(Expr::Or(mut v)) => {
+ v.push(not(atom, is_negated));
+ Ok(Expr::Or(v))
+ },
+ None => {
+ Ok(not(atom, is_negated))
+ }
+ }
+ }
+
+ fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
+ match curr_expr {
+ Expr::Atom(a) => {
+ Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
+ },
+ Expr::Not(n) => {
+ Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
+ },
+ Expr::And(a) => {
+ Ok(not(Expr::Or(a.clone()), &mut is_negated))
+ },
+ Expr::Or(o) => {
+ Ok(not(Expr::Or(o.clone()), &mut is_negated))
+ },
+ }
+ }
+
+ /// Завършва парсването и връща построения израз.
+ pub fn finish(self) -> Result<Expr, ParseError> {
+ if self.open_parans_count > 0 {
+ return Err(ParseError::UnexpectedEnd);
+ }
+
+ let mut x = self.tokens;
+ x.insert(0, '(');
+ x.push(')');
+
+ let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
+ p.parse_expr()
+ }
+
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:27 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
+/// Парсър за прост израз, който не съдържа скоби
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct SimpleExprParser {
+ current_expr: Vec<char>
+}
+
+impl SimpleExprParser {
+ pub fn new() -> SimpleExprParser {
+ SimpleExprParser { current_expr: vec![] }
+ }
+
+ /// Приема атом.
+ ///
+ /// `c` ще бъде валиден символ за атом.
+ /// В противен случай можете да panic-нете (няма да се тества)
+ pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
+ match c {
+ _ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
+ '&' | '|' | '!' => panic!("Invalid atom provided"),
+ _ => Ok(self.current_expr.push(c))
+ }
+ }
+
+/// Приема символ за операция.
+ ///
+ /// `op` ще бъде едно от '&', '|', '!'.
+ /// В противен случай можете да panic-нете (няма да се тества)
+ pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
+ match op {
+ '&' | '|' if self.current_expr.last().is_some() && {
+ let token = self.current_expr.last().unwrap();
+ token == &'&' || token == &'|'
+ } => Err(ParseError::UnexpectedBinOp),
+ '!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
+ '&' | '|' | '!' => Ok(self.current_expr.push(op)),
+ _ => panic!("Invalid operation provided")
+ }
+ }
+}
+
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:27 (преди 9 месеца)

use std::vec;
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
/// Парсър за прост израз, който не съдържа скоби
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SimpleExprParser {
current_expr: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { current_expr: vec![] }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
_ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
'&' | '|' | '!' => panic!("Invalid atom provided"),
_ => Ok(self.current_expr.push(c))
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.current_expr.last().is_some() && {
let token = self.current_expr.last().unwrap();
token == &'&' || token == &'|'
} => Err(ParseError::UnexpectedBinOp),
'!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
'&' | '|' | '!' => Ok(self.current_expr.push(op)),
_ => panic!("Invalid operation provided")
}
}
+
+fn build_expr_tree(&self) -> Result<Expr, ParseError> {
+ let mut acc: Option<Expr> = None;
+ let mut is_negated = false;
+
+ for token in &self.current_expr {
+ match token {
+ x if *x == '!' => {
+ is_negated = !is_negated;
+ },
+ x if is_atom(*x) => {
+ if let Some(Expr::And(ref mut v)) = acc {
+ if is_negated {
+ v.push(Expr::Not(Box::new(Expr::Atom(*token))));
+ is_negated = false;
+ } else {
+ v.push(Expr::Atom(*token))
+ }
+
+ } else if let Some(Expr::Or(ref mut v)) = acc {
+ if is_negated {
+
+ v.push(Expr::Not(Box::new(Expr::Atom(*token))));
+ is_negated = false;
+ } else {
+ v.push(Expr::Atom(*token))
+ }
+ } else {
+ if is_negated {
+ acc = Some(Expr::Not(Box::new(Expr::Atom(*x))));
+ is_negated = false;
+ } else {
+ acc = Some(Expr::Atom(*x))
+ }
+ }
+ },
+ x if acc.is_some() && !is_atom(*x) => {
+ let expr = acc.clone().unwrap();
+ if let Some(Expr::And(_)) = acc {
+ if *x == '|' {
+ acc = Some(Expr::Or(vec![expr]));
+ }
+
+ } else if let Some(Expr::Or(_)) = acc {
+
+ if *x == '&' {
+ acc = Some(Expr::And(vec![expr]));
+ }
+
+ } else {
+ acc = if *x == '&' {
+ Some(Expr::And(vec![expr]))
+ } else {
+ Some(Expr::Or(vec![expr]))
+ }
+ }
+ },
+ x if !is_atom(*x) => {
+ if let Some(existing_acc) = acc {
+ acc = Some(SimpleExprParser::gen_op(*x, existing_acc)?);
+ }
+ },
+ _ => {
+ return Err(ParseError::UnexpectedEnd)
+ }
+
+ }
+ }
+
+ acc.ok_or_else(||ParseError::UnexpectedEnd)
+ }
+
+ fn gen_op(char: char, curr_expr: Expr) -> Result<Expr, ParseError> {
+ match char {
+ '&' => Ok(Expr::And(vec![curr_expr])),
+ '|' => Ok(Expr::Or(vec![curr_expr])),
+ _ => Err(ParseError::UnexpectedUnaryOp)
+ }
+ }
+
+ /// Завършва парсването и връща построения израз.
+ pub fn finish(self) -> Result<Expr, ParseError> {
+ self.build_expr_tree()
+ }
+
}
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:28 (преди 9 месеца)

use std::vec;
+#[macro_export]
+macro_rules! not {
+ ($a: expr) => {
+ Expr::Not(Box::new($a))
+ };
+}
+#[macro_export]
+macro_rules! atom {
+ ($a:literal) => {
+ Expr::Atom($a)
+ };
+}
+
+#[macro_export]
+macro_rules! or {
+ {
+ $($a: expr),+
+ } => {
+ {
+ let mut acc = Vec::new();
+ $( acc.push($a); )+
+ Expr::Or(acc)
+ }
+ };
+}
+
+#[macro_export]
+macro_rules! and {
+ {
+ $( $a:expr ),+
+ } => {
+ {
+ let mut acc = Vec::new();
+ $( acc.push($a); )+
+ Expr::And(acc)
+ }
+ }
+}
+
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
/// Парсър за прост израз, който не съдържа скоби
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SimpleExprParser {
current_expr: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { current_expr: vec![] }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
_ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
'&' | '|' | '!' => panic!("Invalid atom provided"),
_ => Ok(self.current_expr.push(c))
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.current_expr.last().is_some() && {
let token = self.current_expr.last().unwrap();
token == &'&' || token == &'|'
} => Err(ParseError::UnexpectedBinOp),
'!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
'&' | '|' | '!' => Ok(self.current_expr.push(op)),
_ => panic!("Invalid operation provided")
}
}
fn build_expr_tree(&self) -> Result<Expr, ParseError> {
let mut acc: Option<Expr> = None;
let mut is_negated = false;
for token in &self.current_expr {
match token {
x if *x == '!' => {
is_negated = !is_negated;
},
x if is_atom(*x) => {
if let Some(Expr::And(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else if let Some(Expr::Or(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else {
if is_negated {
acc = Some(Expr::Not(Box::new(Expr::Atom(*x))));
is_negated = false;
} else {
acc = Some(Expr::Atom(*x))
}
}
},
x if acc.is_some() && !is_atom(*x) => {
let expr = acc.clone().unwrap();
if let Some(Expr::And(_)) = acc {
if *x == '|' {
acc = Some(Expr::Or(vec![expr]));
}
} else if let Some(Expr::Or(_)) = acc {
if *x == '&' {
acc = Some(Expr::And(vec![expr]));
}
} else {
acc = if *x == '&' {
Some(Expr::And(vec![expr]))
} else {
Some(Expr::Or(vec![expr]))
}
}
},
x if !is_atom(*x) => {
if let Some(existing_acc) = acc {
acc = Some(SimpleExprParser::gen_op(*x, existing_acc)?);
}
},
_ => {
return Err(ParseError::UnexpectedEnd)
}
}
}
acc.ok_or_else(||ParseError::UnexpectedEnd)
}
fn gen_op(char: char, curr_expr: Expr) -> Result<Expr, ParseError> {
match char {
'&' => Ok(Expr::And(vec![curr_expr])),
'|' => Ok(Expr::Or(vec![curr_expr])),
_ => Err(ParseError::UnexpectedUnaryOp)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
self.build_expr_tree()
}
}
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}

Калоян качи решение на 22.12.2024 23:28 (преди 9 месеца)

use std::vec;
#[macro_export]
macro_rules! not {
($a: expr) => {
Expr::Not(Box::new($a))
};
}
#[macro_export]
macro_rules! atom {
($a:literal) => {
Expr::Atom($a)
};
}
#[macro_export]
macro_rules! or {
{
$($a: expr),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::Or(acc)
}
};
}
#[macro_export]
macro_rules! and {
{
$( $a:expr ),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::And(acc)
}
}
}
#[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),
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
/// Парсър за прост израз, който не съдържа скоби
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SimpleExprParser {
current_expr: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { current_expr: vec![] }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
_ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
'&' | '|' | '!' => panic!("Invalid atom provided"),
_ => Ok(self.current_expr.push(c))
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.current_expr.last().is_some() && {
let token = self.current_expr.last().unwrap();
token == &'&' || token == &'|'
} => Err(ParseError::UnexpectedBinOp),
'!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
'&' | '|' | '!' => Ok(self.current_expr.push(op)),
_ => panic!("Invalid operation provided")
}
}
fn build_expr_tree(&self) -> Result<Expr, ParseError> {
let mut acc: Option<Expr> = None;
let mut is_negated = false;
for token in &self.current_expr {
match token {
x if *x == '!' => {
is_negated = !is_negated;
},
x if is_atom(*x) => {
if let Some(Expr::And(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else if let Some(Expr::Or(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else {
if is_negated {
acc = Some(Expr::Not(Box::new(Expr::Atom(*x))));
is_negated = false;
} else {
acc = Some(Expr::Atom(*x))
}
}
},
x if acc.is_some() && !is_atom(*x) => {
let expr = acc.clone().unwrap();
if let Some(Expr::And(_)) = acc {
if *x == '|' {
acc = Some(Expr::Or(vec![expr]));
}
} else if let Some(Expr::Or(_)) = acc {
if *x == '&' {
acc = Some(Expr::And(vec![expr]));
}
} else {
acc = if *x == '&' {
Some(Expr::And(vec![expr]))
} else {
Some(Expr::Or(vec![expr]))
}
}
},
x if !is_atom(*x) => {
if let Some(existing_acc) = acc {
acc = Some(SimpleExprParser::gen_op(*x, existing_acc)?);
}
},
_ => {
return Err(ParseError::UnexpectedEnd)
}
}
}
acc.ok_or_else(||ParseError::UnexpectedEnd)
}
fn gen_op(char: char, curr_expr: Expr) -> Result<Expr, ParseError> {
match char {
'&' => Ok(Expr::And(vec![curr_expr])),
'|' => Ok(Expr::Or(vec![curr_expr])),
_ => Err(ParseError::UnexpectedUnaryOp)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
self.build_expr_tree()
}
}
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
}
+
+#[test]
+fn test_simple_expr_parser() {
+ let mut parser = SimpleExprParser::new();
+
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('C');
+
+ let expr = parser.finish().unwrap();
+
+ assert_eq!(expr, and!(atom!('C'), not!(atom!('C'))));
+
+ let value = eval(&expr, &[], &[]);
+
+ let value_expr = Value::Expr(and!(atom!('C'), not!(atom!('C'))));
+ assert_eq!(value, value_expr);
+}
+
+#[test]
+fn test_simple_expr_parser_neg_at_start() {
+ let mut parser = SimpleExprParser::new();
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('C');
+
+ let res_expr = parser.finish().unwrap();
+ let expr = not!(atom!('C'));
+
+ assert_eq!(res_expr, expr);
+}
+
+#[test]
+fn test_simple_expr_parser_correct_errors() {
+ let mut parser = SimpleExprParser::new();
+
+ assert_eq!(Ok(()), parser.push_atom('A'));
+ assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('A'));
+ assert_eq!(Err(ParseError::UnexpectedUnaryOp), parser.push_op('!'));
+
+ let _ = parser.push_op('&');
+ assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('&'));
+ assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('|'));
+ assert_eq!(Ok(()), parser.push_op('!'));
+}
+
+#[test]
+fn test_simple_expr_parser_empty_expr_does_not_panic() {
+ let parser = SimpleExprParser::new();
+ println!("{:?}", parser.finish());
+}
+
+#[test]
+fn test_simple_expr_parser_correct_op_order() {
+ // !C & B | !A
+ let mut parser = SimpleExprParser::new();
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('|');
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('A');
+
+ let res_expr = parser.finish().unwrap();
+ let expr = or!(and!(not!(atom!('C')), atom!('B')), not!(atom!('A')));
+
+ assert_eq!(res_expr, expr);
+}
+
+#[test]
+fn test_simple_expr_parser_correct_appending_multiple_ands() {
+ let mut parser = SimpleExprParser::new();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+
+ let res_expr = parser.finish();
+ let expr = and!(atom!('A'), atom!('B'), atom!('C'));
+
+ assert_eq!(res_expr.unwrap(), expr);
+
+}
+
+#[test]
+fn test_expr_parser() {
+ // !(A & B & !(C | B) )
+
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.open_paren();
+
+ let _ = parser.push_atom('A');
+
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+
+ let _ = parser.push_op('!');
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('|');
+
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+ let _ = parser.close_paren();
+
+ let expr = not!(and!(atom!('A'), atom!('B'), not!(or!(atom!('C'), atom!('B')))));
+
+ let result = parser.finish().unwrap();
+ assert_eq!(expr, result);
+
+ assert_eq!(eval(&result, &['C'], &[]), Value::True);
+}
+
+#[test]
+fn test_expr_parser_multiple_negation() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.push_op('!');
+
+ let _ = parser.push_atom('B');
+
+ let result1 = parser.finish();
+
+ assert_eq!(result1.unwrap(), atom!('B'));
+}
+
+#[test]
+fn test_expr_parser_correct_append_multiple_ands() {
+ // A & B & C & (C & A & B)
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+
+
+ let res_expr = parser.finish();
+ let expr = and!(atom!('A'), atom!('B'), atom!('C'), and!(atom!('C'), atom!('A'), atom!('B')));
+
+ assert_eq!(res_expr.unwrap(), expr);
+
+}
+
+#[test]
+fn test_eval_parans() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+
+ let expr = parser.finish().unwrap();
+
+ assert_eq!(eval(&expr, &[], &[]), Value::Expr(not!(and!(atom!('A'), atom!('B')))));
+
+}
+
+#[test]
+fn test_expr_parser_multiple_negations_odd() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.push_op('!');
+ let _ = parser.push_op('!');
+
+ let _ = parser.push_atom('B');
+
+ let result2 = parser.finish();
+
+ assert_eq!(result2.unwrap(), not!(atom!('B')));
+}
+
+#[test]
+fn test_expr_parser_empty_expr() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.close_paren();
+
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+ let res = parser.finish();
+
+ assert_eq!(res.unwrap_err(), ParseError::UnexpectedEnd)
+}
+
+#[test]
+fn test_expr_parser_open_parans_fewer_than_closing() {
+ let mut parser = ExprParser::new();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('A');
+ let _ = parser.close_paren();
+
+ assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
+}
+
+
+#[test]
+fn test_expr_parser_open_parans_more_than_closing() {
+ let mut parser = ExprParser::new();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('A');
+ let _ = parser.close_paren();
+ let _ = parser.close_paren();
+
+ assert_eq!(parser.close_paren(), Err(ParseError::UnexpectedParen));
+}
+
+#[test]
+fn test_expr_parser_basic_expr() {
+ 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();
+ assert_eq!(expr, Ok(Expr::And(vec![Expr::Atom('A'), Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])])))
+}
+
+#[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();
+
+ 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']);
+}
+
+#[test]
+fn test_basic_errors() {
+ 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));
+
+ 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 23:32 (преди 9 месеца)

use std::vec;
+#[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),
+}
+
#[macro_export]
macro_rules! not {
($a: expr) => {
Expr::Not(Box::new($a))
};
}
#[macro_export]
macro_rules! atom {
($a:literal) => {
Expr::Atom($a)
};
}
#[macro_export]
macro_rules! or {
{
$($a: expr),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::Or(acc)
}
};
}
#[macro_export]
macro_rules! and {
{
$( $a:expr ),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::And(acc)
}
}
}
-#[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),
-}
-
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
-fn not(expr: Expr, is_negated: &mut bool) -> Expr {
- if *is_negated {
- *is_negated = !(*is_negated);
- return Expr::Not(Box::new(expr));
- }
-
- expr
-}
-
-fn is_atom(ch: char) -> bool {
- ch != '&' && ch != '|' && ch != '!'
-}
-
/// Парсър за прост израз, който не съдържа скоби
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SimpleExprParser {
current_expr: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { current_expr: vec![] }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
_ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
'&' | '|' | '!' => panic!("Invalid atom provided"),
_ => Ok(self.current_expr.push(c))
}
}
-/// Приема символ за операция.
+ /// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.current_expr.last().is_some() && {
let token = self.current_expr.last().unwrap();
token == &'&' || token == &'|'
} => Err(ParseError::UnexpectedBinOp),
'!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
'&' | '|' | '!' => Ok(self.current_expr.push(op)),
_ => panic!("Invalid operation provided")
}
}
-fn build_expr_tree(&self) -> Result<Expr, ParseError> {
+ fn build_expr_tree(&self) -> Result<Expr, ParseError> {
let mut acc: Option<Expr> = None;
let mut is_negated = false;
for token in &self.current_expr {
match token {
x if *x == '!' => {
is_negated = !is_negated;
},
x if is_atom(*x) => {
if let Some(Expr::And(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else if let Some(Expr::Or(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else {
if is_negated {
acc = Some(Expr::Not(Box::new(Expr::Atom(*x))));
is_negated = false;
} else {
acc = Some(Expr::Atom(*x))
}
}
},
x if acc.is_some() && !is_atom(*x) => {
let expr = acc.clone().unwrap();
if let Some(Expr::And(_)) = acc {
if *x == '|' {
acc = Some(Expr::Or(vec![expr]));
}
} else if let Some(Expr::Or(_)) = acc {
if *x == '&' {
acc = Some(Expr::And(vec![expr]));
}
} else {
acc = if *x == '&' {
Some(Expr::And(vec![expr]))
} else {
Some(Expr::Or(vec![expr]))
}
}
},
x if !is_atom(*x) => {
if let Some(existing_acc) = acc {
acc = Some(SimpleExprParser::gen_op(*x, existing_acc)?);
}
},
_ => {
return Err(ParseError::UnexpectedEnd)
}
}
}
acc.ok_or_else(||ParseError::UnexpectedEnd)
}
fn gen_op(char: char, curr_expr: Expr) -> Result<Expr, ParseError> {
match char {
'&' => Ok(Expr::And(vec![curr_expr])),
'|' => Ok(Expr::Or(vec![curr_expr])),
_ => Err(ParseError::UnexpectedUnaryOp)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
self.build_expr_tree()
}
}
+fn not(expr: Expr, is_negated: &mut bool) -> Expr {
+ if *is_negated {
+ *is_negated = !(*is_negated);
+ return Expr::Not(Box::new(expr));
+ }
+
+ expr
+}
+
+fn is_atom(ch: char) -> bool {
+ ch != '&' && ch != '|' && ch != '!'
+}
+
+/// Парсър за пълния израз
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
-/// Приема атом.
+
+ /// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
- }
+ }
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
- /// Приема отваряща скоба.
+ /// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
- pub fn parse_expr(&self) -> Result<Expr, ParseError> {
+ pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
- fn is_op(ch: &char) -> bool {
+ fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
+
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
-}
-
+}
-#[test]
-fn test_simple_expr_parser() {
- let mut parser = SimpleExprParser::new();
-
- let _ = parser.push_atom('C');
- let _ = parser.push_op('&');
- let _ = parser.push_op('!');
- let _ = parser.push_atom('C');
-
- let expr = parser.finish().unwrap();
-
- assert_eq!(expr, and!(atom!('C'), not!(atom!('C'))));
-
- let value = eval(&expr, &[], &[]);
-
- let value_expr = Value::Expr(and!(atom!('C'), not!(atom!('C'))));
- assert_eq!(value, value_expr);
-}
-
-#[test]
-fn test_simple_expr_parser_neg_at_start() {
- let mut parser = SimpleExprParser::new();
- let _ = parser.push_op('!');
- let _ = parser.push_atom('C');
-
- let res_expr = parser.finish().unwrap();
- let expr = not!(atom!('C'));
-
- assert_eq!(res_expr, expr);
-}
-
-#[test]
-fn test_simple_expr_parser_correct_errors() {
- let mut parser = SimpleExprParser::new();
-
- assert_eq!(Ok(()), parser.push_atom('A'));
- assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('A'));
- assert_eq!(Err(ParseError::UnexpectedUnaryOp), parser.push_op('!'));
-
- let _ = parser.push_op('&');
- assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('&'));
- assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('|'));
- assert_eq!(Ok(()), parser.push_op('!'));
-}
-
-#[test]
-fn test_simple_expr_parser_empty_expr_does_not_panic() {
- let parser = SimpleExprParser::new();
- println!("{:?}", parser.finish());
-}
-
-#[test]
-fn test_simple_expr_parser_correct_op_order() {
- // !C & B | !A
- let mut parser = SimpleExprParser::new();
- let _ = parser.push_op('!');
- let _ = parser.push_atom('C');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('B');
- let _ = parser.push_op('|');
- let _ = parser.push_op('!');
- let _ = parser.push_atom('A');
-
- let res_expr = parser.finish().unwrap();
- let expr = or!(and!(not!(atom!('C')), atom!('B')), not!(atom!('A')));
-
- assert_eq!(res_expr, expr);
-}
-
-#[test]
-fn test_simple_expr_parser_correct_appending_multiple_ands() {
- let mut parser = SimpleExprParser::new();
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('B');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('C');
-
- let res_expr = parser.finish();
- let expr = and!(atom!('A'), atom!('B'), atom!('C'));
-
- assert_eq!(res_expr.unwrap(), expr);
-
-}
-
-#[test]
-fn test_expr_parser() {
- // !(A & B & !(C | B) )
-
- let mut parser = ExprParser::new();
-
- let _ = parser.push_op('!');
- let _ = parser.open_paren();
-
- let _ = parser.push_atom('A');
-
- let _ = parser.push_op('&');
- let _ = parser.push_atom('B');
- let _ = parser.push_op('&');
-
- let _ = parser.push_op('!');
- let _ = parser.open_paren();
- let _ = parser.push_atom('C');
- let _ = parser.push_op('|');
-
- let _ = parser.push_atom('B');
- let _ = parser.close_paren();
- let _ = parser.close_paren();
-
- let expr = not!(and!(atom!('A'), atom!('B'), not!(or!(atom!('C'), atom!('B')))));
-
- let result = parser.finish().unwrap();
- assert_eq!(expr, result);
-
- assert_eq!(eval(&result, &['C'], &[]), Value::True);
-}
-
-#[test]
-fn test_expr_parser_multiple_negation() {
- let mut parser = ExprParser::new();
-
- let _ = parser.push_op('!');
- let _ = parser.push_op('!');
-
- let _ = parser.push_atom('B');
-
- let result1 = parser.finish();
-
- assert_eq!(result1.unwrap(), atom!('B'));
-}
-
-#[test]
-fn test_expr_parser_correct_append_multiple_ands() {
- // A & B & C & (C & A & B)
- let mut parser = ExprParser::new();
-
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('B');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('C');
- let _ = parser.push_op('&');
- let _ = parser.open_paren();
- let _ = parser.push_atom('C');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('B');
- let _ = parser.close_paren();
-
-
- let res_expr = parser.finish();
- let expr = and!(atom!('A'), atom!('B'), atom!('C'), and!(atom!('C'), atom!('A'), atom!('B')));
-
- assert_eq!(res_expr.unwrap(), expr);
-
-}
-
-#[test]
-fn test_eval_parans() {
- let mut parser = ExprParser::new();
-
- let _ = parser.push_op('!');
- let _ = parser.open_paren();
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('B');
- let _ = parser.close_paren();
-
- let expr = parser.finish().unwrap();
-
- assert_eq!(eval(&expr, &[], &[]), Value::Expr(not!(and!(atom!('A'), atom!('B')))));
-
-}
-
-#[test]
-fn test_expr_parser_multiple_negations_odd() {
- let mut parser = ExprParser::new();
-
- let _ = parser.push_op('!');
- let _ = parser.push_op('!');
- let _ = parser.push_op('!');
-
- let _ = parser.push_atom('B');
-
- let result2 = parser.finish();
-
- assert_eq!(result2.unwrap(), not!(atom!('B')));
-}
-
-#[test]
-fn test_expr_parser_empty_expr() {
- let mut parser = ExprParser::new();
-
- let _ = parser.open_paren();
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.open_paren();
- let _ = parser.close_paren();
-
- let _ = parser.push_atom('B');
- let _ = parser.close_paren();
- let res = parser.finish();
-
- assert_eq!(res.unwrap_err(), ParseError::UnexpectedEnd)
-}
-
-#[test]
-fn test_expr_parser_open_parans_fewer_than_closing() {
- let mut parser = ExprParser::new();
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('C');
- let _ = parser.push_op('&');
- let _ = parser.open_paren();
- let _ = parser.open_paren();
- let _ = parser.push_atom('B');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('A');
- let _ = parser.close_paren();
-
- assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
-}
-
-
-#[test]
-fn test_expr_parser_open_parans_more_than_closing() {
- let mut parser = ExprParser::new();
- let _ = parser.push_atom('A');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('C');
- let _ = parser.push_op('&');
- let _ = parser.open_paren();
- let _ = parser.open_paren();
- let _ = parser.push_atom('B');
- let _ = parser.push_op('&');
- let _ = parser.push_atom('A');
- let _ = parser.close_paren();
- let _ = parser.close_paren();
-
- assert_eq!(parser.close_paren(), Err(ParseError::UnexpectedParen));
-}
-
-#[test]
-fn test_expr_parser_basic_expr() {
- 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();
- assert_eq!(expr, Ok(Expr::And(vec![Expr::Atom('A'), Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])])))
-}
-
-#[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();
-
- 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']);
-}
-
-#[test]
-fn test_basic_errors() {
- 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));
-
- 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 23:32 (преди 9 месеца)

use std::vec;
#[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),
}
#[macro_export]
macro_rules! not {
($a: expr) => {
Expr::Not(Box::new($a))
};
}
#[macro_export]
macro_rules! atom {
($a:literal) => {
Expr::Atom($a)
};
}
#[macro_export]
macro_rules! or {
{
$($a: expr),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::Or(acc)
}
};
}
#[macro_export]
macro_rules! and {
{
$( $a:expr ),+
} => {
{
let mut acc = Vec::new();
$( acc.push($a); )+
Expr::And(acc)
}
}
}
impl Expr {
fn eval_helper(&self, truthy: &[char], falsy: &[char]) -> Value {
match self {
Expr::Atom(x) => {
if truthy.contains(&x) {
Value::True
} else if falsy.contains(&x) {
Value::False
} else {
Value::Expr(Expr::Atom(x.clone()))
}
},
Expr::Not(inner) => {
let inner_value = inner.clone().eval_helper(truthy, falsy);
match inner_value {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(_) => Value::Expr(Expr::Not(inner.clone())),
}
},
Expr::And(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::True)) {
return Value::True;
} else if v.iter().any(|x| matches!(*x, Value::False)) {
return Value::False;
} else {
let filtered: Vec<_> = v.into_iter().filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
Value::Expr(Expr::And(filtered))
}
},
Expr::Or(subexprs) => {
let v: Vec<_> = subexprs.iter().map(|expr| expr.clone().eval_helper(truthy, falsy)).collect();
if v.iter().all(|x| matches!(*x, Value::False)) {
return Value::False;
} else if v.iter().any(|x| matches!(*x, Value::True)) {
return Value::True;
} else {
let filtered: Vec<_> = v.into_iter()
.filter_map(|x| {
if let Value::Expr(expr) = x {
Some(expr)
} else {
None
}
}) // Extract the `Expr` value from `Value::Expr`
.collect();
if filtered.len() == 1 {
return Value::Expr(filtered.last().unwrap().clone());
}
return Value::Expr(Expr::Or(filtered));
}
},
}
}
}
/// Парсър за прост израз, който не съдържа скоби
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SimpleExprParser {
current_expr: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { current_expr: vec![] }
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
_ if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedExpr),
'&' | '|' | '!' => panic!("Invalid atom provided"),
_ => Ok(self.current_expr.push(c))
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.current_expr.last().is_some() && {
let token = self.current_expr.last().unwrap();
token == &'&' || token == &'|'
} => Err(ParseError::UnexpectedBinOp),
'!' if self.current_expr.last().is_some() && is_atom(*self.current_expr.last().unwrap()) => Err(ParseError::UnexpectedUnaryOp),
'&' | '|' | '!' => Ok(self.current_expr.push(op)),
_ => panic!("Invalid operation provided")
}
}
fn build_expr_tree(&self) -> Result<Expr, ParseError> {
let mut acc: Option<Expr> = None;
let mut is_negated = false;
for token in &self.current_expr {
match token {
x if *x == '!' => {
is_negated = !is_negated;
},
x if is_atom(*x) => {
if let Some(Expr::And(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else if let Some(Expr::Or(ref mut v)) = acc {
if is_negated {
v.push(Expr::Not(Box::new(Expr::Atom(*token))));
is_negated = false;
} else {
v.push(Expr::Atom(*token))
}
} else {
if is_negated {
acc = Some(Expr::Not(Box::new(Expr::Atom(*x))));
is_negated = false;
} else {
acc = Some(Expr::Atom(*x))
}
}
},
x if acc.is_some() && !is_atom(*x) => {
let expr = acc.clone().unwrap();
if let Some(Expr::And(_)) = acc {
if *x == '|' {
acc = Some(Expr::Or(vec![expr]));
}
} else if let Some(Expr::Or(_)) = acc {
if *x == '&' {
acc = Some(Expr::And(vec![expr]));
}
} else {
acc = if *x == '&' {
Some(Expr::And(vec![expr]))
} else {
Some(Expr::Or(vec![expr]))
}
}
},
x if !is_atom(*x) => {
if let Some(existing_acc) = acc {
acc = Some(SimpleExprParser::gen_op(*x, existing_acc)?);
}
},
_ => {
return Err(ParseError::UnexpectedEnd)
}
}
}
acc.ok_or_else(||ParseError::UnexpectedEnd)
}
fn gen_op(char: char, curr_expr: Expr) -> Result<Expr, ParseError> {
match char {
'&' => Ok(Expr::And(vec![curr_expr])),
'|' => Ok(Expr::Or(vec![curr_expr])),
_ => Err(ParseError::UnexpectedUnaryOp)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
self.build_expr_tree()
}
}
fn not(expr: Expr, is_negated: &mut bool) -> Expr {
if *is_negated {
*is_negated = !(*is_negated);
return Expr::Not(Box::new(expr));
}
expr
}
fn is_atom(ch: char) -> bool {
ch != '&' && ch != '|' && ch != '!'
}
/// Парсър за пълния израз
pub struct ExprParser {
tokens: Vec<char>,
open_parans_count: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { tokens: vec![], open_parans_count: 0}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'&' | '|' | '!' | '(' | ')' => {
Err(ParseError::UnexpectedExpr)
}
_ => {
Ok(self.tokens.push(c))
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'&' | '|' if self.tokens.last().is_some() && {
let token = self.tokens.last().unwrap();
token != &'|' && token != &'&' && token != &'('
} => {
Ok(self.tokens.push(op))
},
'!' if matches!(self.tokens.last(), None) || !is_atom(*self.tokens.last().unwrap()) => {
Ok(self.tokens.push(op))
},
'!' => {
Err(ParseError::UnexpectedUnaryOp)
}
_ => Err(ParseError::UnexpectedBinOp)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
self.open_parans_count += 1;
Ok(self.tokens.push('('))
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.open_parans_count < 1 {
return Err(ParseError::UnexpectedParen);
}
if self.tokens.last().is_some() && ExprParser::is_op(self.tokens.last().unwrap()) {
return Err(ParseError::UnexpectedEnd);
}
self.open_parans_count -= 1;
Ok(self.tokens.push(')'))
}
pub fn parse_expr(&self) -> Result<Expr, ParseError> {
let mut iter = self.tokens.clone().into_iter();
ExprParser::parse_expr_helper(&mut iter, None, false)
}
fn parse_expr_helper(iter: &mut dyn Iterator<Item = char>, mut curr_expr: Option<Expr>, mut is_negated: bool) -> Result<Expr, ParseError> {
if let Some(ch) = iter.next() {
match ch {
'&' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_conj(expr, &mut is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'|' => {
if let Some(expr) = curr_expr {
curr_expr = Some(ExprParser::handle_disj(expr, is_negated)?);
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated);
} else {
return Err(ParseError::UnexpectedBinOp);
}
},
'(' => {
let sub_expr = ExprParser::parse_expr_helper(iter, None, false)?;
match curr_expr {
Some(Expr::And(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Or(ref mut v)) => {
v.push(not(sub_expr, &mut is_negated));
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
Some(Expr::Not(expr)) => {
let unwrapped = ExprParser::unwrap_recur(*expr);
match unwrapped {
Expr::Atom(ch) => {
return Ok(Expr::Atom(ch));
},
Expr::And(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::And(subexprs));
},
Expr::Or(mut subexprs) => {
subexprs.push(not(sub_expr, &mut is_negated));
return Ok(Expr::Or(subexprs));
},
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Some(Expr::Atom(_)) => {
return Err(ParseError::UnexpectedExpr)
},
None => {
return ExprParser::parse_expr_helper(iter, Some(not(sub_expr, &mut is_negated)), is_negated)
}
}
},
')' => {
// Handle closing parenthesis if needed
if curr_expr.is_some() {
return Ok(curr_expr.unwrap());
} else {
return Err(ParseError::UnexpectedEnd);
}
},
'!' => {
is_negated = !is_negated;
return ExprParser::parse_expr_helper(iter, curr_expr, is_negated)
},
ch => {
let new_atom = Expr::Atom(ch);
let new_curr_expr = ExprParser::handle_atom(curr_expr, new_atom, &mut is_negated)?;
return ExprParser::parse_expr_helper(iter, Some(new_curr_expr), is_negated)
},
}
}
curr_expr.ok_or(ParseError::UnexpectedEnd)
}
fn handle_conj(curr_expr: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
a@Expr::Atom(_) => Ok(not(Expr::And(vec![a]), is_negated)),
n@Expr::Not(_) => Ok(not(Expr::And(vec![n]), is_negated)),
a@Expr::And(_) => Ok(not(a, is_negated)),
o@Expr::Or(_) => Ok(not(Expr::And(vec![o]), is_negated)),
}
}
fn unwrap_recur(expr: Expr) -> Expr {
match expr {
Expr::Not(inner_box) => {
ExprParser::unwrap_recur(*inner_box)
},
inner_expr => inner_expr
}
}
fn handle_atom(curr_expr: Option<Expr>, atom: Expr, is_negated: &mut bool) -> Result<Expr, ParseError> {
match curr_expr {
Some(Expr::And(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::And(v))
}
Some(Expr::Atom(_)) => {
Err(ParseError::UnexpectedExpr)
},
Some(Expr::Not(expr)) => {
let first_not_boxed_expr = ExprParser::unwrap_recur(*expr);
match first_not_boxed_expr {
Expr::And(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::And(cpy))
},
Expr::Or(v) => {
let mut cpy = v.clone();
cpy.push(not(atom, is_negated));
Ok(Expr::Or(cpy))
}
_ => Err(ParseError::UnexpectedExpr)
}
},
Some(Expr::Or(mut v)) => {
v.push(not(atom, is_negated));
Ok(Expr::Or(v))
},
None => {
Ok(not(atom, is_negated))
}
}
}
fn handle_disj(curr_expr: Expr, mut is_negated: bool) -> Result<Expr, ParseError> {
match curr_expr {
Expr::Atom(a) => {
Ok(not(Expr::Or(vec![Expr::Atom(a)]), &mut is_negated))
},
Expr::Not(n) => {
Ok(Expr::Or(vec![Expr::Not(Box::new(*n))]))
},
Expr::And(a) => {
Ok(not(Expr::Or(a.clone()), &mut is_negated))
},
Expr::Or(o) => {
Ok(not(Expr::Or(o.clone()), &mut is_negated))
},
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.open_parans_count > 0 {
return Err(ParseError::UnexpectedEnd);
}
let mut x = self.tokens;
x.insert(0, '(');
x.push(')');
let p = ExprParser {tokens: x, open_parans_count: self.open_parans_count};
p.parse_expr()
}
fn is_op(ch: &char) -> bool {
ch == &'&' || ch == &'|' || ch == &'!'
}
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
expr.eval_helper(truthy, falsy)
+}
+
+
+#[test]
+fn test_simple_expr_parser() {
+ let mut parser = SimpleExprParser::new();
+
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('C');
+
+ let expr = parser.finish().unwrap();
+
+ assert_eq!(expr, and!(atom!('C'), not!(atom!('C'))));
+
+ let value = eval(&expr, &[], &[]);
+
+ let value_expr = Value::Expr(and!(atom!('C'), not!(atom!('C'))));
+ assert_eq!(value, value_expr);
+}
+
+#[test]
+fn test_simple_expr_parser_neg_at_start() {
+ let mut parser = SimpleExprParser::new();
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('C');
+
+ let res_expr = parser.finish().unwrap();
+ let expr = not!(atom!('C'));
+
+ assert_eq!(res_expr, expr);
+}
+
+#[test]
+fn test_simple_expr_parser_correct_errors() {
+ let mut parser = SimpleExprParser::new();
+
+ assert_eq!(Ok(()), parser.push_atom('A'));
+ assert_eq!(Err(ParseError::UnexpectedExpr), parser.push_atom('A'));
+ assert_eq!(Err(ParseError::UnexpectedUnaryOp), parser.push_op('!'));
+
+ let _ = parser.push_op('&');
+ assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('&'));
+ assert_eq!(Err(ParseError::UnexpectedBinOp), parser.push_op('|'));
+ assert_eq!(Ok(()), parser.push_op('!'));
+}
+
+#[test]
+fn test_simple_expr_parser_empty_expr_does_not_panic() {
+ let parser = SimpleExprParser::new();
+ println!("{:?}", parser.finish());
+}
+
+#[test]
+fn test_simple_expr_parser_correct_op_order() {
+ // !C & B | !A
+ let mut parser = SimpleExprParser::new();
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('|');
+ let _ = parser.push_op('!');
+ let _ = parser.push_atom('A');
+
+ let res_expr = parser.finish().unwrap();
+ let expr = or!(and!(not!(atom!('C')), atom!('B')), not!(atom!('A')));
+
+ assert_eq!(res_expr, expr);
+}
+
+#[test]
+fn test_simple_expr_parser_correct_appending_multiple_ands() {
+ let mut parser = SimpleExprParser::new();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+
+ let res_expr = parser.finish();
+ let expr = and!(atom!('A'), atom!('B'), atom!('C'));
+
+ assert_eq!(res_expr.unwrap(), expr);
+
+}
+
+#[test]
+fn test_expr_parser() {
+ // !(A & B & !(C | B) )
+
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.open_paren();
+
+ let _ = parser.push_atom('A');
+
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+
+ let _ = parser.push_op('!');
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('|');
+
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+ let _ = parser.close_paren();
+
+ let expr = not!(and!(atom!('A'), atom!('B'), not!(or!(atom!('C'), atom!('B')))));
+
+ let result = parser.finish().unwrap();
+ assert_eq!(expr, result);
+
+ assert_eq!(eval(&result, &['C'], &[]), Value::True);
+}
+
+#[test]
+fn test_expr_parser_multiple_negation() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.push_op('!');
+
+ let _ = parser.push_atom('B');
+
+ let result1 = parser.finish();
+
+ assert_eq!(result1.unwrap(), atom!('B'));
+}
+
+#[test]
+fn test_expr_parser_correct_append_multiple_ands() {
+ // A & B & C & (C & A & B)
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+
+
+ let res_expr = parser.finish();
+ let expr = and!(atom!('A'), atom!('B'), atom!('C'), and!(atom!('C'), atom!('A'), atom!('B')));
+
+ assert_eq!(res_expr.unwrap(), expr);
+
+}
+
+#[test]
+fn test_eval_parans() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+
+ let expr = parser.finish().unwrap();
+
+ assert_eq!(eval(&expr, &[], &[]), Value::Expr(not!(and!(atom!('A'), atom!('B')))));
+
+}
+
+#[test]
+fn test_expr_parser_multiple_negations_odd() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.push_op('!');
+ let _ = parser.push_op('!');
+ let _ = parser.push_op('!');
+
+ let _ = parser.push_atom('B');
+
+ let result2 = parser.finish();
+
+ assert_eq!(result2.unwrap(), not!(atom!('B')));
+}
+
+#[test]
+fn test_expr_parser_empty_expr() {
+ let mut parser = ExprParser::new();
+
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.close_paren();
+
+ let _ = parser.push_atom('B');
+ let _ = parser.close_paren();
+ let res = parser.finish();
+
+ assert_eq!(res.unwrap_err(), ParseError::UnexpectedEnd)
+}
+
+#[test]
+fn test_expr_parser_open_parans_fewer_than_closing() {
+ let mut parser = ExprParser::new();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('A');
+ let _ = parser.close_paren();
+
+ assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
+}
+
+
+#[test]
+fn test_expr_parser_open_parans_more_than_closing() {
+ let mut parser = ExprParser::new();
+ let _ = parser.push_atom('A');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('C');
+ let _ = parser.push_op('&');
+ let _ = parser.open_paren();
+ let _ = parser.open_paren();
+ let _ = parser.push_atom('B');
+ let _ = parser.push_op('&');
+ let _ = parser.push_atom('A');
+ let _ = parser.close_paren();
+ let _ = parser.close_paren();
+
+ assert_eq!(parser.close_paren(), Err(ParseError::UnexpectedParen));
+}
+
+#[test]
+fn test_expr_parser_basic_expr() {
+ 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();
+ assert_eq!(expr, Ok(Expr::And(vec![Expr::Atom('A'), Expr::Or(vec![Expr::Atom('B'), Expr::Not(Box::new(Expr::Atom('C')))])])))
+}
+
+#[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();
+
+ 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']);
+}
+
+#[test]
+fn test_basic_errors() {
+ 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));
+
+ 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));
}