Anonymous user
Truth table: Difference between revisions
Add source for Rust
(Add clojure solution to truth tables) |
(Add source for Rust) |
||
Line 941:
{{incorrect|Déjà Vu|User input is not arbitrary but fixed to the three examples shown}}
<lang dejavu>print-line lst end:
(print-truth-table) t n func:
print-truth-table vars name func:
stu s t u:
abcd a b c d:
print-truth-table [ "A" "B" ] "A ^ B" @/=
Line 967:
print-truth-table [ "A" "B" "C" "D" ] "A ^ (B ^ (C ^ D))" @abcd</lang>
{{out}}
<pre>A
0
0
1
1
S
0
0
0
0
1
1
1
1
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
</pre>
Line 1,582:
function isboolop(chr){return "&|!^".indexOf(chr)!=-1;}
function varsindexof(chr){
}
function printtruthtable(){
}
function truthpartfor(index){
}
}
function parsebool(){
}
}
}
</script></head><body onload="printtruthtable()"></body></html></lang>
Line 2,014:
<pre>TruthTable["V ~Xor~ (B ~Xor~ (K ~Xor~ D ) )"]
B
False
False
False
False
False
False
False
False
True
True
True
True
True
True
True
True
=={{header|Maxima}}==
Line 2,125:
It would be easy to modify the program to take <code>+</code> for XOR instead.
<lang parigp>vars(P)={
};
truthTable(P)={
);
};
truthTable("x+y") \\ OR
Line 2,455:
sub truth_table {
}
}
Line 2,771:
{{works with|SWI-Prolog|Any - tested with release 7.6.4}}
<lang prolog>/*
0
1
*/
truth_table :-
print_expr(Expr, Vars) :-
print_expr(_, _).
% 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).
Line 2,831:
bracket('(') --> ['('].
bracket(')') --> [')'].
% 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) }.
Line 2,848:
variable(V) --> [V], \+ infix(V), \+ bracket(V).
space(' ') --> [' '].
char(X) --> [X], { dif(X, ' ') }.
% Step 3 - evaluate the parsed expression
eval_expr(Expr, Vars, Tvals, R) :-
eval(X, [Vals,Vars], R) :- nth1(N,Vars,X), nth1(N,Vals,R).
Line 3,086:
<pre>
$ truthtable 'A ^ B'
A
False
False
True
True
$ truthtable 'foo & bar | baz'
foo
False
False
False
False
True
True
True
True
$ truthtable 'Jim & (Spock ^ Bones) | Scotty'
Jim
False
False
False
False
False
False
False
False
True
True
True
True
True
True
True
True
=={{header|REXX}}==
Line 3,531:
true true true false | true
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}}==
Line 3,561 ⟶ 4,034:
<pre>
Boolean expression (e.g. 'a & b'): (a & b) | c
a
false
false
false
false
true
true
true
true
</pre>
Line 3,593 ⟶ 4,066:
<pre>
Enter a boolean expression: ($a&&$b)||$c
$a
0
0
0
0
1
1
1
1
</pre>
| |||