parser.ts

const LogicValues = [true, false] as const;
type Logic = typeof LogicValues[number];
const CARDINALITY = LogicValues.length;

type Literal = { __t: "Literal"; symbol: string };
type UnaryOperator = { __t: "Unary"; e: (a: Logic) => Logic };
type BinaryOperator = { __t: "Binary"; e: (a: Logic, b: Logic) => Logic };

type Token = Literal | UnaryOperator | BinaryOperator;

type LogicTable = {
  [symbol: string]: boolean;
  result: Logic;
}[];

const binaryOperators: Record<string, BinaryOperator["e"]> = {
  "->": (a, b) => !a || b,
  "^": (a, b) => a && b,
  v: (a, b) => a || b,
  "<=>": (a, b) => a === b,
};

const unaryOperators: Record<string, UnaryOperator["e"]> = {
  "~": (a) => !a,
};

const allOperators = { ...unaryOperators, ...binaryOperators };

const assert = (a: boolean, msg: string) => {
  if (!a) {
    throw new Error(msg);
  }
};

function parseToken(token: string): Token {
  if (token in unaryOperators) {
    return { __t: "Unary", e: unaryOperators[token] };
  } else if (token in binaryOperators) {
    return { __t: "Binary", e: binaryOperators[token] };
  } else {
    return { __t: "Literal", symbol: token };
  }
}

function parse(expression: string): Token[] {
  const out: Token[] = [];
  const stack: string[] = [];

  const tokens = expression.replace(/\s/g, "").split("");
  outer: for (let i = 0; i < tokens.length; ++i) {
    for (const op in unaryOperators) {
      if (tokens.slice(i, i + op.length).join("") === op) {
        stack.push(op);
        i += op.length - 1;
        continue outer;
      }
    }

    for (const op in binaryOperators) {
      if (tokens.slice(i, i + op.length).join("") === op) {
        while (stack.length > 0 && stack[stack.length - 1] in allOperators) {
          out.push(parseToken(stack.pop()));
        }
        stack.push(op);
        i += op.length - 1;
        continue outer;
      }
    }

    const token = tokens[i];
    if (token === "(") {
      stack.push("(");
    } else if (token === ")") {
      while (stack.length > 0 && stack[stack.length - 1] !== "(") {
        out.push(parseToken(stack.pop()));
      }
      assert(stack.pop() === "(", "Unbalanced parentheses 1!");
    } else {
      out.push({ __t: "Literal", symbol: token });
    }
  }

  while (stack.length > 0) {
    const token = stack.pop();
    assert(token !== "(" && token !== ")", "Unbalanced parentheses 2!");
    out.push(parseToken(token));
  }

  return out;
}

function execute(tokens: Token[]): LogicTable {
  const symbolsSet = new Set<string>();
  for (const token of tokens) {
    if (token.__t === "Literal") {
      symbolsSet.add(token.symbol);
    }
  }

  const permutations = CARDINALITY ** symbolsSet.size;
  const symbols = Array.from(symbolsSet);
  const valuesMap = Object.fromEntries(
    symbols.map((val) => [val, LogicValues[0] as Logic])
  );

  const results: LogicTable = [];

  for (let i = 0; i < permutations; ++i) {
    const perm = i
      .toString(CARDINALITY)
      .padStart(symbols.length, "0")
      .slice(-symbols.length)
      .split("")
      .map((val) => parseInt(val, CARDINALITY));

    for (let j = 0; j < symbols.length; ++j) {
      valuesMap[symbols[j]] = LogicValues[perm[j]];
    }

    results.push({
      ...valuesMap,
      result: executePermutation(tokens, valuesMap),
    });
  }

  return results;
}

function executePermutation(
  tokens: Token[],
  valueMap: Record<string, Logic>
): Logic {
  const stack: Logic[] = [];
  for (const token of tokens) {
    if (token.__t === "Literal") {
      stack.push(valueMap[token.symbol]);
    } else if (token.__t === "Binary") {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(token.e(a, b));
    } else if (token.__t === "Unary") {
      const a = stack.pop();
      stack.push(token.e(a));
    }
  }
  assert(stack.length === 1, "Stack has more than one element!");
  return stack[0];
}

/******************************/
// Tests

const isOk = (t: LogicTable) => t.every((t) => t.result === LogicValues[0]);
const isNotOk = (t: LogicTable) => t.some((t) => t.result !== LogicValues[0]);

console.assert(isOk(execute(parse("A -> B <=> ~B -> ~A"))));
console.assert(isOk(execute(parse("~(A v B) <=> (~A ^ ~B)"))));
console.assert(isOk(execute(parse("(~(A ^ B)) <=> (~A v ~B)"))));