Arithmetic Expression Parser

// Arithmetic expression parser: tokens, shunting-yard and RPN evaluation.
type Token =
  | { type: "number"; value: number }
  | { type: "operator"; value: string }
  | { type: "paren"; value: "(" | ")" };

const PRECEDENCE: Record<string, number> = {
  "+": 1, "-": 1, "*": 2, "/": 2, "%": 2, "^": 3, "u-": 4, "u+": 4,
};

const RIGHT_ASSOCIATIVE = new Set(["^", "u-", "u+"]);

export function tokenizeExpression(input: string): Token[] {
  const tokens: Token[] = [];
  let index = 0;
  while (index < input.length) {
    const char = input[index]!;
    if (/\s/.test(char)) {
      index += 1;
      continue;
    }
    if (/[0-9.]/.test(char)) {
      const match = /^\d*\.?\d+(?:[eE][+-]?\d+)?/.exec(input.slice(index));
      if (!match) throw new SyntaxError("invalid number at position " + index);
      tokens.push({ type: "number", value: Number(match[0]) });
      index += match[0].length;
      continue;
    }
    if ("+-*/%^".includes(char)) {
      tokens.push({ type: "operator", value: char });
      index += 1;
      continue;
    }
    if (char === "(" || char === ")") {
      tokens.push({ type: "paren", value: char });
      index += 1;
      continue;
    }
    throw new SyntaxError("unexpected character '" + char + "'");
  }
  return tokens;
}

function evaluateRpn(tokens: Token[]): number {
  const stack: number[] = [];
  for (const token of tokens) {
    if (token.type === "number") {
      stack.push(token.value);
      continue;
    }
    const operator = token.value;
    if (operator === "u-" || operator === "u+") {
      const operand = stack.pop();
      if (operand === undefined) throw new SyntaxError("missing unary operand");
      stack.push(operator === "u-" ? -operand : operand);
      continue;
    }
    const right = stack.pop();
    const left = stack.pop();
    if (left === undefined || right === undefined) throw new SyntaxError("missing operand");
    const value = operator === "+" ? left + right
      : operator === "-" ? left - right
      : operator === "*" ? left * right
      : operator === "/" ? left / right
      : operator === "%" ? left % right
      : left ** right;
    stack.push(value);
  }
  if (stack.length !== 1) throw new SyntaxError("invalid expression");
  return stack[0]!;
}

export function evaluateExpression(expression: string): number {
  const output: Token[] = [];
  const operators: string[] = [];
  const tokens = tokenizeExpression(expression);
  let previous: Token | undefined;
  for (const token of tokens) {
    if (token.type === "number") {
      output.push(token);
    } else if (token.type === "operator") {
      const unary = (token.value === "-" || token.value === "+")
        && (!previous || previous.type === "operator" || (previous.type === "paren" && previous.value === "("));
      const operator = unary ? "u" + token.value : token.value;
      while (operators.length > 0) {
        const top = operators[operators.length - 1]!;
        if (top === "(") break;
        const higher = PRECEDENCE[top]! > PRECEDENCE[operator]!
          || (PRECEDENCE[top] === PRECEDENCE[operator] && !RIGHT_ASSOCIATIVE.has(operator));
        if (!higher) break;
        output.push({ type: "operator", value: operators.pop()! });
      }
      operators.push(operator);
    } else if (token.value === "(") {
      operators.push("(");
    } else {
      while (operators.length > 0 && operators[operators.length - 1] !== "(") {
        output.push({ type: "operator", value: operators.pop()! });
      }
      if (operators.length === 0) throw new SyntaxError("unbalanced parentheses");
      operators.pop();
    }
    previous = token;
  }
  while (operators.length > 0) {
    const operator = operators.pop()!;
    if (operator === "(") throw new SyntaxError("unbalanced parentheses");
    output.push({ type: "operator", value: operator });
  }
  return evaluateRpn(output);
}