typescript-katas/2kyu/evaluate-mathematical-expression/solution.ts

type TokenType = 'number' | 'operator' | 'parenthesis' | 'decimal';
type TokenValue = number | '+' | '-' | '*' | '/' | '(' | ')' | '.';

type Token = NumberToken | OperatorToken | ParenthesisToken | DecimalToken;

type OperatorChars = '+' | '-' | '*' | '/';
type OperatorToken = {
  type: 'operator',
  value: OperatorChars,
}

const isOperatorChar = (char: string): char is OperatorChars => {
  return char === '+' || char === '-' || char === '*' || char === '/';
}

type NumberToken = {
  type: 'number',
  value: string,
}

type ParenthesisChars = '(' | ')';
type ParenthesisToken = {
  type: 'parenthesis',
  value: ParenthesisChars,
}

const isParenthesisChar = (char: string): char is ParenthesisChars => {
  return char === '(' || char === ')';
}

type DecimalChars = '.';
type DecimalToken = {
  type: 'decimal',
  value: DecimalChars,
}

const isDecimalChar = (char: string): char is DecimalChars => {
  return char === '.';
}

export const tokenize = (expression: string): Token[] => {
  const tokens: Token[] = [];
  const chars = expression.split('');
  let done = false;
  let i = 0;
  while (!done) {
    if (i >= chars.length) {
      done = true;
      continue;
    }

    const char = chars[i];
    if (char === ' ') {
      i++;
      continue;
    }
    // parenthesis
    if (isParenthesisChar(char)) {
      tokens.push({ type: 'parenthesis', value: char });
      i++;
      continue;
    }
    // operator
    if (isOperatorChar(char)) {
      tokens.push({ type: 'operator', value: char });
      i++;
      continue;
    }
    // number
    if (char.match(/\d/)) {
      let number = '';
      while (chars[i] && chars[i].match(/\d/)) {
        number += chars[i];
        i++;
      }
      tokens.push({ type: 'number', value: number });
      continue;
    }
    // decimal
    if (isDecimalChar(char)) {
      tokens.push({ type: 'decimal', value: char });
      i++;
      continue;
    }

    throw new Error('Invalid character');
  }
  return tokens;
}

abstract class ASTNodeCommon {
  abstract readonly type: string;
  abstract get value(): number;
}

type ASTNode = NumberNode | OperatorNode | GroupNode | NegationNode;

class NumberNode extends ASTNodeCommon {
  private _value: number;
  type = 'numbernode';
  constructor(numValue: number) {
    super();
    this._value = numValue;
  }

  get value() {
    return this._value;
  }

  static fromToken(token: NumberToken): NumberNode {
    return new NumberNode(parseFloat(token.value));
  }

  static fromTokens(tokens: [NumberToken, DecimalToken, NumberToken]): NumberNode {
    return new NumberNode(parseFloat(tokens[0].value + '.' + tokens[2].value));
  }
}

class OperatorNode extends ASTNodeCommon {
  type = 'operatornode';
  constructor(public operator: OperatorChars, public left: ASTNode, public right: ASTNode) {
    super();
  }

  get value(): number {
    const left = this.left.value as number;
    const right = this.right.value as number;
    switch (this.operator) {
      case '+':
        return left + right;
      case '-':
        return left - right;
      case '*':
        return left * right;
      case '/':
        return left / right;
      default:
        throw new Error('Invalid operator');
    }
  }
}

class GroupNode extends ASTNodeCommon {
  type = 'groupnode';

  constructor(public child: ASTNode) {
    super();
  }

  get value(): number {
    return this.child.value as number;
  }

  static fromTokens(tokens: (Token | ASTNode)[]): GroupNode {
    const node = parse(tokens);
    return new GroupNode(node);
  }
}
class NegationNode extends ASTNodeCommon {
  type = 'negationnode';

  constructor(public child: NumberNode | GroupNode) {
    super();
  }

  get value(): number {
    return -(this.child.value as number);
  }
}

/**
 * Transforms number tokens into NumberNodes
 */
function parseNumbers(tokens: (Token | ASTNode)[]): (Token | ASTNode)[] {
  let i = 0;
  while (i < tokens.length) {
    const token = tokens[i];

    if (token.type !== 'number') {
      i++;
      continue;
    };

    // check if it is a decimal
    const nextToken = tokens[i + 1];
    const nextNextToken = tokens[i + 2];
    const nextTokenType = nextToken?.type;
    const nextNextTokenType = nextNextToken?.type;

    if (nextTokenType === 'decimal' && nextNextTokenType === 'number') {
      // it is a decimal number
      const numberNode = NumberNode.fromTokens([
        token as NumberToken,
        nextToken as DecimalToken,
        nextNextToken as NumberToken
      ]);
      tokens.splice(i, 3, numberNode);
      i += 2;
      continue;
    } else {
      // it is a regular number
      const numberNode = NumberNode.fromToken(token as NumberToken);
      tokens.splice(i, 1, numberNode);
    }
    i++;
  }

  return tokens;
}

/**
 * Matches highest level parenthesis and replaces them with GroupNodes.
 * Only the highest level parenthesis are required because GroupNode will
 * recursively parse the rest of the expression.
 */
function parseGroups(tokens: (Token | ASTNode)[]): (Token | ASTNode)[] {
  // match highest level parenthesis
  let i = 0;
  const parenthesisPairs: [number, number][] = [];
  const startParenthesis: number[] = [];
  while (i < tokens.length) {
    const token = tokens[i];

    if (token.type !== 'parenthesis') {
      i++;
      continue;
    };

    // it is a parenthesis
    if (token.value === '(') {
      startParenthesis.push(i);
    } else {
      const start = startParenthesis.pop();
      if (startParenthesis.length === 0) {
        if (start === undefined) {
          throw new Error('Invalid parenthesis');
        }
        parenthesisPairs.push([start, i]);
      }
    }
    i++;
  }

  // slice out parenthesis pairs and replace with GroupNode
  for (const [start, end] of parenthesisPairs) {
    const groupNode = GroupNode.fromTokens(tokens.slice(start + 1, end));
    tokens.splice(start, end - start + 1, groupNode);
    // update pairs after splice
    for (let i = 0; i < parenthesisPairs.length; i++) {
      const [start2, end2] = parenthesisPairs[i];
      parenthesisPairs[i] = [start2 - (end - start), end2 - (end - start)];
    }
  }

  return tokens;
}

function parseNegation(tokens: (Token | ASTNode)[]): (Token | ASTNode)[] {
  let i = 0;
  while (i < tokens.length) {
    const token = tokens[i];

    if (token.type !== 'operator') {
      i++;
      continue;
    };

    if (token.value === '-') {
      const prevToken = tokens[i - 1] as Token;
      if (!prevToken || isOperatorChar(prevToken.value)) {
        // it is a negation
        const child = tokens[i + 1] as NumberNode | GroupNode;
        const negationNode = new NegationNode(child);
        tokens.splice(i, 2, negationNode);
      }
    }
    i++;
  }

  return tokens;
}

function parseMultDiv(tokens: (Token | ASTNode)[]): (Token | ASTNode)[] {
  let i = 0;
  while (i < tokens.length) {
    const token = tokens[i];

    if (token.type !== 'operator') {
      i++;
      continue;
    };

    if (token.value === '*' || token.value === '/') {
      const left = tokens[i - 1] as ASTNode;
      const right = tokens[i + 1] as ASTNode;
      const operator = token.value as OperatorChars;
      const operatorNode = new OperatorNode(operator, left, right);
      tokens.splice(i - 1, 3, operatorNode);
      continue;
    }
    i++;
  }

  return tokens;
}

function parseAddSub(tokens: (Token | ASTNode)[]): (Token | ASTNode)[] {
  let i = 0;
  while (i < tokens.length) {
    const token = tokens[i];

    if (token.type !== 'operator') {
      i++;
      continue;
    };

    if (token.value === '+' || token.value === '-') {
      const left = tokens[i - 1] as ASTNode;
      const right = tokens[i + 1] as ASTNode;
      const operator = token.value as OperatorChars;
      const operatorNode = new OperatorNode(operator, left, right);
      tokens.splice(i - 1, 3, operatorNode);
      continue;
    }
    i++;
  }

  return tokens;
}

export function parse(tokens: (Token | ASTNode)[]): ASTNode {
  // array that we will save intermediate results in
  const transform = [...tokens];

  // first pass: parse groups (parenthesis)
  parseGroups(transform);

  // second pass: parse numbers and decimals
  parseNumbers(transform);

  // third pass: negation
  parseNegation(transform);

  // fourth pass: multiplication and division
  parseMultDiv(transform);

  // fifth pass: addition and subtraction
  parseAddSub(transform);

  console.log(JSON.stringify(transform[0], null, 2));
  return transform[0] as ASTNode;
}

export function calc(expression: string): number {
  // evaluate `expression` and return result
  return parse(tokenize(expression)).value;
}