expr.ts

type Register<TOTAL, CARRY> = [TOTAL, CARRY];

type AddToRegister<
  R extends Register<string, string>,
  A extends string,
  B extends string
> = A extends `1`
  ? B extends `1`
    ? R[1] extends `1`
      ? Register<`1${R[0]}`, `1`>
      : Register<`0${R[0]}`, `1`>
    : R[1] extends `1`
    ? Register<`0${R[0]}`, `1`>
    : Register<`1${R[0]}`, ``>
  : B extends `1`
  ? R[1] extends `1`
    ? Register<`0${R[0]}`, `1`>
    : Register<`1${R[0]}`, ``>
  : R[1] extends `1`
  ? Register<`1${R[0]}`, ``>
  : Register<`0${R[0]}`, ``>;

type Adder<
  A extends string,
  B extends string,
  R extends Register<string, string>
> = A extends `${infer LeaderA}0`
  ? B extends `${infer LeaderB}0`
    ? Adder<LeaderA, LeaderB, AddToRegister<R, ``, ``>>
    : B extends `${infer LeaderB}1`
    ? Adder<LeaderA, LeaderB, AddToRegister<R, ``, `1`>>
    : Adder<LeaderA, "", AddToRegister<R, ``, ``>>
  : A extends `${infer LeaderA}1`
  ? B extends `${infer LeaderB}0`
    ? Adder<LeaderA, LeaderB, AddToRegister<R, `1`, ``>>
    : B extends `${infer LeaderB}1`
    ? Adder<LeaderA, LeaderB, AddToRegister<R, `1`, `1`>>
    : Adder<LeaderA, "", AddToRegister<R, `1`, ``>>
  : B extends `${infer LeaderB}0`
  ? Adder<"", LeaderB, AddToRegister<R, ``, ``>>
  : B extends `${infer LeaderB}1`
  ? Adder<"", LeaderB, AddToRegister<R, `1`, ``>>
  : `${R[1]}${R[0]}`;

type Add<A extends string, B extends string> = A extends UnrecognizedExpression
  ? UnrecognizedExpression
  : B extends UnrecognizedExpression
  ? UnrecognizedExpression
  : Adder<A, B, Register<``, ``>>;

type UnrecognizedExpression = "UnrecognizedExpression";

type BinaryDigit = "0" | "1";
type isBinaryNumber<D> = D extends `${BinaryDigit}${infer Rest}`
  ? Rest extends ""
    ? true
    : isBinaryNumber<Rest>
  : false;

type Expr<E extends string> = E extends ` ${infer WithoutWhitespace}`
  ? Expr<WithoutWhitespace>
  : E extends `${infer WithoutWhitespace} `
  ? Expr<WithoutWhitespace>
  : isBinaryNumber<E> extends true
  ? E
  : E extends `${infer A}+${infer B}`
  ? Add<Expr<A>, Expr<B>>
  : UnrecognizedExpression;

function equalsTo<T>(value: T) {
  console.log(value);
}

equalsTo<Expr<"0 + 0">>("0");
equalsTo<Expr<"0 + 1">>("1");
equalsTo<Expr<"1 + 0">>("1");
equalsTo<Expr<"1 + 1">>("10");
equalsTo<Expr<"11 + 1">>("100");
equalsTo<Expr<"11 + 11">>("110");
equalsTo<Expr<"1100100 + 11101011">>("101001111");
equalsTo<Expr<"1 + 1 + 1">>("11");
equalsTo<Expr<"11 + 11 + 11">>("1001");
equalsTo<Expr<"11 + 11 + 11 + 11">>("1100");
equalsTo<Expr<"11 + 11 + 11 + 11 + 11">>("1111");

equalsTo<Expr<"1 + 2">>("UnrecognizedExpression");
equalsTo<Expr<"1 * 1">>("UnrecognizedExpression");

export {}