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.


import sequtils, strutils, sugar
 
# List of possible variables names.
const VarChars = {'A'..'E', 'G'..'S', 'U'..'Z'}
 
type
 
  Expression = object
    names: seq[char]    # List of variables names.
    values: seq[bool]   # Associated values.
    formula: string     # Formula as a string.
 
 
proc initExpression(str: string): Expression =
  ## Build an expression from a string.
  for ch in str:
    if ch in VarChars and ch notin result.names:
      result.names.add ch
  result.values.setLen(result.names.len)
  result.formula = str
 
 
template apply(stack: seq[bool]; op: (bool, bool) -> bool): bool =
  ## Apply an operator on the last two operands of an evaluation stack.
  ## Needed to make sure that pops are done (avoiding short-circuit optimization).
  let op2 = stack.pop()
  let op1 = stack.pop()
  op(op1, op2)
 
 
proc evaluate(expr: Expression): bool =
  ## Evaluate the current expression.
 
  var stack: seq[bool]  # Evaluation stack.
 
  for e in expr.formula:
    stack.add case e
              of 'T': true
              of 'F': false
              of '!': not stack.pop()
              of '&': stack.apply(`and`)
              of '|': stack.apply(`or`)
              of '^': stack.apply(`xor`)
              else:
                if e in VarChars: expr.values[expr.names.find(e)]
                else:
                  raise newException(
                    ValueError, "Non-conformant character in expression: '$#'.".format(e))
 
  if stack.len != 1:
    raise newException(ValueError, "Ill-formed expression.")
  result = stack[0]
 
 
proc setVariables(expr: var Expression; pos: Natural) =
  ## Recursively set the variables.
  ## When all the variables are set, launch the evaluation of the expression
  ## and print the result.
 
  assert pos <= expr.values.len
 
  if pos == expr.values.len:
    # Evaluate and display.
    let vs = expr.values.mapIt(if it: 'T' else: 'F').join("  ")
    let es = if expr.evaluate(): 'T' else: 'F'
    echo vs, "  ", es
 
  else:
    # Set values.
    expr.values[pos] = false
    expr.setVariables(pos + 1)
    expr.values[pos] = true
    expr.setVariables(pos + 1)
 
 
echo "Accepts single-character variables (except for 'T' and 'F',"
echo "which specify explicit true or false values), postfix, with"
echo "&|!^ for and, or, not, xor, respectively; optionally"
echo "seperated by spaces or tabs. Just enter nothing to quit."
 
while true:
  # Read formula and create expression.
  stdout.write "\nBoolean expression: "
  let line = stdin.readLine.toUpperAscii.multiReplace((" ", ""), ("\t", ""))
  if line.len == 0: break
  var expr = initExpression(line)
  if expr.names.len == 0: break
 
  # Display the result.
  let vs = expr.names.join("  ")
  echo '\n', vs, "  ", expr.formula
  let h = vs.len + expr.formula.len + 2
  echo repeat('=', h)
  expr.setVariables(0)