Решение на Логически изрази от Георги Йорданов
Към профила на Георги Йорданов
Резултати
- 16 точки от тестове
- 0 бонус точки
- 16 точки общо
- 16 успешни тест(а)
- 4 неуспешни тест(а)
Код
#[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,
}
fn is_valid_atom_symbol(c: char) -> bool {
c != ' ' && c != '&' && c != '|' && c != '!' && c != '(' && c != ')'
}
fn is_valid_op_symbol(c: char) -> bool {
c == '&' || c == '|' || c == '!'
}
#[derive (Debug)]
pub struct SimpleExprParser {
symbols: Vec<char>,
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser { symbols: vec![] }
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match self.symbols.last() {
Some(sym) => if is_valid_atom_symbol(*sym) {
Err(ParseError::UnexpectedExpr)
} else {
self.symbols.push(c);
Ok(())
},
None => {
self.symbols.push(c);
Ok(())
}
}
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match self.symbols.last() {
Some('!') | Some('&') | Some('|') | None => if op == '!' {
self.symbols.push(op);
Ok(())
} else {
Err(ParseError::UnexpectedBinOp)
}
Some(_) => if op == '!' {
Err(ParseError::UnexpectedUnaryOp)
} else {
self.symbols.push(op);
Ok(())
}
}
}
pub fn finish(self) -> Result<Expr, ParseError> {
let mut it = self.symbols.into_iter().peekable();
let mut result: Expr = Expr::Atom(' ');
while let Some(ch) = it.next() {
if result == Expr::Atom(' ') {
if is_valid_atom_symbol(ch) {
result = Expr::Atom(ch);
continue;
} else {
let mut nots = 1;
while let Some(&next_ch) = it.peek() {
if next_ch == '!' {
nots += 1;
it.next();
} else {
break;
}
}
match it.next() {
Some(next_ch) if is_valid_atom_symbol(next_ch) => {
let mut expr = Expr::Atom(next_ch);
for i in 0..nots {
expr = Expr::Not(Box::new(expr));
}
result = expr;
continue;
},
Some(_) => {
return Err(ParseError::UnexpectedBinOp);
},
None => {
return Err(ParseError::UnexpectedEnd);
}
}
}
}
if is_valid_atom_symbol(ch) {
match &mut result {
Expr::And(val) | Expr::Or(val) => val.push(Expr::Atom(ch)),
_ => return Err(ParseError::UnexpectedExpr)
}
} else if ch == '!' {
match &mut result {
Expr::And(val) | Expr::Or(val) => {
let mut nots = 1;
while let Some(&next_ch) = it.peek() {
if next_ch == '!' {
nots += 1;
it.next();
} else {
break;
}
}
match it.next() {
Some(next_ch) if is_valid_atom_symbol(next_ch) => {
let mut expr = Expr::Atom(next_ch);
for i in 0..nots {
expr = Expr::Not(Box::new(expr));
}
val.push(expr);
continue;
},
Some(_) => {
return Err(ParseError::UnexpectedBinOp);
},
None => {
return Err(ParseError::UnexpectedEnd);
}
}
}
_ => return Err(ParseError::UnexpectedExpr),
}
} else if ch == '|' {
result = Expr::Or(vec![result]);
} else if ch == '&' {
result = Expr::And(vec![result]);
}
}
match &result {
Expr::And(vec) | Expr::Or(vec) => if vec.len() == 1 {
Err(ParseError::UnexpectedEnd)
} else {
Ok(result)
},
_ => Ok(result)
}
}
}
pub struct ExprParser {
symbols: Vec<char>,
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser { symbols: vec![] }
}
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
if let Some(sym) = self.symbols.last() {
match sym {
'(' | '&' | '|' | '!' => {
self.symbols.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr),
}
} else {
self.symbols.push(c);
Ok(())
}
}
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
if let Some(sym) = self.symbols.last() {
match sym {
'!' => if op == '!' {
self.symbols.push(op);
Ok(())
} else {
Err(ParseError::UnexpectedBinOp)
},
'(' | '&' | '|' => if op == '!' {
self.symbols.push(op);
Ok(())
} else {
Err(ParseError::UnexpectedBinOp)
},
')' | _ => if op == '!' {
Err(ParseError::UnexpectedUnaryOp)
} else {
self.symbols.push(op);
Ok(())
}
}
} else {
if op == '!' {
self.symbols.push(op);
Ok(())
} else {
Err(ParseError::UnexpectedBinOp)
}
}
}
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if let Some(sym) = self.symbols.last() {
match sym {
'(' | '&' | '|' | '!' => {
self.symbols.push('(');
Ok(())
},
_ => Err(ParseError::UnexpectedParen),
}
} else {
self.symbols.push('(');
Ok(())
}
}
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if let Some(sym) = self.symbols.last() {
match sym {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedParen),
')' | _ => {
self.symbols.push(')');
Ok(())
}
}
} else {
Err(ParseError::UnexpectedParen)
}
}
pub fn finish(self) -> Result<Expr, ParseError> {
self.balanced()?;
self.trailing_oper()?;
let mut expr_stack: Vec<Expr> = vec![];
let postfix = self.to_postfix();
for ch in postfix {
if is_valid_atom_symbol(ch) {
expr_stack.push(Expr::Atom(ch));
}
else if ch == '!' {
if let Some(expr) = expr_stack.pop() {
expr_stack.push(Expr::Not(Box::new(expr)))
} else {
return Err(ParseError::UnexpectedUnaryOp);
}
}
else if ch == '&' {
if expr_stack.len() < 2 {
println!("{:?}", expr_stack);
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
match left {
Expr::And(mut vec) => {
vec.push(right);
expr_stack.push(Expr::And(vec));
},
_ => expr_stack.push(Expr::And(vec![left, right])),
}
}
else if ch == '|' {
if expr_stack.len() < 2 {
return Err(ParseError::UnexpectedBinOp);
}
let right = expr_stack.pop().unwrap();
let left = expr_stack.pop().unwrap();
match left {
Expr::Or(mut vec) => {
vec.push(right);
expr_stack.push(Expr::Or(vec));
},
_ => expr_stack.push(Expr::Or(vec![left, right])),
}
}
}
if expr_stack.len() != 1 {
Err(ParseError::UnexpectedExpr)
} else {
Ok(expr_stack.last().unwrap().clone())
}
}
// check for trailing operator in expressions such as: A &
fn trailing_oper(&self) -> Result<(), ParseError> {
match self.symbols.last() {
Some('!') | Some('&') | Some('|') | None => Err(ParseError::UnexpectedEnd),
Some(_) => Ok(())
}
}
// check for balancing parens
fn balanced(&self) -> Result<(), ParseError> {
let mut paren_stack: Vec<char> = vec![];
for c in &self.symbols {
if *c == '(' {
paren_stack.push(*c);
} else if *c == ')' {
if paren_stack.is_empty() {
return Err(ParseError::UnexpectedParen);
} else {
paren_stack.pop();
}
} else {
continue;
}
}
if paren_stack.is_empty() {
Ok(())
} else {
Err(ParseError::UnexpectedParen)
}
}
// shunting yard algorithm
fn to_postfix(&self) -> Vec<char> {
let mut postfix: Vec<char> = vec![];
let mut operator_stack: Vec<char> = vec![];
for c in &self.symbols {
if is_valid_atom_symbol(*c) {
postfix.push(*c);
}
else if is_valid_op_symbol(*c) {
while let Some(val) = operator_stack.last() {
if Self::get_priority(*val) >= Self::get_priority(*c) {
postfix.push(operator_stack.pop().unwrap());
} else {
break;
}
}
operator_stack.push(*c);
} else if *c == '(' {
operator_stack.push('(');
} else if *c == ')' {
while let Some(val) = operator_stack.last() {
if *val != '(' {
postfix.push(operator_stack.pop().unwrap())
} else {
operator_stack.pop();
break;
}
}
}
}
while let Some(c) = operator_stack.last() {
postfix.push(operator_stack.pop().unwrap());
}
postfix
}
fn get_priority(symbol: char) -> i32 {
if symbol == '!' {
2
} else if symbol == '&' || symbol == '|' {
1
} else {
0
}
}
}
#[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(_) => eval_atom(expr, truthy, falsy),
Expr::Not(_) => eval_not(expr, truthy, falsy),
Expr::And(_) => eval_and(expr, truthy, falsy),
Expr::Or(_) => eval_or(expr, truthy, falsy),
}
}
fn eval_atom(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
if let Expr::Atom(ch) = expr {
if truthy.contains(ch) {
Value::True
} else if falsy.contains(ch) {
Value::False
} else {
Value::Expr(expr.clone())
}
} else {
// won't happen
Value::Expr(expr.clone())
}
}
fn eval_not(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
if let Expr::Not(nested_expr) = expr {
match eval(&nested_expr, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(evaluated) => Value::Expr(Expr::Not(Box::new(evaluated))),
}
} else {
// won't happen...
Value::Expr(expr.clone())
}
}
fn eval_and(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
if let Expr::And(vec) = expr {
let evaluated = vec
.iter()
.map(|nested_expr| eval(nested_expr, truthy, falsy))
.collect::<Vec<_>>();
if evaluated.iter().all(|ev_expr| *ev_expr == Value::True) {
Value::True
} else if evaluated.iter().any(|ev_expr| *ev_expr == Value::False) {
Value::False
} else if evaluated.iter().all(|ev_expr| if let Value::Expr(_) | Value::True = ev_expr {true } else {false}) {
let filtered = evaluated.into_iter()
.filter_map(|ev_expr| if let Value::Expr(expr) = ev_expr {Some(expr.clone())} else {None} )
.collect::<Vec<Expr>>();
if filtered.len() < 2 {
Value::Expr(filtered.last().unwrap().clone())
} else {
Value::Expr(Expr::And(filtered
.into_iter()
.collect::<Vec<Expr>>()))
}
} else {
// Unreachable
Value::False
}
} else {
// won't happen...
Value::Expr(expr.clone())
}
}
fn eval_or(expr: &Expr, truthy: &[char], falsy: &[char]) -> Value {
if let Expr::Or(vec) = expr {
let evaluated = vec
.iter()
.map(|nested_expr| eval(nested_expr, truthy, falsy))
.collect::<Vec<_>>();
if evaluated.iter().all(|ev_expr| *ev_expr == Value::False) {
Value::False
} else if evaluated.iter().any(|ev_expr| *ev_expr == Value::True) {
Value::True
} else if evaluated.iter().all(|ev_expr| if let Value::Expr(_) | Value::False = ev_expr {true } else {false}) {
let filtered = evaluated.into_iter()
.filter_map(|ev_expr| if let Value::Expr(expr) = ev_expr {Some(expr.clone())} else {None} )
.collect::<Vec<Expr>>();
if filtered.len() < 2 {
Value::Expr(filtered.last().unwrap().clone())
} else {
Value::Expr(Expr::And(filtered
.into_iter()
.collect::<Vec<Expr>>()))
}
} else {
// Unreachable
Value::False
}
} else {
// won't happen...
Value::Expr(expr.clone())
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20241224-258381-jrin8l/solution)
warning: unused variable: `i`
--> src/lib.rs:98:33
|
98 | ... for i in 0..nots {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `i`
--> src/lib.rs:135:37
|
135 | ... for i in 0..nots {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
warning: unused variable: `c`
--> src/lib.rs:401:24
|
401 | while let Some(c) = operator_stack.last() {
| ^ help: if this is intentional, prefix it with an underscore: `_c`
warning: `solution` (lib) generated 3 warnings
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.89s
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 ... FAILED
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_not ... ok
test solution_test::test_paren_nested ... 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_error_unexpected_end ... FAILED
test solution_test::test_parser_errors_basic ... ok
test solution_test::test_parser_expr_and_not ... ok
test solution_test::test_parser_multiple_not ... ok
test solution_test::test_parser_multiple_atoms_same_op ... 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(And([Atom('A'), Atom('C')]))`,
right: `Expr(Or([Atom('A'), Atom('C')]))`', tests/solution_test.rs:429: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(And([Atom('A'), Atom('C')]))`,
right: `Expr(Or([Atom('A'), Atom('C')]))`', tests/solution_test.rs:409:5
---- solution_test::test_eval_unwrap_nested stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
left: `Expr(And([Atom('X'), Atom('B'), Not(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(And([Atom('X'), Atom('B'), Not(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:307: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_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
failures:
solution_test::test_eval_partial
solution_test::test_eval_unwrap_nested
solution_test::test_parser_error_unexpected_end
solution_test::test_parser_multiple_atoms_same_op
test result: FAILED. 16 passed; 4 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
error: test failed, to rerun pass `--test solution_test`