248 lines
8.6 KiB
C#
248 lines
8.6 KiB
C#
using System;
|
|
using System.Collections;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
using System.Text;
|
|
|
|
public class TruthTable
|
|
{
|
|
enum TokenType { Unknown, WhiteSpace, Constant, Operand, Operator, LeftParenthesis, RightParenthesis }
|
|
|
|
readonly char trueConstant, falseConstant;
|
|
readonly IDictionary<char, Operator> operators = new Dictionary<char, Operator>();
|
|
|
|
public TruthTable(char falseConstant, char trueConstant)
|
|
{
|
|
this.trueConstant = trueConstant;
|
|
this.falseConstant = falseConstant;
|
|
Operators = new OperatorCollection(operators);
|
|
}
|
|
|
|
public OperatorCollection Operators { get; }
|
|
|
|
public void PrintTruthTable(string expression, bool isPostfix = false)
|
|
{
|
|
try {
|
|
foreach (string line in GetTruthTable(expression, isPostfix)) {
|
|
Console.WriteLine(line);
|
|
}
|
|
} catch (ArgumentException ex) {
|
|
Console.WriteLine(expression + " " + ex.Message);
|
|
}
|
|
}
|
|
|
|
public IEnumerable<string> GetTruthTable(string expression, bool isPostfix = false)
|
|
{
|
|
if (string.IsNullOrWhiteSpace(expression)) throw new ArgumentException("Invalid expression.");
|
|
//Maps parameters to an index in BitSet
|
|
//Makes sure they appear in the truth table in the order they first appear in the expression
|
|
var parameters = expression
|
|
.Where(c => TypeOf(c) == TokenType.Operand)
|
|
.Distinct()
|
|
.Reverse()
|
|
.Select((c, i) => (symbol: c, index: i))
|
|
.ToDictionary(p => p.symbol, p => p.index);
|
|
|
|
int count = parameters.Count;
|
|
if (count > 32) throw new ArgumentException("Cannot have more than 32 parameters.");
|
|
string header = count == 0 ? expression : string.Join(" ",
|
|
parameters.OrderByDescending(p => p.Value).Select(p => p.Key)) + " " + expression;
|
|
|
|
if (!isPostfix) expression = ConvertToPostfix(expression);
|
|
|
|
var values = default(BitSet);
|
|
var stack = new Stack<char>(expression.Length);
|
|
for (int loop = 1 << count; loop > 0; loop--) {
|
|
foreach (char token in expression) stack.Push(token);
|
|
bool result = Evaluate(stack, values, parameters);
|
|
if (header != null) {
|
|
if (stack.Count > 0) throw new ArgumentException("Invalid expression.");
|
|
yield return header;
|
|
header = null;
|
|
}
|
|
string line = (count == 0 ? "" : " ") + (result ? trueConstant : falseConstant);
|
|
line = string.Join(" ", Enumerable.Range(0, count)
|
|
.Select(i => values[count - i - 1] ? trueConstant : falseConstant)) + line;
|
|
yield return line;
|
|
values++;
|
|
}
|
|
}
|
|
|
|
public string ConvertToPostfix(string infix)
|
|
{
|
|
var stack = new Stack<char>();
|
|
var postfix = new StringBuilder();
|
|
foreach (char c in infix) {
|
|
switch (TypeOf(c)) {
|
|
case TokenType.WhiteSpace:
|
|
continue;
|
|
case TokenType.Constant:
|
|
case TokenType.Operand:
|
|
postfix.Append(c);
|
|
break;
|
|
case TokenType.Operator:
|
|
int precedence = Precedence(c);
|
|
while (stack.Count > 0 && Precedence(stack.Peek()) > precedence) {
|
|
postfix.Append(stack.Pop());
|
|
}
|
|
stack.Push(c);
|
|
break;
|
|
case TokenType.LeftParenthesis:
|
|
stack.Push(c);
|
|
break;
|
|
case TokenType.RightParenthesis:
|
|
char top = default(char);
|
|
while (stack.Count > 0) {
|
|
top = stack.Pop();
|
|
if (top == '(') break;
|
|
else postfix.Append(top);
|
|
}
|
|
if (top != '(') throw new ArgumentException("No matching left parenthesis.");
|
|
break;
|
|
default:
|
|
throw new ArgumentException("Invalid character: " + c);
|
|
}
|
|
}
|
|
while (stack.Count > 0) {
|
|
char top = stack.Pop();
|
|
if (top == '(') throw new ArgumentException("No matching right parenthesis.");
|
|
postfix.Append(top);
|
|
}
|
|
return postfix.ToString();
|
|
}
|
|
|
|
private bool Evaluate(Stack<char> expression, BitSet values, IDictionary<char, int> parameters)
|
|
{
|
|
if (expression.Count == 0) throw new ArgumentException("Invalid expression.");
|
|
char c = expression.Pop();
|
|
TokenType type = TypeOf(c);
|
|
while (type == TokenType.WhiteSpace) type = TypeOf(c = expression.Pop());
|
|
switch (type) {
|
|
case TokenType.Constant:
|
|
return c == trueConstant;
|
|
case TokenType.Operand:
|
|
return values[parameters[c]];
|
|
case TokenType.Operator:
|
|
bool right = Evaluate(expression, values, parameters);
|
|
Operator op = operators[c];
|
|
if (op.Arity == 1) return op.Function(right, right);
|
|
bool left = Evaluate(expression, values, parameters);
|
|
return op.Function(left, right);
|
|
default:
|
|
throw new ArgumentException("Invalid character: " + c);
|
|
}
|
|
}
|
|
|
|
private TokenType TypeOf(char c)
|
|
{
|
|
if (char.IsWhiteSpace(c)) return TokenType.WhiteSpace;
|
|
if (c == '(') return TokenType.LeftParenthesis;
|
|
if (c == ')') return TokenType.RightParenthesis;
|
|
if (c == trueConstant || c == falseConstant) return TokenType.Constant;
|
|
if (operators.ContainsKey(c)) return TokenType.Operator;
|
|
if (char.IsLetter(c)) return TokenType.Operand;
|
|
return TokenType.Unknown;
|
|
}
|
|
|
|
private int Precedence(char op) => operators.TryGetValue(op, out var o) ? o.Precedence : int.MinValue;
|
|
}
|
|
|
|
struct Operator
|
|
{
|
|
public Operator(char symbol, int precedence, Func<bool, bool> function) : this(symbol, precedence, 1, (l, r) => function(r)) { }
|
|
|
|
public Operator(char symbol, int precedence, Func<bool, bool, bool> function) : this(symbol, precedence, 2, function) { }
|
|
|
|
private Operator(char symbol, int precedence, int arity, Func<bool, bool, bool> function) : this()
|
|
{
|
|
Symbol = symbol;
|
|
Precedence = precedence;
|
|
Arity = arity;
|
|
Function = function;
|
|
}
|
|
|
|
public char Symbol { get; }
|
|
public int Precedence { get; }
|
|
public int Arity { get; }
|
|
public Func<bool, bool, bool> Function { get; }
|
|
}
|
|
|
|
public class OperatorCollection : IEnumerable
|
|
{
|
|
readonly IDictionary<char, Operator> operators;
|
|
|
|
internal OperatorCollection(IDictionary<char, Operator> operators) {
|
|
this.operators = operators;
|
|
}
|
|
|
|
public void Add(char symbol, int precedence, Func<bool, bool> function)
|
|
=> operators[symbol] = new Operator(symbol, precedence, function);
|
|
public void Add(char symbol, int precedence, Func<bool, bool, bool> function)
|
|
=> operators[symbol] = new Operator(symbol, precedence, function);
|
|
|
|
public void Remove(char symbol) => operators.Remove(symbol);
|
|
|
|
IEnumerator IEnumerable.GetEnumerator() => operators.Values.GetEnumerator();
|
|
}
|
|
|
|
struct BitSet
|
|
{
|
|
private int bits;
|
|
|
|
private BitSet(int bits) { this.bits = bits; }
|
|
|
|
public static BitSet operator ++(BitSet bitSet) => new BitSet(bitSet.bits + 1);
|
|
|
|
public bool this[int index] => (bits & (1 << index)) != 0;
|
|
}
|
|
|
|
class Program
|
|
{
|
|
public static void Main() {
|
|
TruthTable tt = new TruthTable('F', 'T') {
|
|
Operators = {
|
|
{ '!', 6, r => !r },
|
|
{ '&', 5, (l, r) => l && r },
|
|
{ '^', 4, (l, r) => l ^ r },
|
|
{ '|', 3, (l, r) => l || r }
|
|
}
|
|
};
|
|
//Add a crazy operator:
|
|
var rng = new Random();
|
|
tt.Operators.Add('?', 6, r => rng.NextDouble() < 0.5);
|
|
string[] expressions = {
|
|
"!!!T",
|
|
"?T",
|
|
"F & x | T",
|
|
"F & (x | T",
|
|
"F & x | T)",
|
|
"a ! (a & a)",
|
|
"a | (a * a)",
|
|
"a ^ T & (b & !c)",
|
|
};
|
|
foreach (string expression in expressions) {
|
|
tt.PrintTruthTable(expression);
|
|
Console.WriteLine();
|
|
}
|
|
|
|
//Define a different language
|
|
tt = new TruthTable('0', '1') {
|
|
Operators = {
|
|
{ '-', 6, r => !r },
|
|
{ '^', 5, (l, r) => l && r },
|
|
{ 'v', 3, (l, r) => l || r },
|
|
{ '>', 2, (l, r) => !l || r },
|
|
{ '=', 1, (l, r) => l == r },
|
|
}
|
|
};
|
|
expressions = new[] {
|
|
"-X v 0 = X ^ 1",
|
|
"(H > M) ^ (S > H) > (S > M)"
|
|
};
|
|
foreach (string expression in expressions) {
|
|
tt.PrintTruthTable(expression);
|
|
Console.WriteLine();
|
|
}
|
|
}
|
|
}
|