Truth table: Difference between revisions
Content added Content deleted
(Add clojure solution to truth tables) |
(Add source for Rust) |
||
| Line 941: | Line 941: | ||
{{incorrect|Déjà Vu|User input is not arbitrary but fixed to the three examples shown}} |
{{incorrect|Déjà Vu|User input is not arbitrary but fixed to the three examples shown}} |
||
<lang dejavu>print-line lst end: |
<lang dejavu>print-line lst end: |
||
for v in reversed copy lst: |
|||
print\( v chr 9 ) |
|||
print end |
|||
(print-truth-table) t n func: |
(print-truth-table) t n func: |
||
if n: |
|||
(print-truth-table) push-through copy t 0 -- n @func |
|||
(print-truth-table) push-through copy t 1 -- n @func |
|||
else: |
|||
print-line t func for in copy t |
|||
print-truth-table vars name func: |
print-truth-table vars name func: |
||
print-line vars name |
|||
(print-truth-table) [] len vars @func |
|||
print "" # extra new line |
|||
stu s t u: |
stu s t u: |
||
or s /= t u |
|||
abcd a b c d: |
abcd a b c d: |
||
/= a /= b /= c d |
|||
print-truth-table [ "A" "B" ] "A ^ B" @/= |
print-truth-table [ "A" "B" ] "A ^ B" @/= |
||
| Line 967: | Line 967: | ||
print-truth-table [ "A" "B" "C" "D" ] "A ^ (B ^ (C ^ D))" @abcd</lang> |
print-truth-table [ "A" "B" "C" "D" ] "A ^ (B ^ (C ^ D))" @abcd</lang> |
||
{{out}} |
{{out}} |
||
<pre>A |
<pre>A B A ^ B |
||
0 |
0 0 0 |
||
0 |
0 1 1 |
||
1 |
1 0 1 |
||
1 |
1 1 0 |
||
S |
S T U S | (T ^ U) |
||
0 |
0 0 0 0 |
||
0 |
0 0 1 1 |
||
0 |
0 1 0 1 |
||
0 |
0 1 1 0 |
||
1 |
1 0 0 1 |
||
1 |
1 0 1 1 |
||
1 |
1 1 0 1 |
||
1 |
1 1 1 1 |
||
A |
A B C D A ^ (B ^ (C ^ D)) |
||
0 |
0 0 0 0 0 |
||
0 |
0 0 0 1 1 |
||
0 |
0 0 1 0 1 |
||
0 |
0 0 1 1 0 |
||
0 |
0 1 0 0 1 |
||
0 |
0 1 0 1 0 |
||
0 |
0 1 1 0 0 |
||
0 |
0 1 1 1 1 |
||
1 |
1 0 0 0 1 |
||
1 |
1 0 0 1 0 |
||
1 |
1 0 1 0 0 |
||
1 |
1 0 1 1 1 |
||
1 |
1 1 0 0 0 |
||
1 |
1 1 0 1 1 |
||
1 |
1 1 1 0 1 |
||
1 |
1 1 1 1 0 |
||
</pre> |
</pre> |
||
| Line 1,582: | Line 1,582: | ||
function isboolop(chr){return "&|!^".indexOf(chr)!=-1;} |
function isboolop(chr){return "&|!^".indexOf(chr)!=-1;} |
||
function varsindexof(chr){ |
function varsindexof(chr){ |
||
var i; |
|||
for(i=0;i<vars.length;i++){if(vars[i][0]==chr)return i;} |
|||
return -1; |
|||
} |
} |
||
function printtruthtable(){ |
function printtruthtable(){ |
||
var i,str; |
|||
elem=document.createElement("pre"); |
|||
expr=prompt("Boolean expression:\nAccepts single-character variables (except for \"T\" and \"F\", which specify explicit true or false values), postfix, with \"&|!^\" for and, or, not, xor, respectively; optionally seperated by whitespace.").replace(/\s/g,""); |
|||
vars=[]; |
|||
for(i=0;i<expr.length;i++)if(!isboolop(expr[i])&&expr[i]!="T"&&expr[i]!="F"&&varsindexof(expr[i])==-1)vars.push([expr[i],-1]); |
|||
if(vars.length==0)return; |
|||
str=""; |
|||
for(i=0;i<vars.length;i++)str+=vars[i][0]+" "; |
|||
elem.innerHTML="<b>"+str+expr+"</b>\n"; |
|||
vars[0][1]=false; |
|||
truthpartfor(1); |
|||
vars[0][1]=true; |
|||
truthpartfor(1); |
|||
vars[0][1]=-1; |
|||
document.body.appendChild(elem); |
|||
} |
} |
||
function truthpartfor(index){ |
function truthpartfor(index){ |
||
if(index==vars.length){ |
|||
var str,i; |
|||
str=""; |
|||
for(i=0;i<index;i++)str+=(vars[i][1]?"<b>T</b>":"F")+" "; |
|||
elem.innerHTML+=str+(parsebool()?"<b>T</b>":"F")+"\n"; |
|||
return; |
|||
} |
|||
} |
|||
vars[index][1]=false; |
|||
truthpartfor(index+1); |
|||
vars[index][1]=true; |
|||
truthpartfor(index+1); |
|||
vars[index][1]=-1; |
|||
} |
} |
||
function parsebool(){ |
function parsebool(){ |
||
var stack,i,idx; |
|||
console.log(vars); |
|||
stack=[]; |
|||
for(i=0;i<expr.length;i++){ |
|||
if(expr[i]=="T")stack.push(true); |
|||
else if(expr[i]=="F")stack.push(false); |
|||
else if((idx=varsindexof(expr[i]))!=-1)stack.push(vars[idx][1]); |
|||
else if(isboolop(expr[i])){ |
|||
switch(expr[i]){ |
|||
case "&":stack.push(stack.pop()&stack.pop());break; |
|||
case "|":stack.push(stack.pop()|stack.pop());break; |
|||
case "!":stack.push(!stack.pop());break; |
|||
case "^":stack.push(stack.pop()^stack.pop());break; |
|||
} |
|||
} |
|||
} else alert("Non-conformant character "+expr[i]+" in expression. Should not be possible."); |
|||
console.log(stack); |
|||
} |
|||
} |
|||
return stack[0]; |
|||
} |
} |
||
</script></head><body onload="printtruthtable()"></body></html></lang> |
</script></head><body onload="printtruthtable()"></body></html></lang> |
||
| Line 2,014: | Line 2,014: | ||
<pre>TruthTable["V ~Xor~ (B ~Xor~ (K ~Xor~ D ) )"] |
<pre>TruthTable["V ~Xor~ (B ~Xor~ (K ~Xor~ D ) )"] |
||
B |
B D K V V ~Xor~ (B ~Xor~ (K ~Xor~ D ) ) |
||
False |
False False False False False |
||
False |
False False False True True |
||
False |
False False True False True |
||
False |
False False True True False |
||
False |
False True False False True |
||
False |
False True False True False |
||
False |
False True True False False |
||
False |
False True True True True |
||
True |
True False False False True |
||
True |
True False False True False |
||
True |
True False True False False |
||
True |
True False True True True |
||
True |
True True False False False |
||
True |
True True False True True |
||
True |
True True True False True |
||
True |
True True True True False</pre> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
| Line 2,125: | Line 2,125: | ||
It would be easy to modify the program to take <code>+</code> for XOR instead. |
It would be easy to modify the program to take <code>+</code> for XOR instead. |
||
<lang parigp>vars(P)={ |
<lang parigp>vars(P)={ |
||
my(v=List(),x); |
|||
while(type(P)=="t_POL", |
|||
x=variable(P); |
|||
listput(v,x); |
|||
P=subst(P,x,1) |
|||
); |
|||
Vec(v) |
|||
}; |
}; |
||
truthTable(P)={ |
truthTable(P)={ |
||
my(var=vars(P),t,b); |
|||
for(i=0,2^#var-1, |
|||
t=eval(P); |
|||
for(j=1,#var, |
|||
b=bittest(i,j-1); |
|||
t=subst(t,var[j],b); |
|||
print1(b) |
|||
); |
|||
); |
|||
print(!!t) |
|||
); |
|||
}; |
}; |
||
truthTable("x+y") \\ OR |
truthTable("x+y") \\ OR |
||
| Line 2,455: | Line 2,455: | ||
sub truth_table { |
sub truth_table { |
||
my $s = shift; |
|||
my (%seen, @vars); |
|||
for ($s =~ /([a-zA-Z_]\w*)/g) { |
|||
$seen{$_} //= do { push @vars, $_; 1 }; |
|||
} |
|||
} |
|||
print "\n", join("\t", @vars, $s), "\n", '-' x 40, "\n"; |
|||
@vars = map("\$$_", @vars); |
|||
$s =~ s/([a-zA-Z_]\w*)/\$$1/g; |
|||
$s = "print(".join(',"\t", ', map("($_?'T':'F')", @vars, $s)).",\"\\n\")"; |
|||
$s = "for my $_ (0, 1) { $s }" for (reverse @vars); |
|||
eval $s; |
|||
} |
} |
||
| Line 2,771: | Line 2,771: | ||
{{works with|SWI-Prolog|Any - tested with release 7.6.4}} |
{{works with|SWI-Prolog|Any - tested with release 7.6.4}} |
||
<lang prolog>/* |
<lang prolog>/* |
||
To evaluate the truth table a line of text is inputted and then there are three steps |
|||
Let's say the expression is: |
|||
'not a and (b or c)' |
|||
Step 1: tokenize into atoms and brackets |
|||
eg: Tokenized = [ not, a, and, '(', b, or, c, ')' ]. |
|||
Step 2: convert to a term that can be evaluated, and get out the variables |
|||
eg: Expression = op(and, op(not, a), op(or, b, c)), Variables = [ a, b, c ] |
|||
Step 3: permeate over the variables, substituting the values for each var, and evaluate the expression for each permutation |
|||
eg: [ 0, 0, 0] |
|||
op(and, op(not, 0), op(or, 0, 0)) |
|||
op(and, 1, op(or, 0, 0)) |
|||
op(and, 1, 0) |
|||
0 |
|||
0 |
|||
[ 0, 0, 1] |
|||
op(and, op(not, 0), op(or, 0, 1)) |
|||
op(and, 1, op(or, 0, 0)) |
|||
op(and, 1, 1) |
|||
1 |
|||
1 |
|||
*/ |
*/ |
||
truth_table :- |
truth_table :- |
||
current_input(In), |
|||
read_line_to_codes(In, Line), |
|||
atom_codes(A, Line), |
|||
atom_chars(A, Chars), |
|||
% parse everything into the form we want |
|||
phrase(tok(Tok), Chars, _), |
|||
phrase(expr(Expr,Vars), Tok, _), |
|||
list_to_set(Vars,VarSet), |
|||
% evaluate |
|||
print_expr(Expr, VarSet), !. |
|||
print_expr(Expr, Vars) :- |
print_expr(Expr, Vars) :- |
||
% write the header (once) |
|||
maplist(format('~p '), Vars), |
|||
format('~n'), |
|||
% write the results for as many times as there are rows |
|||
eval_expr(Expr, Vars, Tvals, R), |
|||
maplist(format('~p '), Tvals), |
|||
format('~p~n', R), |
|||
fail. |
|||
print_expr(_, _). |
print_expr(_, _). |
||
% Step 1 - tokenize the input into spaces, brackets and atoms |
% Step 1 - tokenize the input into spaces, brackets and atoms |
||
tok([A|As]) --> spaces(_), chars([X|Xs]), {atom_codes(A, [X|Xs])}, spaces(_), tok(As). |
tok([A|As]) --> spaces(_), chars([X|Xs]), {atom_codes(A, [X|Xs])}, spaces(_), tok(As). |
||
| Line 2,831: | Line 2,831: | ||
bracket('(') --> ['(']. |
bracket('(') --> ['(']. |
||
bracket(')') --> [')']. |
bracket(')') --> [')']. |
||
% Step 2 - Parse the expression into an evaluable term |
% Step 2 - Parse the expression into an evaluable term |
||
expr(op(I, E, E2), V) --> starter(E, V1), infix(I), expr(E2, V2), { append(V1, V2, V) }. |
expr(op(I, E, E2), V) --> starter(E, V1), infix(I), expr(E2, V2), { append(V1, V2, V) }. |
||
| Line 2,848: | Line 2,848: | ||
variable(V) --> [V], \+ infix(V), \+ bracket(V). |
variable(V) --> [V], \+ infix(V), \+ bracket(V). |
||
space(' ') --> [' ']. |
space(' ') --> [' ']. |
||
char(X) --> [X], { dif(X, ' ') }. |
char(X) --> [X], { dif(X, ' ') }. |
||
% Step 3 - evaluate the parsed expression |
% Step 3 - evaluate the parsed expression |
||
eval_expr(Expr, Vars, Tvals, R) :- |
eval_expr(Expr, Vars, Tvals, R) :- |
||
length(Vars,Len), |
|||
length(Tvals, Len), |
|||
maplist(truth_val, Tvals), |
|||
eval(Expr, [Tvals,Vars],R). |
|||
eval(X, [Vals,Vars], R) :- nth1(N,Vars,X), nth1(N,Vals,R). |
eval(X, [Vals,Vars], R) :- nth1(N,Vars,X), nth1(N,Vals,R). |
||
| Line 3,086: | Line 3,086: | ||
<pre> |
<pre> |
||
$ truthtable 'A ^ B' |
$ truthtable 'A ^ B' |
||
A |
A B A ^ B |
||
False |
False False False |
||
False |
False True True |
||
True |
True False True |
||
True |
True True False |
||
$ truthtable 'foo & bar | baz' |
$ truthtable 'foo & bar | baz' |
||
foo |
foo bar baz foo & bar | baz |
||
False |
False False False False |
||
False |
False False True True |
||
False |
False True False False |
||
False |
False True True True |
||
True |
True False False False |
||
True |
True False True True |
||
True |
True True False True |
||
True |
True True True True |
||
$ truthtable 'Jim & (Spock ^ Bones) | Scotty' |
$ truthtable 'Jim & (Spock ^ Bones) | Scotty' |
||
Jim |
Jim Spock Bones Scotty Jim & (Spock ^ Bones) | Scotty |
||
False |
False False False False False |
||
False |
False False False True True |
||
False |
False False True False False |
||
False |
False False True True True |
||
False |
False True False False False |
||
False |
False True False True True |
||
False |
False True True False False |
||
False |
False True True True True |
||
True |
True False False False False |
||
True |
True False False True True |
||
True |
True False True False True |
||
True |
True False True True True |
||
True |
True True False False True |
||
True |
True True False True True |
||
True |
True True True False False |
||
True |
True True True True True</pre> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
| Line 3,531: | Line 3,531: | ||
true true true false | true |
true true true false | true |
||
true true true true | false</pre> |
true true true true | false</pre> |
||
=={{header|Rust}}== |
|||
The solution accepts Boolean expressions in infix notation with priorities and parentheses. |
|||
Operators NOT, AND, OR and XOR are supported and recognized in a few common notations (e.g., <code>OR</code>, <code>or</code> and <code>|</code> are equivalent). |
|||
Non-word symbols does not have to be separated with spaces, for instance <code>a|b&c</code> is parsed correctly. |
|||
The implementation is mostly generic (tokenizer, infix-to-postfix translation and evaluation automaton) and not limited to Boolean expressions. |
|||
There is no thorough verification that the tokens form an actual infix expression though. |
|||
Therefore an invalid expression may be accepted if its evaluation finishes without an error. |
|||
Extending the set of implemented operators should be almost trivial without any change of the logically more complex parts. |
|||
<lang Rust>use std::{ |
|||
collections::HashMap, |
|||
fmt::{Display, Formatter}, |
|||
iter::FromIterator, |
|||
}; |
|||
// Generic expression evaluation automaton and expression formatting support |
|||
#[derive(Clone, Debug)] |
|||
pub enum EvaluationError<T> { |
|||
NoResults, |
|||
TooManyResults, |
|||
OperatorFailed(T), |
|||
} |
|||
pub trait Operator<T> { |
|||
type Err; |
|||
fn execute(&self, stack: &mut Vec<T>) -> Result<(), Self::Err>; |
|||
} |
|||
#[derive(Clone, Copy, Debug)] |
|||
enum Element<O> { |
|||
Operator(O), |
|||
Variable(usize), |
|||
} |
|||
#[derive(Clone, Debug)] |
|||
pub struct Expression<O> { |
|||
elements: Vec<Element<O>>, |
|||
symbols: Vec<String>, |
|||
} |
|||
impl<O> Expression<O> { |
|||
pub fn evaluate<T>( |
|||
&self, |
|||
mut bindings: impl FnMut(usize) -> T, |
|||
) -> Result<T, EvaluationError<O::Err>> |
|||
where |
|||
O: Operator<T>, |
|||
{ |
|||
let mut stack = Vec::new(); |
|||
for element in self.elements.iter() { |
|||
match element { |
|||
Element::Variable(index) => stack.push(bindings(*index)), |
|||
Element::Operator(op) => op |
|||
.execute(&mut stack) |
|||
.map_err(EvaluationError::OperatorFailed)?, |
|||
} |
|||
} |
|||
match stack.pop() { |
|||
Some(result) if stack.is_empty() => Ok(result), |
|||
Some(_) => Err(EvaluationError::TooManyResults), |
|||
None => Err(EvaluationError::NoResults), |
|||
} |
|||
} |
|||
pub fn symbols(&self) -> &[String] { |
|||
&self.symbols |
|||
} |
|||
pub fn formatted(&self) -> Result<String, EvaluationError<O::Err>> |
|||
where |
|||
O: Operator<Formatted>, |
|||
{ |
|||
self.evaluate(|index| Formatted(self.symbols[index].clone())) |
|||
.map(|formatted| formatted.0) |
|||
} |
|||
} |
|||
#[derive(Clone, Debug)] |
|||
pub struct Formatted(pub String); |
|||
impl Display for Formatted { |
|||
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { |
|||
write!(f, "{}", self.0) |
|||
} |
|||
} |
|||
impl<O> Display for Expression<O> |
|||
where |
|||
O: Operator<Formatted>, |
|||
{ |
|||
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { |
|||
match self.formatted() { |
|||
Ok(result) => write!(f, "{}", result), |
|||
Err(_) => write!(f, "<malformed expression>"), |
|||
} |
|||
} |
|||
} |
|||
// Generic parts of the parsing machinery |
|||
#[derive(Clone, Copy, Debug)] |
|||
pub enum Token<'a, O> { |
|||
LBrace, |
|||
RBrace, |
|||
Operator(O), |
|||
Variable(&'a str), |
|||
Malformed(&'a str), |
|||
} |
|||
pub type Symbol<'a, O> = (&'a str, bool, Token<'a, O>); |
|||
#[derive(Debug)] |
|||
pub struct Tokens<'a, O> { |
|||
source: &'a str, |
|||
symbols: &'a [Symbol<'a, O>], |
|||
} |
|||
impl<'a, O> Tokens<'a, O> { |
|||
pub fn new(source: &'a str, symbols: &'a [Symbol<'a, O>]) -> Self { |
|||
Self { source, symbols } |
|||
} |
|||
} |
|||
impl<'a, O: Clone> Iterator for Tokens<'a, O> { |
|||
type Item = Token<'a, O>; |
|||
fn next(&mut self) -> Option<Self::Item> { |
|||
self.source = self.source.trim_start(); |
|||
let symbol = self.symbols.iter().find_map(|(symbol, word, token)| { |
|||
if self.source.starts_with(symbol) { |
|||
let end = symbol.len(); |
|||
if *word { |
|||
match &self.source[end..].chars().next() { |
|||
Some(c) if !c.is_whitespace() => return None, |
|||
_ => (), |
|||
} |
|||
} |
|||
Some((token, end)) |
|||
} else { |
|||
None |
|||
} |
|||
}); |
|||
if let Some((token, end)) = symbol { |
|||
self.source = &self.source[end..]; |
|||
Some(token.clone()) |
|||
} else { |
|||
match self.source.chars().next() { |
|||
Some(c) if c.is_alphabetic() => { |
|||
let end = self |
|||
.source |
|||
.char_indices() |
|||
.find_map(|(i, c)| Some(i).filter(|_| !c.is_alphanumeric())) |
|||
.unwrap_or_else(|| self.source.len()); |
|||
let result = &self.source[0..end]; |
|||
self.source = &self.source[end..]; |
|||
Some(Token::Variable(result)) |
|||
} |
|||
Some(c) => { |
|||
let end = c.len_utf8(); |
|||
let result = &self.source[0..end]; |
|||
self.source = &self.source[end..]; |
|||
Some(Token::Malformed(result)) |
|||
} |
|||
None => None, |
|||
} |
|||
} |
|||
} |
|||
} |
|||
pub trait WithPriority { |
|||
type Priority; |
|||
fn priority(&self) -> Self::Priority; |
|||
} |
|||
impl<'a, O> FromIterator<Token<'a, O>> for Result<Expression<O>, Token<'a, O>> |
|||
where |
|||
O: WithPriority, |
|||
O::Priority: Ord, |
|||
{ |
|||
fn from_iter<T: IntoIterator<Item = Token<'a, O>>>(tokens: T) -> Self { |
|||
let mut token_stack = Vec::new(); |
|||
let mut indices = HashMap::new(); |
|||
let mut symbols = Vec::new(); |
|||
let mut elements = Vec::new(); |
|||
'outer: for token in tokens { |
|||
match token { |
|||
Token::Malformed(_) => return Err(token), |
|||
Token::LBrace => token_stack.push(token), |
|||
Token::RBrace => { |
|||
// Flush all operators to the matching LBrace |
|||
while let Some(token) = token_stack.pop() { |
|||
match token { |
|||
Token::LBrace => continue 'outer, |
|||
Token::Operator(op) => elements.push(Element::Operator(op)), |
|||
_ => return Err(token), |
|||
} |
|||
} |
|||
} |
|||
Token::Variable(name) => { |
|||
let index = indices.len(); |
|||
let symbol = name.to_string(); |
|||
let index = *indices.entry(symbol.clone()).or_insert_with(|| { |
|||
symbols.push(symbol); |
|||
index |
|||
}); |
|||
elements.push(Element::Variable(index)); |
|||
} |
|||
Token::Operator(ref op) => { |
|||
while let Some(token) = token_stack.pop() { |
|||
match token { |
|||
Token::Operator(pop) if op.priority() < pop.priority() => { |
|||
elements.push(Element::Operator(pop)); |
|||
} |
|||
Token::Operator(pop) => { |
|||
token_stack.push(Token::Operator(pop)); |
|||
break; |
|||
} |
|||
_ => { |
|||
token_stack.push(token); |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
token_stack.push(token); |
|||
} |
|||
} |
|||
} |
|||
// Handle leftovers |
|||
while let Some(token) = token_stack.pop() { |
|||
match token { |
|||
Token::Operator(op) => elements.push(Element::Operator(op)), |
|||
_ => return Err(token), |
|||
} |
|||
} |
|||
Ok(Expression { elements, symbols }) |
|||
} |
|||
} |
|||
// Definition of Boolean operators |
|||
#[derive(Clone, Copy, Debug, PartialEq, Eq)] |
|||
pub enum Boolean { |
|||
Or, |
|||
Xor, |
|||
And, |
|||
Not, |
|||
} |
|||
impl Display for Boolean { |
|||
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { |
|||
let s = match self { |
|||
Self::Or => "∨", |
|||
Self::And => "∧", |
|||
Self::Not => "¬", |
|||
Self::Xor => "⩛", |
|||
}; |
|||
write!(f, "{}", s) |
|||
} |
|||
} |
|||
impl WithPriority for Boolean { |
|||
type Priority = u8; |
|||
fn priority(&self) -> u8 { |
|||
match self { |
|||
Self::Or => 0, |
|||
Self::Xor => 1, |
|||
Self::And => 2, |
|||
Self::Not => 3, |
|||
} |
|||
} |
|||
} |
|||
#[derive(Clone, Debug)] |
|||
pub enum BooleanError { |
|||
StackUnderflow, |
|||
} |
|||
impl Operator<bool> for Boolean { |
|||
type Err = BooleanError; |
|||
fn execute(&self, stack: &mut Vec<bool>) -> Result<(), Self::Err> { |
|||
let mut pop = || stack.pop().ok_or(BooleanError::StackUnderflow); |
|||
let result = match self { |
|||
Boolean::Or => pop()? | pop()?, |
|||
Boolean::And => pop()? & pop()?, |
|||
Boolean::Xor => pop()? ^ pop()?, |
|||
Boolean::Not => !pop()?, |
|||
}; |
|||
stack.push(result); |
|||
Ok(()) |
|||
} |
|||
} |
|||
impl Operator<Formatted> for Boolean { |
|||
type Err = BooleanError; |
|||
fn execute(&self, stack: &mut Vec<Formatted>) -> Result<(), Self::Err> { |
|||
let mut pop = || stack.pop().ok_or(BooleanError::StackUnderflow); |
|||
let result = match self { |
|||
Boolean::Not => format!("{}{}", Boolean::Not, pop()?), |
|||
binary_operator => { |
|||
// The stack orders the operands backwards, so to format them |
|||
// properly, we have to count with the reversed popping order |
|||
let b = pop()?; |
|||
let a = pop()?; |
|||
format!("({} {} {})", a, binary_operator, b) |
|||
} |
|||
}; |
|||
stack.push(Formatted(result)); |
|||
Ok(()) |
|||
} |
|||
} |
|||
impl Boolean { |
|||
// It is important for the tokens to be ordered by their parsing priority (if |
|||
// some operator was a prefix of another operator, the prefix must come later) |
|||
const SYMBOLS: [Symbol<'static, Boolean>; 18] = [ |
|||
("(", false, Token::LBrace), |
|||
(")", false, Token::RBrace), |
|||
("|", false, Token::Operator(Boolean::Or)), |
|||
("∨", false, Token::Operator(Boolean::Or)), |
|||
("or", true, Token::Operator(Boolean::Or)), |
|||
("OR", true, Token::Operator(Boolean::Or)), |
|||
("&", false, Token::Operator(Boolean::And)), |
|||
("∧", false, Token::Operator(Boolean::And)), |
|||
("and", true, Token::Operator(Boolean::And)), |
|||
("AND", true, Token::Operator(Boolean::And)), |
|||
("!", false, Token::Operator(Boolean::Not)), |
|||
("¬", false, Token::Operator(Boolean::Not)), |
|||
("not", true, Token::Operator(Boolean::Not)), |
|||
("NOT", true, Token::Operator(Boolean::Not)), |
|||
("^", false, Token::Operator(Boolean::Xor)), |
|||
("⩛", false, Token::Operator(Boolean::Xor)), |
|||
("xor", true, Token::Operator(Boolean::Xor)), |
|||
("XOR", true, Token::Operator(Boolean::Xor)), |
|||
]; |
|||
pub fn tokenize(s: &str) -> Tokens<'_, Boolean> { |
|||
Tokens::new(s, &Self::SYMBOLS) |
|||
} |
|||
pub fn parse<'a>(s: &'a str) -> Result<Expression<Boolean>, Token<'a, Boolean>> { |
|||
Self::tokenize(s).collect() |
|||
} |
|||
} |
|||
// Finally the table printing |
|||
fn print_truth_table(s: &str) -> Result<(), std::borrow::Cow<'_, str>> { |
|||
let expression = Boolean::parse(s).map_err(|e| format!("Parsing failed at token {:?}", e))?; |
|||
let formatted = expression |
|||
.formatted() |
|||
.map_err(|_| "Malformed expression detected.")?; |
|||
let var_count = expression.symbols().len(); |
|||
if var_count > 64 { |
|||
return Err("Too many variables to list.".into()); |
|||
} |
|||
let column_widths = { |
|||
// Print header and compute the widths of columns |
|||
let mut widths = Vec::with_capacity(var_count); |
|||
for symbol in expression.symbols() { |
|||
print!("{} ", symbol); |
|||
widths.push(symbol.chars().count() + 2); // Include spacing |
|||
} |
|||
println!("{}", formatted); |
|||
let width = widths.iter().sum::<usize>() + formatted.chars().count(); |
|||
(0..width).for_each(|_| print!("-")); |
|||
println!(); |
|||
widths |
|||
}; |
|||
// Choose the bit extraction order for the more traditional table ordering |
|||
let var_value = |input, index| (input >> (var_count - 1 - index)) & 1 ^ 1; |
|||
// Use counter to enumerate all bit combinations |
|||
for var_values in 0u64..(1 << var_count) { |
|||
for (var_index, width) in column_widths.iter().enumerate() { |
|||
let value = var_value(var_values, var_index); |
|||
print!("{:<width$}", value, width = width); |
|||
} |
|||
match expression.evaluate(|var_index| var_value(var_values, var_index) == 1) { |
|||
Ok(result) => println!("{}", if result { "1" } else { "0" }), |
|||
Err(e) => println!("{:?}", e), |
|||
} |
|||
} |
|||
println!(); |
|||
Ok(()) |
|||
} |
|||
fn main() { |
|||
loop { |
|||
let input = { |
|||
println!("Enter the expression to parse (or nothing to quit):"); |
|||
let mut input = String::new(); |
|||
std::io::stdin().read_line(&mut input).unwrap(); |
|||
println!(); |
|||
input |
|||
}; |
|||
if input.trim().is_empty() { |
|||
break; |
|||
} |
|||
if let Err(e) = print_truth_table(&input) { |
|||
eprintln!("{}\n", e); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Enter the expression to parse (or nothing to quit): |
|||
Jim & (Spock xor Bones) | Scotty |
|||
Jim Spock Bones Scotty ((Jim ∧ (Spock ⩛ Bones)) ∨ Scotty) |
|||
------------------------------------------------------------- |
|||
1 1 1 1 1 |
|||
1 1 1 0 0 |
|||
1 1 0 1 1 |
|||
1 1 0 0 1 |
|||
1 0 1 1 1 |
|||
1 0 1 0 1 |
|||
1 0 0 1 1 |
|||
1 0 0 0 0 |
|||
0 1 1 1 1 |
|||
0 1 1 0 0 |
|||
0 1 0 1 1 |
|||
0 1 0 0 0 |
|||
0 0 1 1 1 |
|||
0 0 1 0 0 |
|||
0 0 0 1 1 |
|||
0 0 0 0 0 |
|||
Enter the expression to parse (or nothing to quit): |
|||
</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
| Line 3,561: | Line 4,034: | ||
<pre> |
<pre> |
||
Boolean expression (e.g. 'a & b'): (a & b) | c |
Boolean expression (e.g. 'a & b'): (a & b) | c |
||
a |
a b c | (a & b) | c |
||
false |
false false false | false |
||
false |
false false true | true |
||
false |
false true false | false |
||
false |
false true true | true |
||
true |
true false false | false |
||
true |
true false true | true |
||
true |
true true false | true |
||
true |
true true true | true |
||
</pre> |
</pre> |
||
| Line 3,593: | Line 4,066: | ||
<pre> |
<pre> |
||
Enter a boolean expression: ($a&&$b)||$c |
Enter a boolean expression: ($a&&$b)||$c |
||
$a |
$a $b $c Result |
||
0 |
0 0 0 0 |
||
0 |
0 0 1 1 |
||
0 |
0 1 0 0 |
||
0 |
0 1 1 1 |
||
1 |
1 0 0 0 |
||
1 |
1 0 1 1 |
||
1 |
1 1 0 1 |
||
1 |
1 1 1 1 |
||
</pre> |
</pre> |
||