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

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

Решение на Логически изрази от Симеон Георгиев

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

Към профила на Симеон Георгиев

Резултати

  • 13 точки от тестове
  • 0 бонус точки
  • 13 точки общо
  • 13 успешни тест(а)
  • 7 неуспешни тест(а)

Код

use std::collections::VecDeque;
#[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(Debug)]
enum SimpleExprParserState {
ExpectingAtomOrNot,
ExpectingBinaryOp,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
state: SimpleExprParserState,
expressions: VecDeque<Expr>,
operations: VecDeque<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
Self {
state: SimpleExprParserState::ExpectingAtomOrNot,
expressions: VecDeque::new(),
operations: VecDeque::new(),
}
}
pub fn push_expr(&mut self, expr: Expr) -> Result<(), ParseError> {
match self.state {
SimpleExprParserState::ExpectingAtomOrNot => (),
SimpleExprParserState::ExpectingBinaryOp => return Err(ParseError::UnexpectedExpr),
}
self.expressions.push_back(expr);
self.state = SimpleExprParserState::ExpectingBinaryOp;
Ok(())
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.push_expr(Expr::Atom(c))
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' | '&' | '|' => (),
'(' | ')' => return Err(ParseError::UnexpectedParen),
_ => return Err(ParseError::UnexpectedExpr),
}
match self.state {
SimpleExprParserState::ExpectingAtomOrNot if op != '!' => return Err(ParseError::UnexpectedBinOp),
SimpleExprParserState::ExpectingBinaryOp if op == '!' => return Err(ParseError::UnexpectedUnaryOp),
_ => (),
}
self.operations.push_back(op);
self.state = SimpleExprParserState::ExpectingAtomOrNot;
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
// println!("{:?}", self.state);
match self.state {
SimpleExprParserState::ExpectingAtomOrNot => return Err(ParseError::UnexpectedEnd),
SimpleExprParserState::ExpectingBinaryOp => (),
}
let mut operations = self.operations.clone();
let mut expressions = self.expressions.clone();
// println!("operations {:?}", operations);
// println!("expressions {:?}", expressions);
while let Some(op) = operations.pop_front() {
let expression = expressions.pop_front().unwrap();
if op == '!' {
expressions.push_front(Expr::Not(Box::new(expression)));
} else if op == '&' || op == '|' {
let mut op_members = VecDeque::from([expression]);
// println!("op_members {:?}", op_members);
while let Some(&next_op) = operations.front() {
if next_op != op {
break;
}
op_members.push_back(expressions.pop_front().unwrap());
operations.pop_front();
}
op_members.push_back(expressions.pop_front().unwrap());
// println!("op_members {:?}", op_members);
expressions.push_front(
match op {
'&' => Expr::And(op_members.into()),
'|' => Expr::Or(op_members.into()),
_ => panic!("dont know this")
}
)
} else {
panic!("wtf");
}
}
// println!("{}", expressions.len());
if expressions.len() == 1 {
Ok(expressions.pop_front().unwrap())
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
previous_parsers: Vec<SimpleExprParser>,
}
impl ExprParser {
pub fn new() -> ExprParser {
Self {
previous_parsers: Vec::from([SimpleExprParser::new()]),
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.previous_parsers.last_mut().unwrap().push_atom(c)
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.previous_parsers.last_mut().unwrap().push_op(op)
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
match self.previous_parsers.last().unwrap().state {
SimpleExprParserState::ExpectingBinaryOp => return Err(ParseError::UnexpectedParen),
_ => (),
}
// println!("open before push {:?}", self.previous_parsers.len());
self.previous_parsers.push(SimpleExprParser::new());
// println!("open after push {:?}", self.previous_parsers.len());
Ok(())
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
// println!("close {:?} {:?}", self.previous_parsers.len(), self.previous_parsers.last().unwrap().state);
match self.previous_parsers.last().unwrap().state {
SimpleExprParserState::ExpectingAtomOrNot => return Err(ParseError::UnexpectedParen),
_ => (),
}
// println!("close before pop {:?}", self.previous_parsers.len());
let current_parser = self.previous_parsers.pop().ok_or(ParseError::UnexpectedParen)?;
// println!("close after pop {:?}", self.previous_parsers.len());
match current_parser.finish() {
Ok(expr) => self.previous_parsers.last_mut()
.ok_or(ParseError::UnexpectedParen)?
.push_expr(expr)?,
Err(e) => return Err(e),
}
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
// println!("finish {:?}", self.previous_parsers.len());
if self.previous_parsers.len() == 1 {
self.previous_parsers.into_iter().next().unwrap().finish()
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
True,
False,
Expr(Expr),
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
match expr {
Expr::Atom(c) => {
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(expr.clone())
}
}
Expr::Not(sub_expr) => match eval(sub_expr, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
expr => expr,
},
Expr::And(operands) => {
let mut unevaluated_operands = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::False => return Value::False,
Value::True => continue,
Value::Expr(expr) => unevaluated_operands.push(expr),
}
}
match unevaluated_operands.len() {
0 => Value::True,
1 => Value::Expr(unevaluated_operands[0].clone()),
_ => Value::Expr(Expr::And(unevaluated_operands))
}
}
Expr::Or(operands) => {
let mut unevaluated_operands = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::False => continue,
Value::True => return Value::True,
Value::Expr(expr) => unevaluated_operands.push(expr),
}
}
match unevaluated_operands.len() {
0 => Value::False,
1 => Value::Expr(unevaluated_operands[0].clone()),
_ => Value::Expr(Expr::Or(unevaluated_operands))
}
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20241224-258381-2qgw9d/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.85s
     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 ... ok
test solution_test::test_eval_not_and_or ... ok
test solution_test::test_eval_partial ... FAILED
test solution_test::test_eval_unwrap_nested ... FAILED
test solution_test::test_eval_unwrap_and_or ... FAILED
test solution_test::test_paren_around_expr ... ok
test solution_test::test_paren_expr_priority ... ok
test solution_test::test_paren_not ... FAILED
test solution_test::test_paren_nested ... FAILED
test solution_test::test_paren_surrounded ... ok
test solution_test::test_parser_alternating_ops ... ok
test solution_test::test_parser_and_or ... ok
test solution_test::test_parser_atom ... ok
test solution_test::test_parser_error_unexpected_end ... ok
test solution_test::test_parser_errors_basic ... ok
test solution_test::test_parser_expr_and_not ... FAILED
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_eval_partial stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Atom('B'))`,
 right: `Expr(Not(Atom('B')))`', tests/solution_test.rs:411:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'solution_test::test_eval_partial' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Atom('B'))`,
 right: `Expr(Not(Atom('B')))`', tests/solution_test.rs:409:5

---- solution_test::test_eval_unwrap_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Or([Atom('X'), Atom('B'), 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'), 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_eval_unwrap_and_or stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Atom('B'))`,
 right: `Expr(Not(Atom('B')))`', tests/solution_test.rs:466:9
thread 'solution_test::test_eval_unwrap_and_or' panicked at 'assertion failed: `(left == right)`
  left: `Expr(Atom('B'))`,
 right: `Expr(Not(Atom('B')))`', tests/solution_test.rs:456:5

---- solution_test::test_paren_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Not(And([Atom('X'), Or([Atom('A'), Atom('B')])]))`,
 right: `And([Atom('X'), Not(Or([Atom('A'), Atom('B')]))])`', tests/solution_test.rs:219:9
thread 'solution_test::test_paren_not' panicked at 'assertion failed: `(left == right)`
  left: `Not(And([Atom('X'), Or([Atom('A'), Atom('B')])]))`,
 right: `And([Atom('X'), Not(Or([Atom('A'), Atom('B')]))])`', tests/solution_test.rs:216:5

---- solution_test::test_paren_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Not(Not(And([Atom('A'), Not(And([Atom('B'), And([Atom('C'), Atom('D')])]))])))`,
 right: `Not(And([Atom('A'), Not(And([Atom('B'), Not(And([Atom('C'), Atom('D')]))]))]))`', tests/solution_test.rs:255:9
thread 'solution_test::test_paren_nested' panicked at 'assertion failed: `(left == right)`
  left: `Not(Not(And([Atom('A'), Not(And([Atom('B'), And([Atom('C'), Atom('D')])]))])))`,
 right: `Not(And([Atom('A'), Not(And([Atom('B'), Not(And([Atom('C'), Atom('D')]))]))]))`', tests/solution_test.rs:252:5

---- solution_test::test_parser_expr_and_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Not(And([Atom('A'), Atom('B')]))`,
 right: `And([Atom('A'), Not(Atom('B'))])`', tests/solution_test.rs:110:9
thread 'solution_test::test_parser_expr_and_not' panicked at 'assertion failed: `(left == right)`
  left: `Not(And([Atom('A'), Atom('B')]))`,
 right: `And([Atom('A'), Not(Atom('B'))])`', tests/solution_test.rs:107:5

---- solution_test::test_parser_multiple_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Not(Not(Or([Atom('A'), Atom('B')])))`,
 right: `Or([Atom('A'), Not(Not(Atom('B')))])`', tests/solution_test.rs:147:9
thread 'solution_test::test_parser_multiple_not' panicked at 'assertion failed: `(left == right)`
  left: `Not(Not(Or([Atom('A'), Atom('B')])))`,
 right: `Or([Atom('A'), Not(Not(Atom('B')))])`', tests/solution_test.rs:140:5


failures:
    solution_test::test_eval_partial
    solution_test::test_eval_unwrap_and_or
    solution_test::test_eval_unwrap_nested
    solution_test::test_paren_nested
    solution_test::test_paren_not
    solution_test::test_parser_expr_and_not
    solution_test::test_parser_multiple_not

test result: FAILED. 13 passed; 7 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

error: test failed, to rerun pass `--test solution_test`

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

Симеон качи първо решение на 21.12.2024 12:22 (преди 9 месеца)

Симеон качи решение на 22.12.2024 23:41 (преди 9 месеца)

use std::collections::VecDeque;
#[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(Debug)]
enum SimpleExprParserState {
ExpectingAtomOrNot,
ExpectingBinaryOp,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
state: SimpleExprParserState,
expressions: VecDeque<Expr>,
operations: VecDeque<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
Self {
state: SimpleExprParserState::ExpectingAtomOrNot,
expressions: VecDeque::new(),
operations: VecDeque::new(),
}
}
pub fn push_expr(&mut self, expr: Expr) -> Result<(), ParseError> {
match self.state {
SimpleExprParserState::ExpectingAtomOrNot => (),
SimpleExprParserState::ExpectingBinaryOp => return Err(ParseError::UnexpectedExpr),
}
self.expressions.push_back(expr);
self.state = SimpleExprParserState::ExpectingBinaryOp;
Ok(())
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.push_expr(Expr::Atom(c))
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' | '&' | '|' => (),
'(' | ')' => return Err(ParseError::UnexpectedParen),
_ => return Err(ParseError::UnexpectedExpr),
}
match self.state {
SimpleExprParserState::ExpectingAtomOrNot if op != '!' => return Err(ParseError::UnexpectedBinOp),
SimpleExprParserState::ExpectingBinaryOp if op == '!' => return Err(ParseError::UnexpectedUnaryOp),
_ => (),
}
self.operations.push_back(op);
self.state = SimpleExprParserState::ExpectingAtomOrNot;
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
// println!("{:?}", self.state);
match self.state {
SimpleExprParserState::ExpectingAtomOrNot => return Err(ParseError::UnexpectedEnd),
SimpleExprParserState::ExpectingBinaryOp => (),
}
let mut operations = self.operations.clone();
let mut expressions = self.expressions.clone();
// println!("operations {:?}", operations);
// println!("expressions {:?}", expressions);
while let Some(op) = operations.pop_front() {
let expression = expressions.pop_front().unwrap();
if op == '!' {
expressions.push_front(Expr::Not(Box::new(expression)));
} else if op == '&' || op == '|' {
let mut op_members = VecDeque::from([expression]);
// println!("op_members {:?}", op_members);
while let Some(&next_op) = operations.front() {
if next_op != op {
break;
}
op_members.push_back(expressions.pop_front().unwrap());
operations.pop_front();
}
op_members.push_back(expressions.pop_front().unwrap());
// println!("op_members {:?}", op_members);
expressions.push_front(
match op {
'&' => Expr::And(op_members.into()),
'|' => Expr::Or(op_members.into()),
_ => panic!("dont know this")
}
)
} else {
panic!("wtf");
}
}
// println!("{}", expressions.len());
if expressions.len() == 1 {
Ok(expressions.pop_front().unwrap())
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
previous_parsers: Vec<SimpleExprParser>,
}
impl ExprParser {
pub fn new() -> ExprParser {
Self {
previous_parsers: Vec::from([SimpleExprParser::new()]),
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
self.previous_parsers.last_mut().unwrap().push_atom(c)
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
self.previous_parsers.last_mut().unwrap().push_op(op)
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
match self.previous_parsers.last().unwrap().state {
SimpleExprParserState::ExpectingBinaryOp => return Err(ParseError::UnexpectedParen),
_ => (),
}
// println!("open before push {:?}", self.previous_parsers.len());
self.previous_parsers.push(SimpleExprParser::new());
// println!("open after push {:?}", self.previous_parsers.len());
Ok(())
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
// println!("close {:?} {:?}", self.previous_parsers.len(), self.previous_parsers.last().unwrap().state);
match self.previous_parsers.last().unwrap().state {
SimpleExprParserState::ExpectingAtomOrNot => return Err(ParseError::UnexpectedParen),
_ => (),
}
// println!("close before pop {:?}", self.previous_parsers.len());
let current_parser = self.previous_parsers.pop().ok_or(ParseError::UnexpectedParen)?;
// println!("close after pop {:?}", self.previous_parsers.len());
match current_parser.finish() {
- Ok(expr) => self.previous_parsers.last_mut().unwrap().push_expr(expr)?,
+ Ok(expr) => self.previous_parsers.last_mut()
+ .ok_or(ParseError::UnexpectedParen)?
+ .push_expr(expr)?,
Err(e) => return Err(e),
}
Ok(())
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
// println!("finish {:?}", self.previous_parsers.len());
if self.previous_parsers.len() == 1 {
self.previous_parsers.into_iter().next().unwrap().finish()
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
True,
False,
Expr(Expr),
}
pub fn eval(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
match expr {
Expr::Atom(c) => {
if truthy.contains(c) {
Value::True
} else if falsy.contains(c) {
Value::False
} else {
Value::Expr(expr.clone())
}
}
Expr::Not(sub_expr) => match eval(sub_expr, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
expr => expr,
},
Expr::And(operands) => {
let mut unevaluated_operands = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::False => return Value::False,
Value::True => continue,
Value::Expr(expr) => unevaluated_operands.push(expr),
}
}
match unevaluated_operands.len() {
0 => Value::True,
1 => Value::Expr(unevaluated_operands[0].clone()),
_ => Value::Expr(Expr::And(unevaluated_operands))
}
}
Expr::Or(operands) => {
let mut unevaluated_operands = Vec::new();
for operand in operands {
match eval(operand, truthy, falsy) {
Value::False => continue,
Value::True => return Value::True,
Value::Expr(expr) => unevaluated_operands.push(expr),
}
}
match unevaluated_operands.len() {
0 => Value::False,
1 => Value::Expr(unevaluated_operands[0].clone()),
_ => Value::Expr(Expr::Or(unevaluated_operands))
}
}
}
}