Evaluate an Expression

Evaluate an arithmetic expression written in Reverse Polish Notation and Standard Notation. See the following expressions that yields the same result.

Standard Notation: 7 + 3 * 4 - 5

Reverse Polish Notation: 3 4 * 7 + 5 -

Reverse Polish Notation (Postfix)

Evaluate an arithmetic expression in Reverse Polish Notation.

The idea is to iterate the array from left to right and push numbers as operands into a stack. There should always be at least two operands in the stack whenever an operator is encountered. The operator indicates the type of operation that should be applied to the top two operands. To apply an operation, two operands are removed from the stack, and the result is pushed back into the stack as a new operand for future calculation. After processing the given expression, the operands stack should be reduced to a single number representing the solution.

const eval = (arr) => {
  const operands = [];

  for (let i = 0; i < arr.length; i++) {
    let c = arr[i];
    if (!isNaN(c)) {
      operands.push(parseInt(c));
      continue;
    }

    let op1 = operands.pop();
    let op2 = operands.pop();
    let subRes = 0;
    if (c === '*') 
      subRes = op1 * op2;
    if (c === '/')
      subRes = op1 / op2;
    if (c === '+') 
      subRes = op1 + op2; 
    if (c === '-')
      subRes = op1 - op2;

    operands.push(subRes);
  }

  return operands.pop();
}

Standard Notation (Infix)

Evaluate an arithmetic expression in Standard Notation.

One of the challenges in solving this problem is respecting the order of operations, which is multiplication, division, addition, and subtraction. The intuition is to first resolve all multiplication and division on the first pass. The second pass can be processed from left to right. Similar to the approach for Reverse Polish Notation, a stack can be used to store the operands or the products and quotients from the first pass. This way, the stack will only contain operands that need to be summed up at the end.

const eval = (s) => {
  const operands = [];
  let curSign = '+';
  let cur = 0;

  for (let i = 0; i < s.length; i++) {
    let c = s[i];
    if (!isNaN(c))
      cur = cur * 10 + parseInt(c);
    if (isNaN(c) || i = s.length - 1) {
      if (c === '*') 
        operands.push(operands.pop() * cur);
      if (c === '/')
        operands.push(operands.pop() / cur);
      if (c === '+') 
        operands.push(cur); 
      if (c === '-')
        operands.push(-cur);
      curSign = c;
      cur = 0;
    }
  }

  return operands.reduce((acc, v) => acc + v);
}

The time complexity for both problems is O(n) because we need to do processing for each element of the array or string. The space complexity for both problem is O(n) in the case where the operands stack contains as operands as the expression.