Решение на Логически изрази от Милица Тончева
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 5 неуспешни тест(а)
Код
use std::cmp::max;
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
Atom(char),
Not(Box<Expr>),
And(Vec<Expr>),
Or(Vec<Expr>),
}
pub fn atom(c: char) -> Expr {
Expr::Atom(c)
}
pub fn not(e: Expr) -> Expr {
Expr::Not(Box::new(e))
}
pub fn and(e: Vec<Expr>) -> Expr {
Expr::And(e)
}
pub fn or(e: Vec<Expr>) -> Expr {
Expr::Or(e)
}
pub fn is_valid_atom(c: char) -> bool {
!is_valid_binary_op(c) &&
!is_valid_unary_op(c) &&
!is_open_paren(c) &&
!is_close_paren(c) &&
!c.is_whitespace()
}
pub fn is_valid_binary_op(c: char) -> bool {
c == '&' || c == '|'
}
pub fn is_valid_unary_op(c: char) -> bool {
c == '!'
}
pub fn is_open_paren(c: char) -> bool {
c == '('
}
pub fn is_close_paren(c: char) -> bool {
c == ')'
}
#[derive(Debug, PartialEq, Eq)]
pub enum ParseError {
UnexpectedExpr,
UnexpectedUnaryOp,
UnexpectedBinOp,
UnexpectedParen,
UnexpectedEnd,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
atoms: Vec<char>,
operators: Vec<char>,
last_el: char,
needed_atoms: usize,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
atoms: Vec::new(),
operators: Vec::new(),
last_el: ' ',
needed_atoms: 1,
}
}
/// Приема атом.
///
/// c ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if !is_valid_atom(c) {
panic!("invalid character for atom");
}
if !is_valid_binary_op(self.last_el) &&
!is_valid_unary_op(self.last_el) &&
!self.last_el.is_whitespace() {
return Err(ParseError::UnexpectedExpr);
}
self.atoms.push(c);
self.last_el = c;
Result::Ok(())
}
fn push_binary(&mut self, op: char) -> Result<(), ParseError> {
if !is_valid_atom(self.last_el) {
return Err(ParseError::UnexpectedBinOp);
}
self.last_el = op;
self.operators.push(op);
if self.needed_atoms == 0 {
self.needed_atoms = 2;
}
else {
self.needed_atoms += 1;
}
Result::Ok(())
}
fn push_unary(&mut self, op: char) -> Result<(), ParseError> {
if is_valid_atom(self.last_el) {
return Err(ParseError::UnexpectedUnaryOp);
}
self.last_el = op;
self.operators.push(op);
self.needed_atoms = max(self.needed_atoms, 1);
Result::Ok(())
}
/// Приема символ за операция.
///
/// op ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
if !is_valid_binary_op(op) && !is_valid_unary_op(op) {
panic!("invalid character for operator");
}
if is_valid_binary_op(op) {
self.push_binary(op)
}
else {
self.push_unary(op)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.atoms.is_empty() ||
self.atoms.len() != self.needed_atoms {
return Result::Err(ParseError::UnexpectedExpr);
}
let mut curr_expr: Expr = Expr::Atom(self.atoms[0]);
if self.operators.is_empty() {
return Ok(curr_expr);
}
let mut i:usize = 1;
let mut j:usize = 0;
if self.operators[0] == '!' {
curr_expr = not(curr_expr);
j += 1;
if self.operators.len() == 1 {
return Ok(curr_expr);
}
}
while j < self.operators.len(){
if self.operators[j].eq(&'&') {
if j+1 < self.operators.len() && is_valid_unary_op(self.operators[j + 1]){
curr_expr = and(vec![curr_expr, not(atom(self.atoms[i]))]);
j+=1;
}
else {
curr_expr = and(vec![curr_expr, atom(self.atoms[i])]);
}
i+=1;
j+=1;
}
else if self.operators[j].eq(&'|') {
if j+1 < self.operators.len() && is_valid_unary_op(self.operators[j + 1]){
curr_expr = or(vec![curr_expr, not(atom(self.atoms[i]))]);
j+=1;
}
else {
curr_expr = or(vec![curr_expr, atom(self.atoms[i])]);
}
i+=1;
j+=1;
}
else {
curr_expr = not(atom(self.atoms[i]));
i+=1;
j+=1;
}
}
Result::Ok(curr_expr)
}
}
/// Парсър за пълния израз
pub struct ExprParser {
complex_atoms: Vec<Vec<char>>,
operators: Vec<char>,
last_el: char,
needed_atoms: usize,
opened_paren: usize,
complex_atoms_index: usize
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
complex_atoms: Vec::new(),
operators: Vec::new(),
last_el: ' ',
needed_atoms: 1,
opened_paren: 0,
complex_atoms_index: 0
}
}
/// Приема атом.
///
/// c ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if !is_valid_atom(c) {
panic!("invalid character for atom");
}
if !is_valid_binary_op(self.last_el) &&
!is_valid_unary_op(self.last_el) &&
!self.last_el.is_whitespace() &&
self.last_el != '('{
return Err(ParseError::UnexpectedExpr);
}
if self.opened_paren == 0 {
self.complex_atoms.push(Vec::new());
self.complex_atoms_index = self.complex_atoms.len() - 1;
}
self.complex_atoms[self.complex_atoms_index].push(c);
self.last_el = c;
Result::Ok(())
}
fn push_binary(&mut self, op: char) -> Result<(), ParseError> {
if !is_valid_atom(self.last_el) &&
!is_close_paren(self.last_el){
return Err(ParseError::UnexpectedBinOp);
}
if self.opened_paren > 0 {
self.complex_atoms[self.complex_atoms_index].push(op);
}
else {
self.operators.push(op);
}
if self.opened_paren == 0 {
if self.needed_atoms == 0 {
self.needed_atoms = 2;
} else {
self.needed_atoms += 1;
}
}
self.last_el = op;
Result::Ok(())
}
fn push_unary(&mut self, op: char) -> Result<(), ParseError> {
if is_valid_atom(self.last_el) || is_close_paren(self.last_el) {
return Err(ParseError::UnexpectedUnaryOp);
}
if self.opened_paren > 0 {
self.complex_atoms[self.complex_atoms_index].push(op);
}
else {
self.operators.push(op);
}
self.last_el = op;
if self.opened_paren == 0 {
self.needed_atoms = max(self.needed_atoms, 1);
}
Result::Ok(())
}
/// Приема символ за операция.
///
/// op ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
if !is_valid_binary_op(op) && !is_valid_unary_op(op) {
panic!("invalid character for operator");
}
if is_valid_binary_op(op) {
self.push_binary(op)
}
else {
self.push_unary(op)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if is_valid_atom(self.last_el) {
return Result::Err(ParseError::UnexpectedParen);
}
self.last_el = '(';
self.complex_atoms.push(Vec::new());
self.complex_atoms_index = self.complex_atoms.len() - 1;
self.opened_paren += 1;
Result::Ok(())
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if is_valid_binary_op(self.last_el) ||
self.opened_paren == 0 ||
is_valid_unary_op(self.last_el) {
return Result::Err(ParseError::UnexpectedParen);
}
self.last_el = ')';
self.opened_paren -=1;
if self.opened_paren != 0 {
self.complex_atoms_index -= 1;
}
Result::Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if self.complex_atoms.is_empty() ||
self.complex_atoms.len() < self.needed_atoms ||
self.opened_paren != 0{
return Result::Err(ParseError::UnexpectedExpr);
}
let mut simple_expr_atoms: Vec<Expr> = Vec::new();
for atom in self.complex_atoms {
let mut sep = SimpleExprParser::new();
for char in atom {
if is_valid_atom(char) {
let _ = sep.push_atom(char);
}
else {
let _ = sep.push_op(char);
}
}
simple_expr_atoms.push(sep.finish().unwrap());
}
let mut curr_expr = simple_expr_atoms[0].clone();
if self.operators.is_empty() {
return Ok(curr_expr);
}
let mut i:usize = 1;
let mut j:usize = 0;
if is_valid_unary_op(self.operators[0]) {
curr_expr = not(curr_expr);
j += 1;
if self.operators.len() == 1 {
return Ok(curr_expr);
}
}
while j < self.operators.len(){
if self.operators[j].eq(&'&') {
if j+1 < self.operators.len() && is_valid_unary_op(self.operators[j + 1]){
curr_expr = and(vec![curr_expr, not(simple_expr_atoms[i].clone())]);
j+=1;
}
else {
curr_expr = and(vec![curr_expr, simple_expr_atoms[i].clone()]);
}
i+=1;
j+=1;
}
else if self.operators[j].eq(&'|') {
if j+1 < self.operators.len() && is_valid_unary_op(self.operators[j + 1]){
curr_expr = or(vec![curr_expr, not(simple_expr_atoms[i].clone())]);
j+=1;
}
else {
curr_expr = or(vec![curr_expr, simple_expr_atoms[i].clone()]);
}
i+=1;
j+=1;
}
else {
curr_expr = not(simple_expr_atoms[i].clone());
i+=1;
j+=1;
}
}
Result::Ok(curr_expr)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
True,
False,
Expr(Expr),
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
match expr {
Expr::Atom(atom) => {
if truthy.contains(&atom) {
Value::True
} else if falsy.contains(&atom) {
Value::False
} else {
Value::Expr(expr.clone())
}
}
Expr::Not(inner) => {
match eval(inner, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(inner_expr) => Value::Expr(Expr::Not(Box::new(inner_expr))),
}
}
// Evaluating AND operation
Expr::And(operands) => {
let mut simplified_operands = Vec::new();
let mut is_any_false = false;
for operand in operands {
match eval(operand, truthy, falsy) {
Value::True => {
continue;
}
Value::False => {
is_any_false = true;
break;
}
Value::Expr(sub_expr) => {
simplified_operands.push(sub_expr);
}
}
}
if is_any_false {
Value::False
} else if simplified_operands.is_empty() {
Value::True
} else if simplified_operands.len() == 1 {
Value::Expr(simplified_operands.into_iter().next().unwrap())
} else {
Value::Expr(Expr::And(simplified_operands))
}
}
// Evaluating OR operation
Expr::Or(operands) => {
let mut simplified_operands = Vec::new();
let mut is_any_true = false;
for operand in operands {
match eval(operand, truthy, falsy) {
Value::True => {
is_any_true = true;
break;
}
Value::False => {
continue;
}
Value::Expr(sub_expr) => {
simplified_operands.push(sub_expr);
}
}
}
if is_any_true {
Value::True
} else if simplified_operands.is_empty() {
Value::False
} else if simplified_operands.len() == 1 {
Value::Expr(simplified_operands.into_iter().next().unwrap())
} else {
Value::Expr(Expr::Or(simplified_operands))
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-5x65pb/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.78s
Running tests/solution_test.rs (target/debug/deps/solution_test-1428e1090729d165)
running 20 tests
test solution_test::test_eval_full ... ok
test solution_test::test_error_paren_mismatched ... FAILED
test solution_test::test_eval_not_and_or ... ok
test solution_test::test_eval_partial ... ok
test solution_test::test_eval_unwrap_and_or ... ok
test solution_test::test_eval_unwrap_nested ... ok
test solution_test::test_paren_around_expr ... ok
test solution_test::test_paren_expr_priority ... ok
test solution_test::test_paren_nested ... FAILED
test solution_test::test_paren_not ... ok
test solution_test::test_parser_alternating_ops ... ok
test solution_test::test_paren_surrounded ... FAILED
test solution_test::test_parser_and_or ... ok
test solution_test::test_parser_atom ... ok
test solution_test::test_parser_error_unexpected_end ... ok
test solution_test::test_parser_errors_basic ... ok
test solution_test::test_parser_expr_and_not ... ok
test solution_test::test_parser_multiple_atoms_same_op ... FAILED
test solution_test::test_parser_multiple_not ... FAILED
test solution_test::test_parser_not ... ok
failures:
---- solution_test::test_error_paren_mismatched stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.close_paren(), Err(_))', tests/solution_test.rs:331:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'solution_test::test_error_paren_mismatched' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:325:5
---- solution_test::test_paren_nested stdout ----
thread '<unnamed>' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedExpr', src/lib.rs:347:49
thread 'solution_test::test_paren_nested' panicked at 'called `Result::unwrap()` on an `Err` value: UnexpectedExpr', tests/solution_test.rs:252:5
---- solution_test::test_paren_surrounded stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Or([Or([Or([Atom('X'), And([Atom('A'), Atom('B')])]), And([Atom('C'), Atom('D')])]), Atom('Y')])`,
right: `Or([Atom('X'), And([Atom('A'), Atom('B')]), And([Atom('C'), Atom('D')]), Atom('Y')])`', tests/solution_test.rs:238:9
thread 'solution_test::test_paren_surrounded' panicked at 'assertion failed: `(left == right)`
left: `Or([Or([Or([Atom('X'), And([Atom('A'), Atom('B')])]), And([Atom('C'), Atom('D')])]), Atom('Y')])`,
right: `Or([Atom('X'), And([Atom('A'), Atom('B')]), And([Atom('C'), Atom('D')]), Atom('Y')])`', tests/solution_test.rs:235:5
---- solution_test::test_parser_multiple_atoms_same_op stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `And([And([Atom('A'), Atom('B')]), Atom('C')])`,
right: `And([Atom('A'), Atom('B'), Atom('C')])`', tests/solution_test.rs:127:9
thread 'solution_test::test_parser_multiple_atoms_same_op' panicked at 'assertion failed: `(left == right)`
left: `And([And([Atom('A'), Atom('B')]), Atom('C')])`,
right: `And([Atom('A'), Atom('B'), Atom('C')])`', tests/solution_test.rs:124:5
---- solution_test::test_parser_multiple_not stdout ----
thread '<unnamed>' panicked at 'index out of bounds: the len is 1 but the index is 1', src/lib.rs:187:38
thread 'solution_test::test_parser_multiple_not' panicked at 'index out of bounds: the len is 1 but the index is 1', tests/solution_test.rs:140:5
failures:
solution_test::test_error_paren_mismatched
solution_test::test_paren_nested
solution_test::test_paren_surrounded
solution_test::test_parser_multiple_atoms_same_op
solution_test::test_parser_multiple_not
test result: FAILED. 15 passed; 5 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`