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

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

Решение на Логически изрази от Ясен Ефремов

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

Към профила на Ясен Ефремов

Резултати

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

Код

fn shunting_yard(tokens: &Vec<char>) -> Result<Vec<char>, ParseError> {
let mut stack = Vec::<char>::new();
let mut rpn = Vec::<char>::new();
for &c in tokens {
match c {
'!' => stack.push(c),
'&' | '|' => {
if !stack.is_empty() && *stack.last().unwrap() == '!' {
while !stack.is_empty() && *stack.last().unwrap() == '!' {
rpn.push(stack.pop().unwrap());
stack.push(c);
}
} else {
stack.push(c);
}
},
'(' => stack.push(c),
')' => {
while !stack.is_empty() && *stack.last().unwrap() != '(' {
rpn.push(stack.pop().unwrap());
}
if stack.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
stack.pop();
if let Some(next_last) = stack.last() {
if *next_last == '!' {
rpn.push(stack.pop().unwrap());
}
}
},
_ => rpn.push(c)
}
}
while let Some(c) = stack.pop() {
rpn.push(c);
}
Ok(rpn)
}
fn rpn_to_expr(tokens: Vec<char>) -> Result<Expr, ParseError> {
let mut stack = Vec::<Expr>::new();
for c in tokens {
match c {
'!' => {
let op = stack.pop().unwrap();
stack.push(Expr::Not(Box::new(op)));
},
'&' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::And(ands1), Expr::And(ands2)) => stack.push(Expr::And([ands1, ands2].concat())),
(Expr::And(ands), e) => stack.push(Expr::And([ands, vec![e]].concat())),
(e, Expr::And(ands)) => stack.push(Expr::And([vec![e], ands].concat())),
(e1, e2) => stack.push(Expr::And(vec![e1, e2])),
}
},
'|' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::Or(ors1), Expr::Or(ors2)) => stack.push(Expr::Or([ors1, ors2].concat())),
(Expr::Or(ors), e) => stack.push(Expr::Or([ors, vec![e]].concat())),
(e, Expr::Or(ors)) => stack.push(Expr::Or([vec![e], ors].concat())),
(e1, e2) => stack.push(Expr::Or(vec![e1, e2])),
}
},
_ => { stack.push(Expr::Atom(c)); }
}
}
if stack.len() != 1 {
Err(ParseError::UnexpectedEnd)
} else {
Ok(stack.last().unwrap().clone())
}
}
#[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,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
tokens: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
tokens: Vec::<char>::new()
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' => {
self.tokens.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.tokens.last() {
match last {
// '!' => { self.tokens.pop(); },
'!' | '&' | '|' => { self.tokens.push(op) },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.tokens.last() {
match last {
'!' => Err(ParseError::UnexpectedBinOp),
'&' | '|' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
let mut skip = false;
for i in 0..tokens.len() {
if skip {
skip = false;
continue;
}
if tokens[i] == '!' {
tokens.swap(i, i - 1);
skip = true;
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
tokens: Vec<char>,
unclosed_paren: u32
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
tokens: Vec::<char>::new(),
unclosed_paren: 0
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => {
self.tokens.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.tokens.last() {
match last {
// '!' => { self.tokens.pop(); },
'!' | '&' | '|' | '(' => { self.tokens.push(op); },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => {
self.tokens.push('(');
self.unclosed_paren += 1;
Ok(())
},
_ => Err(ParseError::UnexpectedParen)
}
} else {
self.tokens.push('(');
self.unclosed_paren += 1;
return Ok(());
}
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.unclosed_paren == 0 {
Err(ParseError::UnexpectedParen)
} else if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedParen),
_ => {
self.tokens.push(')');
self.unclosed_paren -= 1;
Ok(())
}
}
} else {
return Err(ParseError::UnexpectedParen);
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | Some('(') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
for i in 0..tokens.len() {
tokens[i] = match tokens[i] {
'!' => match tokens[i - 1] {
')' => tokens[i], // lucky?
_ => {
tokens.swap(i, i - 1);
tokens[i]
}
},
'(' => ')',
')' => '(',
_ => tokens[i]
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} 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::Atom(*c))
}
},
Expr::Not(e) => {
match eval(e, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(ee) => Value::Expr(Expr::Not(Box::new(ee)))
}
},
Expr::And(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => (),
Value::False => return Value::False,
Value::Expr(ee) => {
if let Expr::And(mut and_e) = ee {
ve_left.append(&mut and_e);
} else {
ve_left.push(ee);
}
},
}
}
if ve_left.is_empty() {
Value::True
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::And(ve_left))
}
},
Expr::Or(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => return Value::True,
Value::False => (),
Value::Expr(ee) => {
if let Expr::Or(mut and_e) = ee {
ve_left.append(&mut and_e);
} else {
ve_left.push(ee);
}
},
}
}
if ve_left.is_empty() {
Value::False
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::Or(ve_left))
}
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20241224-258381-1e98upm/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.83s
     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 ... ok
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_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_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 ... ok
test solution_test::test_parser_multiple_not ... FAILED
test solution_test::test_parser_not ... ok

failures:

---- solution_test::test_parser_multiple_not stdout ----
thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `Not(Or([Atom('A'), Not(Atom('B'))]))`,
 right: `Or([Atom('A'), Not(Not(Atom('B')))])`', tests/solution_test.rs:147:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'solution_test::test_parser_multiple_not' panicked at 'assertion failed: `(left == right)`
  left: `Not(Or([Atom('A'), Not(Atom('B'))]))`,
 right: `Or([Atom('A'), Not(Not(Atom('B')))])`', tests/solution_test.rs:140:5


failures:
    solution_test::test_parser_multiple_not

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

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

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

Ясен качи първо решение на 21.12.2024 19:23 (преди 9 месеца)

Ясен качи решение на 21.12.2024 20:53 (преди 9 месеца)

#[macro_export]
macro_rules! expr {
(atom ( $a:expr ) ) => (
Expr::Atom($a)
);
(not ( $i:ident $a:tt ) ) => (
Expr::Not(Box::new(expr!($i$a)))
);
(and ( $( $i:ident $a:tt ),+ ) ) => {{
let mut ands = Vec::<Expr>::new();
$( ands.push(expr!($i$a)); )+
Expr::And(ands)
}};
(or ( $( $i:ident $a:tt ),+ ) ) => {{
let mut ands = Vec::<Expr>::new();
$( ands.push(expr!($i$a)); )+
Expr::Or(ands)
}};
}
fn shunting_yard(tokens: &Vec<char>) -> Result<Vec<char>, ParseError> {
let mut stack = Vec::<char>::new();
let mut rpn = Vec::<char>::new();
for &c in tokens {
match c {
'!' => stack.push(c),
'&' | '|' => {
if !stack.is_empty() && *stack.last().unwrap() == '!' {
while !stack.is_empty() && *stack.last().unwrap() == '!' {
rpn.push(stack.pop().unwrap());
stack.push(c);
}
} else {
stack.push(c);
}
},
'(' => stack.push(c),
')' => {
while !stack.is_empty() && *stack.last().unwrap() != '(' {
rpn.push(stack.pop().unwrap());
}
if stack.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
stack.pop();
if let Some(next_last) = stack.last() {
if *next_last == '!' {
rpn.push(stack.pop().unwrap());
}
}
},
_ => rpn.push(c)
}
- println!("now: {:?}", stack);
}
while let Some(c) = stack.pop() {
rpn.push(c);
}
Ok(rpn)
}
fn rpn_to_expr(tokens: Vec<char>) -> Result<Expr, ParseError> {
let mut stack = Vec::<Expr>::new();
for c in tokens {
match c {
'!' => {
let op = stack.pop().unwrap();
stack.push(Expr::Not(Box::new(op)));
},
'&' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::And(ands1), Expr::And(ands2)) => stack.push(Expr::And([ands1, ands2].concat())),
(Expr::And(ands), e) => stack.push(Expr::And([ands, vec![e]].concat())),
(e, Expr::And(ands)) => stack.push(Expr::And([vec![e], ands].concat())),
(e1, e2) => stack.push(Expr::And(vec![e1, e2])),
}
},
'|' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::Or(ors1), Expr::Or(ors2)) => stack.push(Expr::Or([ors1, ors2].concat())),
(Expr::Or(ors), e) => stack.push(Expr::Or([ors, vec![e]].concat())),
(e, Expr::Or(ors)) => stack.push(Expr::Or([vec![e], ors].concat())),
(e1, e2) => stack.push(Expr::Or(vec![e1, e2])),
}
},
_ => {
stack.push(Expr::Atom(c));
}
}
}
if stack.len() != 1 {
Err(ParseError::UnexpectedEnd)
} else {
Ok(stack.last().unwrap().clone())
}
}
#[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,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
last: Option<char>,
tokens: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
last: None,
tokens: Vec::<char>::new()
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.last {
match last {
'!' | '&' | '|' => {
self.tokens.push(c);
self.last = Some(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
self.last = Some(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.last {
match last {
'!' | '&' | '|' => {
self.tokens.push(op);
self.last = Some(op);
},
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
self.last = Some(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.last {
match last {
'!' => Err(ParseError::UnexpectedBinOp),
'&' | '|' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
self.last = Some(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.last, Some('!') | Some('&') | Some('|') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
let mut skip = false;
for i in 0..tokens.len() {
if skip {
skip = false;
continue;
}
if tokens[i] == '!' {
tokens.swap(i, i - 1);
skip = true;
}
}
- println!("tokens: {:?}", tokens);
-
if let Ok(rpn) = shunting_yard(&tokens) {
- println!("rpn: {:?}", rpn);
rpn_to_expr(rpn)
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
last: Option<char>,
- tokens: Vec<char>
+ tokens: Vec<char>,
+ unclosed_paren: u32
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
last: None,
- tokens: Vec::<char>::new()
+ tokens: Vec::<char>::new(),
+ unclosed_paren: 0
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.last {
match last {
'!' | '&' | '|' | '(' => {
self.tokens.push(c);
self.last = Some(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
self.last = Some(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.last {
match last {
'!' | '&' | '|' | '(' => {
self.tokens.push(op);
self.last = Some(op);
},
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
self.last = Some(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.last {
match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
self.last = Some(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if let Some(last) = self.last {
return match last {
'!' | '&' | '|' | '(' => {
self.tokens.push('(');
self.last = Some('(');
+ self.unclosed_paren += 1;
Ok(())
},
_ => Err(ParseError::UnexpectedParen)
}
} else {
self.tokens.push('(');
self.last = Some('(');
+ self.unclosed_paren += 1;
return Ok(());
}
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
- if let Some(last) = self.last {
+ if self.unclosed_paren == 0 {
+ Err(ParseError::UnexpectedParen)
+ } else if let Some(last) = self.last {
return match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedParen),
_ => {
self.tokens.push(')');
self.last = Some(')');
+ self.unclosed_paren -= 1;
Ok(())
}
}
} else {
return Err(ParseError::UnexpectedParen);
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.last, Some('!') | Some('&') | Some('|') | Some('(') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
for i in 0..tokens.len() {
tokens[i] = match tokens[i] {
'!' => match tokens[i - 1] {
')' => {
tokens[i] // lucky?
},
_ => {
tokens.swap(i, i - 1);
tokens[i]
}
},
'(' => ')',
')' => '(',
_ => tokens[i]
}
}
- println!("tokens: {:?}", tokens);
-
if let Ok(rpn) = shunting_yard(&tokens) {
- println!("rpn: {:?}", rpn);
rpn_to_expr(rpn)
} 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!(atom(*c)))
}
},
Expr::Not(e) => {
match eval(e, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(ee) => Value::Expr(Expr::Not(Box::new(ee)))
}
},
Expr::And(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => (),
Value::False => return Value::False,
Value::Expr(ee) => ve_left.push(ee),
}
}
if ve_left.is_empty() {
Value::True
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::And(ve_left))
}
},
Expr::Or(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => return Value::True,
Value::False => (),
Value::Expr(ee) => ve_left.push(ee),
}
}
if ve_left.is_empty() {
Value::False
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::Or(ve_left))
}
}
}
}

Ясен качи решение на 21.12.2024 23:06 (преди 9 месеца)

#[macro_export]
macro_rules! expr {
(atom ( $a:expr ) ) => (
Expr::Atom($a)
);
(not ( $i:ident $a:tt ) ) => (
Expr::Not(Box::new(expr!($i$a)))
);
(and ( $( $i:ident $a:tt ),+ ) ) => {{
let mut ands = Vec::<Expr>::new();
$( ands.push(expr!($i$a)); )+
Expr::And(ands)
}};
(or ( $( $i:ident $a:tt ),+ ) ) => {{
let mut ands = Vec::<Expr>::new();
$( ands.push(expr!($i$a)); )+
Expr::Or(ands)
}};
}
fn shunting_yard(tokens: &Vec<char>) -> Result<Vec<char>, ParseError> {
let mut stack = Vec::<char>::new();
let mut rpn = Vec::<char>::new();
for &c in tokens {
match c {
'!' => stack.push(c),
'&' | '|' => {
if !stack.is_empty() && *stack.last().unwrap() == '!' {
while !stack.is_empty() && *stack.last().unwrap() == '!' {
rpn.push(stack.pop().unwrap());
stack.push(c);
}
} else {
stack.push(c);
}
},
'(' => stack.push(c),
')' => {
while !stack.is_empty() && *stack.last().unwrap() != '(' {
rpn.push(stack.pop().unwrap());
}
if stack.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
stack.pop();
if let Some(next_last) = stack.last() {
if *next_last == '!' {
rpn.push(stack.pop().unwrap());
}
}
},
_ => rpn.push(c)
}
}
while let Some(c) = stack.pop() {
rpn.push(c);
}
Ok(rpn)
}
fn rpn_to_expr(tokens: Vec<char>) -> Result<Expr, ParseError> {
let mut stack = Vec::<Expr>::new();
for c in tokens {
match c {
'!' => {
let op = stack.pop().unwrap();
stack.push(Expr::Not(Box::new(op)));
},
'&' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::And(ands1), Expr::And(ands2)) => stack.push(Expr::And([ands1, ands2].concat())),
(Expr::And(ands), e) => stack.push(Expr::And([ands, vec![e]].concat())),
(e, Expr::And(ands)) => stack.push(Expr::And([vec![e], ands].concat())),
(e1, e2) => stack.push(Expr::And(vec![e1, e2])),
}
},
'|' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::Or(ors1), Expr::Or(ors2)) => stack.push(Expr::Or([ors1, ors2].concat())),
(Expr::Or(ors), e) => stack.push(Expr::Or([ors, vec![e]].concat())),
(e, Expr::Or(ors)) => stack.push(Expr::Or([vec![e], ors].concat())),
(e1, e2) => stack.push(Expr::Or(vec![e1, e2])),
}
},
- _ => {
- stack.push(Expr::Atom(c));
- }
+ _ => { stack.push(Expr::Atom(c)); }
}
}
if stack.len() != 1 {
Err(ParseError::UnexpectedEnd)
} else {
Ok(stack.last().unwrap().clone())
}
}
#[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,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
- last: Option<char>,
tokens: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
- last: None,
tokens: Vec::<char>::new()
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' => {
self.tokens.push(c);
- self.last = Some(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
- self.last = Some(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
match last {
- '!' | '&' | '|' => {
- self.tokens.push(op);
- self.last = Some(op);
- },
+ '!' => { self.tokens.pop(); },
+ '&' | '|' => { self.tokens.push(op) },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
- self.last = Some(op);
}
Ok(())
},
'&' | '|' => {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
match last {
'!' => Err(ParseError::UnexpectedBinOp),
'&' | '|' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
- self.last = Some(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
- if matches!(self.last, Some('!') | Some('&') | Some('|') | None) {
+ if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
let mut skip = false;
for i in 0..tokens.len() {
if skip {
skip = false;
continue;
}
if tokens[i] == '!' {
tokens.swap(i, i - 1);
skip = true;
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
- last: Option<char>,
tokens: Vec<char>,
unclosed_paren: u32
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
- last: None,
tokens: Vec::<char>::new(),
unclosed_paren: 0
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => {
self.tokens.push(c);
- self.last = Some(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
- self.last = Some(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
match last {
- '!' | '&' | '|' | '(' => {
- self.tokens.push(op);
- self.last = Some(op);
- },
+ '!' | '&' | '|' | '(' => { self.tokens.push(op); },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
- self.last = Some(op);
}
Ok(())
},
'&' | '|' => {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
- self.last = Some(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
- if let Some(last) = self.last {
+ if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => {
self.tokens.push('(');
- self.last = Some('(');
self.unclosed_paren += 1;
Ok(())
},
_ => Err(ParseError::UnexpectedParen)
}
} else {
self.tokens.push('(');
- self.last = Some('(');
self.unclosed_paren += 1;
return Ok(());
}
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.unclosed_paren == 0 {
Err(ParseError::UnexpectedParen)
- } else if let Some(last) = self.last {
+ } else if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedParen),
_ => {
self.tokens.push(')');
- self.last = Some(')');
self.unclosed_paren -= 1;
Ok(())
}
}
} else {
return Err(ParseError::UnexpectedParen);
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
- if matches!(self.last, Some('!') | Some('&') | Some('|') | Some('(') | None) {
+ if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | Some('(') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
for i in 0..tokens.len() {
tokens[i] = match tokens[i] {
'!' => match tokens[i - 1] {
- ')' => {
- tokens[i] // lucky?
- },
+ ')' => tokens[i], // lucky?
_ => {
tokens.swap(i, i - 1);
tokens[i]
}
},
'(' => ')',
')' => '(',
_ => tokens[i]
}
}
-
+
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} 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!(atom(*c)))
}
},
Expr::Not(e) => {
match eval(e, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(ee) => Value::Expr(Expr::Not(Box::new(ee)))
}
},
Expr::And(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => (),
Value::False => return Value::False,
- Value::Expr(ee) => ve_left.push(ee),
+ Value::Expr(ee) => {
+ if let Expr::And(mut and_e) = ee {
+ ve_left.append(&mut and_e);
+ } else {
+ ve_left.push(ee);
+ }
+ },
}
}
if ve_left.is_empty() {
Value::True
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::And(ve_left))
}
},
Expr::Or(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => return Value::True,
Value::False => (),
- Value::Expr(ee) => ve_left.push(ee),
+ Value::Expr(ee) => {
+ if let Expr::Or(mut and_e) = ee {
+ ve_left.append(&mut and_e);
+ } else {
+ ve_left.push(ee);
+ }
+ },
}
}
if ve_left.is_empty() {
Value::False
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::Or(ve_left))
}
}
}
}

Ясен качи решение на 21.12.2024 23:40 (преди 9 месеца)

-#[macro_export]
-macro_rules! expr {
- (atom ( $a:expr ) ) => (
- Expr::Atom($a)
- );
-
- (not ( $i:ident $a:tt ) ) => (
- Expr::Not(Box::new(expr!($i$a)))
- );
-
- (and ( $( $i:ident $a:tt ),+ ) ) => {{
- let mut ands = Vec::<Expr>::new();
- $( ands.push(expr!($i$a)); )+
- Expr::And(ands)
- }};
-
- (or ( $( $i:ident $a:tt ),+ ) ) => {{
- let mut ands = Vec::<Expr>::new();
- $( ands.push(expr!($i$a)); )+
- Expr::Or(ands)
- }};
-}
-
fn shunting_yard(tokens: &Vec<char>) -> Result<Vec<char>, ParseError> {
let mut stack = Vec::<char>::new();
let mut rpn = Vec::<char>::new();
for &c in tokens {
match c {
'!' => stack.push(c),
'&' | '|' => {
if !stack.is_empty() && *stack.last().unwrap() == '!' {
while !stack.is_empty() && *stack.last().unwrap() == '!' {
rpn.push(stack.pop().unwrap());
stack.push(c);
}
} else {
stack.push(c);
}
},
'(' => stack.push(c),
')' => {
while !stack.is_empty() && *stack.last().unwrap() != '(' {
rpn.push(stack.pop().unwrap());
}
if stack.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
stack.pop();
if let Some(next_last) = stack.last() {
if *next_last == '!' {
rpn.push(stack.pop().unwrap());
}
}
},
_ => rpn.push(c)
}
}
while let Some(c) = stack.pop() {
rpn.push(c);
}
Ok(rpn)
}
fn rpn_to_expr(tokens: Vec<char>) -> Result<Expr, ParseError> {
let mut stack = Vec::<Expr>::new();
for c in tokens {
match c {
'!' => {
let op = stack.pop().unwrap();
stack.push(Expr::Not(Box::new(op)));
},
'&' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::And(ands1), Expr::And(ands2)) => stack.push(Expr::And([ands1, ands2].concat())),
(Expr::And(ands), e) => stack.push(Expr::And([ands, vec![e]].concat())),
(e, Expr::And(ands)) => stack.push(Expr::And([vec![e], ands].concat())),
(e1, e2) => stack.push(Expr::And(vec![e1, e2])),
}
},
'|' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::Or(ors1), Expr::Or(ors2)) => stack.push(Expr::Or([ors1, ors2].concat())),
(Expr::Or(ors), e) => stack.push(Expr::Or([ors, vec![e]].concat())),
(e, Expr::Or(ors)) => stack.push(Expr::Or([vec![e], ors].concat())),
(e1, e2) => stack.push(Expr::Or(vec![e1, e2])),
}
},
_ => { stack.push(Expr::Atom(c)); }
}
}
if stack.len() != 1 {
Err(ParseError::UnexpectedEnd)
} else {
Ok(stack.last().unwrap().clone())
}
}
#[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,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
tokens: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
tokens: Vec::<char>::new()
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' => {
self.tokens.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.tokens.last() {
match last {
'!' => { self.tokens.pop(); },
'&' | '|' => { self.tokens.push(op) },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.tokens.last() {
match last {
'!' => Err(ParseError::UnexpectedBinOp),
'&' | '|' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | None) {
return Err(ParseError::UnexpectedEnd)
}
-
- let mut tokens = self.tokens;
-
+ let mut tokens = self.tokens;
tokens.reverse();
let mut skip = false;
for i in 0..tokens.len() {
if skip {
skip = false;
continue;
}
if tokens[i] == '!' {
tokens.swap(i, i - 1);
skip = true;
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
tokens: Vec<char>,
unclosed_paren: u32
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
tokens: Vec::<char>::new(),
unclosed_paren: 0
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => {
self.tokens.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => { self.tokens.push(op); },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => {
self.tokens.push('(');
self.unclosed_paren += 1;
Ok(())
},
_ => Err(ParseError::UnexpectedParen)
}
} else {
self.tokens.push('(');
self.unclosed_paren += 1;
return Ok(());
}
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.unclosed_paren == 0 {
Err(ParseError::UnexpectedParen)
} else if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedParen),
_ => {
self.tokens.push(')');
self.unclosed_paren -= 1;
Ok(())
}
}
} else {
return Err(ParseError::UnexpectedParen);
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | Some('(') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
-
tokens.reverse();
for i in 0..tokens.len() {
tokens[i] = match tokens[i] {
'!' => match tokens[i - 1] {
')' => tokens[i], // lucky?
_ => {
tokens.swap(i, i - 1);
tokens[i]
}
},
'(' => ')',
')' => '(',
_ => tokens[i]
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} 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!(atom(*c)))
+ Value::Expr(Expr::Atom(*c))
}
},
Expr::Not(e) => {
match eval(e, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(ee) => Value::Expr(Expr::Not(Box::new(ee)))
}
},
Expr::And(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => (),
Value::False => return Value::False,
Value::Expr(ee) => {
if let Expr::And(mut and_e) = ee {
ve_left.append(&mut and_e);
} else {
ve_left.push(ee);
}
},
}
}
if ve_left.is_empty() {
Value::True
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::And(ve_left))
}
},
Expr::Or(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => return Value::True,
Value::False => (),
Value::Expr(ee) => {
if let Expr::Or(mut and_e) = ee {
ve_left.append(&mut and_e);
} else {
ve_left.push(ee);
}
},
}
}
if ve_left.is_empty() {
Value::False
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::Or(ve_left))
}
}
}
}

Ясен качи решение на 22.12.2024 17:08 (преди 9 месеца)

fn shunting_yard(tokens: &Vec<char>) -> Result<Vec<char>, ParseError> {
let mut stack = Vec::<char>::new();
let mut rpn = Vec::<char>::new();
for &c in tokens {
match c {
'!' => stack.push(c),
'&' | '|' => {
if !stack.is_empty() && *stack.last().unwrap() == '!' {
while !stack.is_empty() && *stack.last().unwrap() == '!' {
rpn.push(stack.pop().unwrap());
stack.push(c);
}
} else {
stack.push(c);
}
},
'(' => stack.push(c),
')' => {
while !stack.is_empty() && *stack.last().unwrap() != '(' {
rpn.push(stack.pop().unwrap());
}
if stack.is_empty() {
return Err(ParseError::UnexpectedEnd);
}
stack.pop();
if let Some(next_last) = stack.last() {
if *next_last == '!' {
rpn.push(stack.pop().unwrap());
}
}
},
_ => rpn.push(c)
}
}
while let Some(c) = stack.pop() {
rpn.push(c);
}
Ok(rpn)
}
fn rpn_to_expr(tokens: Vec<char>) -> Result<Expr, ParseError> {
let mut stack = Vec::<Expr>::new();
for c in tokens {
match c {
'!' => {
let op = stack.pop().unwrap();
stack.push(Expr::Not(Box::new(op)));
},
'&' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::And(ands1), Expr::And(ands2)) => stack.push(Expr::And([ands1, ands2].concat())),
(Expr::And(ands), e) => stack.push(Expr::And([ands, vec![e]].concat())),
(e, Expr::And(ands)) => stack.push(Expr::And([vec![e], ands].concat())),
(e1, e2) => stack.push(Expr::And(vec![e1, e2])),
}
},
'|' => {
let op1 = stack.pop().unwrap();
let op2 = stack.pop().unwrap();
match (op1, op2) {
(Expr::Or(ors1), Expr::Or(ors2)) => stack.push(Expr::Or([ors1, ors2].concat())),
(Expr::Or(ors), e) => stack.push(Expr::Or([ors, vec![e]].concat())),
(e, Expr::Or(ors)) => stack.push(Expr::Or([vec![e], ors].concat())),
(e1, e2) => stack.push(Expr::Or(vec![e1, e2])),
}
},
_ => { stack.push(Expr::Atom(c)); }
}
}
if stack.len() != 1 {
Err(ParseError::UnexpectedEnd)
} else {
Ok(stack.last().unwrap().clone())
}
}
#[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,
}
/// Парсър за прост израз, който не съдържа скоби
pub struct SimpleExprParser {
tokens: Vec<char>
}
impl SimpleExprParser {
pub fn new() -> SimpleExprParser {
SimpleExprParser {
tokens: Vec::<char>::new()
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' => {
self.tokens.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.tokens.last() {
match last {
- '!' => { self.tokens.pop(); },
- '&' | '|' => { self.tokens.push(op) },
+ // '!' => { self.tokens.pop(); },
+ '!' | '&' | '|' => { self.tokens.push(op) },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.tokens.last() {
match last {
'!' => Err(ParseError::UnexpectedBinOp),
'&' | '|' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
let mut skip = false;
for i in 0..tokens.len() {
if skip {
skip = false;
continue;
}
if tokens[i] == '!' {
tokens.swap(i, i - 1);
skip = true;
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} else {
Err(ParseError::UnexpectedEnd)
}
}
}
/// Парсър за пълния израз
pub struct ExprParser {
tokens: Vec<char>,
unclosed_paren: u32
}
impl ExprParser {
pub fn new() -> ExprParser {
ExprParser {
tokens: Vec::<char>::new(),
unclosed_paren: 0
}
}
/// Приема атом.
///
/// `c` ще бъде валиден символ за атом.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_atom(&mut self, c: char) -> Result<(), ParseError> {
match c {
'!' | '&' | '|' => panic!("{} is not an atom!", c),
_ => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => {
self.tokens.push(c);
Ok(())
},
_ => Err(ParseError::UnexpectedExpr)
}
} else {
self.tokens.push(c);
Ok(())
}
}
}
}
/// Приема символ за операция.
///
/// `op` ще бъде едно от '&', '|', '!'.
/// В противен случай можете да panic-нете (няма да се тества)
pub fn push_op(&mut self, op: char) -> Result<(), ParseError> {
match op {
'!' => {
if let Some(last) = self.tokens.last() {
match last {
+ // '!' => { self.tokens.pop(); },
'!' | '&' | '|' | '(' => { self.tokens.push(op); },
_ => return Err(ParseError::UnexpectedUnaryOp)
}
} else {
self.tokens.push(op);
}
Ok(())
},
'&' | '|' => {
if let Some(last) = self.tokens.last() {
match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedBinOp),
_ => {
self.tokens.push(op);
Ok(())
}
}
} else {
Err(ParseError::UnexpectedBinOp)
}
},
_ => panic!("{} is not an operation!", op)
}
}
/// Приема отваряща скоба.
pub fn open_paren(&mut self) -> Result<(), ParseError> {
if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => {
self.tokens.push('(');
self.unclosed_paren += 1;
Ok(())
},
_ => Err(ParseError::UnexpectedParen)
}
} else {
self.tokens.push('(');
self.unclosed_paren += 1;
return Ok(());
}
}
/// Приема затваряща скоба.
pub fn close_paren(&mut self) -> Result<(), ParseError> {
if self.unclosed_paren == 0 {
Err(ParseError::UnexpectedParen)
} else if let Some(last) = self.tokens.last() {
return match last {
'!' | '&' | '|' | '(' => Err(ParseError::UnexpectedParen),
_ => {
self.tokens.push(')');
self.unclosed_paren -= 1;
Ok(())
}
}
} else {
return Err(ParseError::UnexpectedParen);
}
}
/// Завършва парсването и връща построения израз.
pub fn finish(self) -> Result<Expr, ParseError> {
if matches!(self.tokens.last(), Some('!') | Some('&') | Some('|') | Some('(') | None) {
return Err(ParseError::UnexpectedEnd)
}
let mut tokens = self.tokens;
tokens.reverse();
for i in 0..tokens.len() {
tokens[i] = match tokens[i] {
'!' => match tokens[i - 1] {
')' => tokens[i], // lucky?
_ => {
tokens.swap(i, i - 1);
tokens[i]
}
},
'(' => ')',
')' => '(',
_ => tokens[i]
}
}
if let Ok(rpn) = shunting_yard(&tokens) {
rpn_to_expr(rpn)
} 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::Atom(*c))
}
},
Expr::Not(e) => {
match eval(e, truthy, falsy) {
Value::True => Value::False,
Value::False => Value::True,
Value::Expr(ee) => Value::Expr(Expr::Not(Box::new(ee)))
}
},
Expr::And(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => (),
Value::False => return Value::False,
Value::Expr(ee) => {
if let Expr::And(mut and_e) = ee {
ve_left.append(&mut and_e);
} else {
ve_left.push(ee);
}
},
}
}
if ve_left.is_empty() {
Value::True
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::And(ve_left))
}
},
Expr::Or(ve) => {
let ve_evaluated: Vec<Value> = ve.iter().map(|e| eval(e, truthy, falsy)).collect();
let mut ve_left = Vec::<Expr>::new();
for e in ve_evaluated {
match e {
Value::True => return Value::True,
Value::False => (),
Value::Expr(ee) => {
if let Expr::Or(mut and_e) = ee {
ve_left.append(&mut and_e);
} else {
ve_left.push(ee);
}
},
}
}
if ve_left.is_empty() {
Value::False
} else if ve_left.len() == 1 {
Value::Expr(ve_left[0].clone())
} else {
Value::Expr(Expr::Or(ve_left))
}
}
}
}