18.md

Day 18 - Operation Order - Part1 Part2

You're given math expressions as your input (only plus and multiplication signs, and parentheses). Your goal is to solve these math expressions.

What has changed is that + and * have the same precedence now. In regular math, 4 + 5 * 2 = 14. In this math, that expression equals 18.

More examples:

• 2 * 3 + (4 * 5) becomes 26.
• 5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 437.
• 5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 12240.
• ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 13632.

Evaluate the expression on each line of the homework; what is the sum of the resulting values?

Part Two

Now, plus signs (+) have a higher precedence than multiplication signs (*), unless overriden with parentheses. I.e., addition is evaluated before multiplication.

Same examples as before:

• 2 * 3 + (4 * 5) becomes 46.
• 5 + (8 * 3 + 9 + 3 * 4 * 3) becomes 1445.
• 5 * 9 * (7 * 3 * 3 + 9 * 3 + (8 + 6 * 4)) becomes 669060.
• ((2 + 4 * 9) * (6 + 9 * 8 + 6) + 6) + 2 + 4 * 2 becomes 23340.

What do you get if you add up the results of evaluating the homework problems using these new rules?

Solution

First, implement a function to get relevant tokens from a math expression.

/**
 * It returns the next parenthesis, or operator, or number. E.g.,
 * an expression of "4 + (23 * 3)" would return "4", "+", "(", "23", "*", "3",
 * ")".
 */
export function* tokens(expression: string): Generator<string> {
  assert(expression.length > 0);
  let remaining = expression;
  while (remaining.length > 0) {
    if (isParenthesis(remaining[0])) {
      const parenthesis = remaining[0];
      remaining = remaining.slice(1).trim();
      yield parenthesis;
    } else {
      let word = '';
      let i = 0;
      for (; i < remaining.length && remaining[i] !== ' '; i++) {
        const letter = remaining[i];
        if (isParenthesis(letter)) {
          break;
        }
        word += letter;
      }
      remaining = remaining.slice(i).trim();
      yield word;
    }
  }
}

For Part One, a single stack is needed. We keep pushing tokens into it until we encounter a word that is a number, and the last thing in the stack is an operator:

function solve(expression: string): number {
  const stack: string[] = [];
  for (const word of tokens(expression)) {
    stack.push(word);
    while (stack.length >= 2) {
      const popped = stack.pop()!;
      // if the current word is a number and the last thing was an operator,
      // take out the operator and the number before it, evaluate it, and put
      // the evaluated word back in.
      if (!isNaN(Number(popped)) && isOperator(last(stack))) {
        const op = stack.pop()!;
        const operand = stack.pop()!;
        stack.push(evaluate(popped, op, operand).toString());
      } else if (popped === ')') {
        // Something like (4 + 5) would've been converted into (9) before the
        // ')' was encountered, so we just take out the 9 outside of the
        // parenthesis. I.e., make "(9)" into "9".
        const resolvedNum = stack.pop()!;
        stack.pop()!; // opening parenthesis
        stack.push(resolvedNum);
      } else {
        // may be the first number, or an opening parenthesis, or an operator,
        // etc. Just push those back in and evaluate those later.
        stack.push(popped);
        break;
      }
    }
  }
  return assert(Number(stack.pop()), (n) => !isNaN(n) && stack.length === 0);
}

For Part Two, we first have to convert the expression into a postfix expression before evaluating it. The comments in the function go into good detail regarding it:

/**
 * It converts an expression like A * B + C + (D * E) to
 * ABC+*DE*+, and an expression like A * B * C * D to ABCD***.
 * Notice that the order of the numbers don't change at all. The rules are:
 */
function toPostfix(infixExpression: string): string[] {
  const output: string[] = [];
  const opStack: string[] = [];
  for (const word of tokens(infixExpression)) {
    if (!isNaN(Number(word))) {
      output.push(word);
    } else if (word === '+') {
      // this is the highest precedence operator, so you don't need to flush any
      // other operators out to the output.
      opStack.push(word);
    } else if (word === '*') {
      // Before putting this lower-precedence operator (*) into the operator
      // stack, take out any higher-precedence operator out (+) and put them
      // into the output stack. This is flushing.
      while (last(opStack) === '+') {
        output.push(opStack.pop()!);
      }
      // with the stack only consisting of '*' (or any plus signs that came
      // before opening parenthesis), push the '*' into the operator stack.
      opStack.push(word);
    } else if (word === '(') {
      // parenthesis go into the OPERATOR stack, since this will tell us when to
      // stop flushing operators when we encounter a closing parenthesis.
      opStack.push(word);
    } else if (word === ')') {
      // a closing parenthesis forces us to flush the operator stack until it
      // was opened.
      while (last(opStack) !== '(') {
        output.push(opStack.pop()!);
      }
      opStack.pop(); // remove the (
    } else {
      throw new Error(`Unknown word ${word}. Stack is ${output}.`);
    }
  }
  // If expression was A * B * C + D, output would equal "ABCD" and operator
  // stack would be ['*', '*', '+']. We need to flush all of those out to make
  // the output equal "ABCD+**".
  while (opStack.length > 0) {
    output.push(opStack.pop()!);
  }
  return output;
}

Finally, evaluating a postfix expression is straightforward:

function solve(postfixExpression: string[]): number {
  const stack: number[] = [];
  for (const word of postfixExpression) {
    if (isOperator(word)) {
      const op1 = assert(stack.pop());
      const op2 = assert(stack.pop());
      stack.push(evaluate(op1, word, op2));
    } else {
      stack.push(assert(Number(word), (n) => !isNaN(n)));
    }
  }
  return assert(stack.pop(), stack.length === 0);
}