Evaluates an expression in Reverse Polish Notation

ReversePolishNotationInterpreter.ts

/**
 * Evaluates an expression in Reverse Polish Notation.
 *
 * @param {string} expression - The input expression.
 * @returns {number} The result of the RPN expression.
*/

// This script parses the expression into a tree and then evaluates, should be something like O(n) because iterates once on the parsing and once in the evaluating

type Operator = {op: string, left: Operator | number, right: Operator | number};

const operators: Record<string, (x: number, y: number) => number> = {
  '+': (x: number, y: number) => y + x,
  '-': (x: number, y: number) => y - x,
  '*': (x: number, y: number) => y * x,
  '/': (x: number, y: number) => y / x,
};

const evaluate = (tree: Operator | number): number => {
  if(typeof tree === 'number') return tree;
  
  return operators[tree.op](evaluate(tree.left), evaluate(tree.right))
};

const parse = (tokens: string[]): Operator | number => {
  const token = tokens.pop();
  
  if(!token) return 0;
  
  if(!Object.keys(operators).includes(token)) return Number(token);
  
  return {op: token, left: parse(tokens), right: parse(tokens)};
}

const calculate = (expression: string): number => {
  const stack = expression.split(' ')
  
  return evaluate(parse(stack));
};

export { calculate };