A truth table is a display of the inputs to, and the output of a Boolean function organized as a table where each row gives one combination of input values and the corresponding value of the function.



Task

 Input a Boolean function from the user as a string then calculate and print a formatted truth table for the given function.
 (One can assume that the user input is correct).
 Print and show output for Boolean functions of two and three input variables, but any program should not be limited to that many variables in the function. 
 Either reverse-polish or infix notation expressions are allowed.


Related tasks

   Boolean values
   Ternary logic


See also

   Wolfram MathWorld entry on truth tables.
   some "truth table" examples from Google.


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);
        }
    }
}