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

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

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

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

Към профила на Памела Славчева

Резултати

  • 18 точки от тестове
  • 2 бонус точки
  • 20 точки общо
  • 18 успешни тест(а)
  • 2 неуспешни тест(а)

Код

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Expr {
Atom(char),
Not(Box<Expr>),
And(Vec<Expr>),
Or(Vec<Expr>),
}
#[derive(PartialEq, Clone, Debug)]
pub enum Type{
None,
Atom,
Not,
And,
Or,
Open,
Close
}
#[derive(Debug, PartialEq, Eq)]
pub enum ParseError {
UnexpectedExpr,
UnexpectedUnaryOp,
UnexpectedBinOp,
UnexpectedParen,
UnexpectedEnd,
}
#[derive(Clone, Debug)]
pub struct SimpleExprParser {
state: Option<Expr>,
last_token: Type
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { state: None, last_token: Type::None }
}
fn create_not_atom(c: char, not_box: &Box<Expr>) -> Box<Expr> {
match **not_box {
Expr::Not(ref element) =>
{
return Box::new(Expr::Not(Self::create_not_atom(c, element)));
}
Expr::Atom(_) => {
return Box::new(Expr::Atom(c));
}
_ => {
panic!("Unexpected expression")
}
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match self.last_token {
Type::None => {
self.state = Some(Expr::Atom(c));
self.last_token = Type::Atom;
},
Type::Atom => {
return Err(ParseError::UnexpectedExpr);
},
Type::Not =>
{
match &mut self.state {
Some(value) => {
match value {
Expr::Not(not_box) =>
{
self.state = Some(Expr::Not(Self::create_not_atom(c, &not_box)));
},
Expr::And(vec) | Expr::Or(vec) => {
let not_state = vec.pop().unwrap();
match not_state {
Expr::Not(not_box) => {
vec.push(Expr::Not(Self::create_not_atom(c, &not_box)));
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
self.last_token = Type::Atom;
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
},
Type::And | Type::Or => {
match &mut self.state {
Some(value) => {
match value {
Expr::And(vec) =>
{
vec.push(Expr::Atom(c));
self.last_token = Type::Atom;
},
Expr::Or(vec) =>
{
vec.push(Expr::Atom(c));
self.last_token = Type::Atom;
},
_ => {
return Err(ParseError::UnexpectedExpr);
},
}
},
_ =>
{
return Err(ParseError::UnexpectedExpr);
}
}
},
_ =>
{
return Err(ParseError::UnexpectedExpr);
}
}
Ok(())
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match self.last_token {
Type::None =>
{
match op {
'!' =>
{
self.state = Some(Expr::Not(Box::new(Expr::Atom('!'))));
self.last_token = Type::Not;
},
_ =>
{
return Err(ParseError::UnexpectedBinOp);
}
}
},
Type::Atom =>
{
match op {
'!' =>
{
return Err(ParseError::UnexpectedUnaryOp);
},
'&' =>
{
match &mut self.state{
Some(value) => {
match value {
Expr::And(_) => {
}
Expr::Atom(_) => {
self.state = Some(Expr::And(vec![self.state.as_ref().unwrap().clone()]));
}
Expr::Or(_) => {
self.state = Some(Expr::And(vec![self.state.as_ref().unwrap().clone()]));
}
Expr::Not(_) => {
self.state = Some(Expr::And(vec![self.state.as_ref().unwrap().clone()]));
}
}
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
self.last_token = Type::And;
},
'|' =>
{
match &mut self.state{
Some(value) => {
match value {
Expr::Or(_) => {
}
Expr::Atom(_) => {
self.state = Some(Expr::Or(vec![self.state.as_ref().unwrap().clone()]));
}
Expr::And(_) => {
self.state = Some(Expr::Or(vec![self.state.as_ref().unwrap().clone()]));
}
Expr::Not(_) => {
self.state = Some(Expr::Or(vec![self.state.as_ref().unwrap().clone()]));
}
}
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
self.last_token = Type::Or;
},
_ =>
{
return Err(ParseError::UnexpectedExpr);
}
}
},
Type::Not =>
{
match op {
'!' =>
{
match &mut self.state {
Some(value) => {
match value {
Expr::Not(_) =>
{
self.state = Some(Expr::Not(Box::new(self.state.as_ref().unwrap().clone())));
},
Expr::And(vec) | Expr::Or(vec) =>
{
let not_state: Expr = vec.pop().unwrap();
match not_state {
Expr::Not(not_box) => {
vec.push(Expr::Not(Box::new(Expr::Not(not_box))));
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
},
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
self.last_token = Type::Not;
}
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
},
Type::And | Type::Or => {
match op {
'!' => {
match &mut self.state.as_mut().unwrap() {
Expr::And(vec) =>{
vec.push(Expr::Not(Box::new(Expr::Atom('!'))));
},
Expr::Or(vec) =>{
vec.push(Expr::Not(Box::new(Expr::Atom('!'))));
},
_ => {
return Err(ParseError::UnexpectedUnaryOp);
}
}
self.last_token = Type::Not;
}
_ => {
return Err(ParseError::UnexpectedBinOp);
}
}
}
,
_ =>
{
return Err(ParseError::UnexpectedExpr);
}
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
match self.last_token {
Type::None | Type::And | Type::Or | Type::Open | Type::Close =>
{
return Err(ParseError::UnexpectedEnd);
}
_=>
{
return Ok(self.state.unwrap());
}
}
}
}
pub struct ExprParser {
stack:Vec<SimpleExprParser>,
last_token:Type,
last_expression: Expr,
current: SimpleExprParser,
}
impl ExprParser {
fn push_not_expr(expr: & Expr, expr_to_push: &Expr) -> Expr {
match expr {
Expr::Not(ref element) => {
return Self::push_not_expr(&*element, expr_to_push);
},
Expr::Atom(_) => {
return Expr::Not(Box::new(expr_to_push.clone()));
},
_ => {
panic!("Unexpected expression")
}
}
}
pub fn new() -> ExprParser {
ExprParser {
current: SimpleExprParser::new(),
stack: vec![],
last_token: Type::None,
last_expression: Expr::Atom('a')
}
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match self.last_token{
Type::Close =>
{
return Err(ParseError::UnexpectedExpr);
},
_ =>
{
let res = self.current.push_atom(c);
if res.is_ok() {
self.last_token = Type::Atom;
}
return res;
},
}
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match (self.last_token.clone(), op) {
(Type::Close, '!') =>
{
return Err(ParseError::UnexpectedUnaryOp);
},
_ =>
{
if self.current.state.is_none() {
match op {
'&' => {
self.current.state = Some(Expr::And(vec![self.last_expression.clone()]));
self.current.last_token = Type::And;
self.last_token = Type::And;
},
'|' => {
self.current.state = Some(Expr::Or(vec![self.last_expression.clone()]));
self.current.last_token = Type::Or;
self.last_token = Type::Or;
},
'!' => {
self.current.state = Some(Expr::Not(Box::new(Expr::Atom('!'))));
self.current.last_token = Type::Not;
self.last_token = Type::Not;
}
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
Ok(())
}
else {
let res = self.current.push_op(op);
if res.is_ok() {
match op {
'!' => self.last_token = Type::Not,
'&' => self.last_token = Type::And,
'|' => self.last_token = Type::Or,
_ => {
return Err(ParseError::UnexpectedExpr);
}
}
}
return res;
}
},
}
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
match self.last_token {
Type::Not | Type::And | Type::Or | Type::Open | Type::None => {
self.stack.push(self.current.clone());
self.current = SimpleExprParser::new();
self.last_token = Type::Open;
}
_ => {
return Err(ParseError::UnexpectedParen);
}
}
Ok(())
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.stack.is_empty() {
return Err(ParseError::UnexpectedParen);
}
match self.last_token {
Type::Atom | Type::Close => {
let temp = self.current.clone().finish();
match temp {
Ok(expr) =>
{
self.last_expression = expr;
self.last_token = Type::Close;
self.current = self.stack.pop().unwrap();
match self.current.last_token {
Type::Not => {
match &mut self.current.state.as_mut().unwrap() {
Expr::Not(_) =>
{
self.current.state = Some(Self::push_not_expr(& self.current.state.clone().unwrap(), &self.last_expression));
self.current.last_token = Type::Atom;
},
Expr::And(vec) | Expr::Or(vec) =>
{
let state = vec.pop();
let exprr = Self::push_not_expr(& state.unwrap(), &self.last_expression);
vec.push(exprr);
self.current.last_token = Type::Atom;
}
_ => {
return Err(ParseError::UnexpectedParen);
}
}
},
Type::And | Type::Or => {
match &mut self.current.state.as_mut().unwrap() {
Expr::And(vec) | Expr::Or(vec) =>
{
vec.push(self.last_expression.clone());
self.current.last_token = Type::Atom;
}
_ => {
return Err(ParseError::UnexpectedParen);
}
}
}
_ => {
}
}
},
_ => return Err(ParseError::UnexpectedParen)
}
},
_ => return Err(ParseError::UnexpectedParen)
}
Ok(())
}
pub fn finish(self) -> Result<Expr, ParseError> {
if !self.stack.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
if self.current.last_token == Type::None
{
if self.last_token == Type::None
{
return Err(ParseError::UnexpectedEnd);
}
return Ok(self.last_expression);
}
self.current.finish()
}
}
#[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)
{
return Value::True;
}
else if falsy.contains(&c)
{
return Value::False;
}
return Value::Expr(Expr::Atom(*c));
},
Expr::Not(expr) =>
{
let value:Value = eval(&*expr, truthy, falsy);
if value == Value::True
{
return Value::False;
}
else if value == Value::False
{
return Value::True;
}
return Value::Expr(Expr::Not(expr.clone()).clone());
},
Expr::And(vec) =>
{
let mut unevaluated = vec![];
for expr in vec{
let value:Value = eval(expr, truthy, falsy);
match value{
Value::False =>
{
return Value::False;
},
Value::True =>
{
},
Value::Expr(inner_expr) =>
{
unevaluated.push(inner_expr);
}
}
}
if unevaluated.len() == 0
{
return Value::True;
}
if unevaluated.len() == 1
{
return Value::Expr(unevaluated[0].clone());
}
return Value::Expr(Expr::And(unevaluated));
},
Expr::Or(vec) =>
{
let mut unevaluated = vec![];
for expr in vec{
let value:Value = eval(expr, truthy, falsy);
match value{
Value::True =>
{
return Value::True;
},
Value::False =>
{
},
Value::Expr(inner_expr) =>
{
unevaluated.push(inner_expr);
}
}
}
if unevaluated.len() == 0
{
return Value::False;
}
if unevaluated.len() == 1
{
return Value::Expr(unevaluated[0].clone());
}
return Value::Expr(Expr::Or(unevaluated));
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_empty_input() {
let parser = SimpleExprParser::new();
assert_eq!(parser.finish(), Err(ParseError::UnexpectedEnd));
}
#[test]
fn test_multiple_not_and_diff_ops() {
let mut parser: SimpleExprParser = SimpleExprParser::new();
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('|'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('|'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_atom('B'), Ok(()));
assert_eq!(parser.push_atom('A'), Err(ParseError::UnexpectedExpr));
assert_eq!(parser.push_op('!'), Err(ParseError::UnexpectedUnaryOp));
assert_eq!(parser.push_op('&'), Ok(()));
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('|'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('|'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_atom('A'), Ok(()));
assert_eq!(parser.push_op('!'), Err(ParseError::UnexpectedUnaryOp));
assert_eq!(parser.push_op('&'), Ok(()));
assert_eq!(parser.push_atom('C'), Ok(()));
let expr = parser.finish();
assert!(expr.is_ok());
let expected_expr = Expr::And(vec![
Expr::Not(Box::new(Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('B'))))))),
Expr::Not(Box::new(Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('A'))))))),
Expr::Atom('C'),
]);
assert_eq!(expr, Ok(expected_expr));
}
#[test]
fn test_multiple_not_with_eval() {
let mut parser: SimpleExprParser = SimpleExprParser::new();
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_atom('B'), Ok(()));
assert_eq!(parser.push_op('|'), Ok(()));
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('|'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('&'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_op('|'), Err(ParseError::UnexpectedBinOp));
assert_eq!(parser.push_atom('A'), Ok(()));
assert_eq!(parser.push_op('!'), Err(ParseError::UnexpectedUnaryOp));
assert_eq!(parser.push_op('|'), Ok(()));
assert_eq!(parser.push_atom('C'), Ok(()));
let expr = parser.finish();
assert!(expr.is_ok());
let expected_expr = Expr::Or(vec![
Expr::Not(Box::new(Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('B'))))))),
Expr::Not(Box::new(Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('A'))))))),
Expr::Atom('C'),
]);
assert_eq!(expr, Ok(expected_expr));
}
#[test]
fn test_combined_and_or_expression_complexerer() {
let mut parser: SimpleExprParser = SimpleExprParser::new();
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_atom('B'), Ok(()));
assert_eq!(parser.push_op('&'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_op('!'), Ok(()));
assert_eq!(parser.push_atom('A'), Ok(()));
assert_eq!(parser.push_op('&'), Ok(()));
assert_eq!(parser.push_atom('C'), Ok(()));
assert_eq!(parser.push_op('|'), Ok(()));
assert_eq!(parser.push_atom('C'), Ok(()));
let expr = parser.finish();
assert!(expr.is_ok());
let expected_expr = Expr::Or(vec![Expr::And(vec![
Expr::Not(Box::new(Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('B'))))))),
Expr::Not(Box::new(Expr::Not(Box::new(Expr::Not(Box::new(Expr::Atom('A'))))))),
Expr::Atom('C'),
]),
Expr::Atom('C'),
]);
}
#[test]
fn test_nested_expressions() {
// (A & B) | (C & (D | !E))
let mut full_parser = ExprParser::new();
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('A');
let _ = full_parser.push_op('&');
let _ = full_parser.push_atom('B');
let _ = full_parser.close_paren();
let _ = full_parser.push_op('|');
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('C');
let _ = full_parser.push_op('&');
let _ = full_parser.open_paren();
let _ = full_parser.push_atom('D');
let _ = full_parser.push_op('|');
let _ = full_parser.push_op('!');
let _ = full_parser.push_atom('E');
let _ = full_parser.close_paren();
let _ = full_parser.close_paren();
let expr = full_parser.finish().unwrap();
assert_eq!(eval(&expr, &['A', 'B'], &[]), Value::True);
assert_eq!(eval(&expr, &['C', 'D'], &['E']), Value::True);
assert_eq!(eval(&expr, &[], &['A', 'B', 'C', 'D', 'E']), Value::False);
assert_eq!(
eval(&expr, &[], &[]),
Value::Expr(Expr::Or(vec![
Expr::And(vec![Expr::Atom('A'), Expr::Atom('B')]),
Expr::And(vec![
Expr::Atom('C'),
Expr::Or(vec![Expr::Atom('D'), Expr::Not(Box::new(Expr::Atom('E')))])
])
]))
);
}
}

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

Compiling solution v0.1.0 (/tmp/d20241224-258381-11wg878/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.74s
     Running tests/solution_test.rs (target/debug/deps/solution_test-1428e1090729d165)

running 20 tests
test solution_test::test_error_paren_mismatched ... ok
test solution_test::test_eval_full ... ok
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_around_expr ... ok
test solution_test::test_paren_expr_priority ... ok
test solution_test::test_paren_nested ... ok
test solution_test::test_paren_not ... ok
test solution_test::test_paren_surrounded ... ok
test solution_test::test_parser_alternating_ops ... ok
test solution_test::test_parser_and_or ... ok
test solution_test::test_parser_atom ... ok
test solution_test::test_parser_errors_basic ... ok
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 ... ok
test solution_test::test_parser_not ... ok

failures:

---- 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
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
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_parser_error_unexpected_end stdout ----
thread '<unnamed>' panicked at 'assertion failed: matches!(parser.finish(), Err(_))', tests/solution_test.rs:319:9
thread 'solution_test::test_parser_error_unexpected_end' panicked at 'called `Option::unwrap()` on a `None` value', tests/solution_test.rs:305:5


failures:
    solution_test::test_eval_unwrap_nested
    solution_test::test_parser_error_unexpected_end

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

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

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

Памела качи първо решение на 22.12.2024 18:45 (преди 9 месеца)