The Multiplication and Division Conundrum

So, you've mastered addition, subtraction, and those tricky parentheses. Feeling confident?

Now, let's up the ante with multiplication and division. This is often the follow-up question in interviews, and it adds an extra layer of complexity. Why? Because multiplication and division have higher precedence than addition and subtraction, and they introduce non-linear relationships between the numbers.

The Fundamental Question: Why Stacks?

The stack is a lifeline in this problem for one primary reason: it provides a way to handle different priorities of operations without needing to backtrack. Think of it as a holding area or a waiting room where numbers and operations can wait their turn to be processed in the correct sequence.

Why Does a Stack Work?

A stack works on a last-in, first-out (LIFO) principle. It allows us to temporarily "park" elements that we'll need soon but not immediately. In the case of multiplication and division, this "parking" facility becomes invaluable. It enables us to first collect the operands and then perform the operation when the time is right.

Mental Model with Example: "4 * 3 + 2"

Let's take an example expression: 4 * 3 + 2. There's no parentheses, so it's easier to follow. We'll use Python for this example.

Here's a step-by-step breakdown:

1. Initialization: We initialize num to 0, stack to an empty list, and sign to +.

1let [num, stack, sign] = [0, [], "+"];

2. First Iteration (4):

   • We encounter 4, so num becomes 4.

3. Second Iteration (*):

   • We hit the *. At this point, the previous sign was +, so we push 4 onto stack.
   • We update sign to *.

4. Third Iteration (3):

   • We encounter 3, so num becomes 3.

5. Fourth Iteration (+):

   • We hit the +. The last sign was *, so we pop 4 from stack and push 4 * 3 = 12.
   • We update sign to +.

6. Fifth Iteration (2):

   • We encounter 2, so num becomes 2.

7. End of String:

   • The last sign is +, so we push 2 onto stack.

8. Final Calculation:

   • We sum the stack [12, 2], which results in 14.

xxxxxxxxxx

console.log(calculator("4*3+2"))

function calculator(s) {

    let [num, stack, sign] = [0, [], "+"]

​

    for (let i = 0; i < s.length; i++) {

        // Check if it's a number

        // If there's a previous `num` (num is not 0),

        // it's multi-digit (ex. 13), so we extend it

        // while processing `3`

        if (!isNaN(s[i])) {

            num = num * 10 + parseInt(s[i])

        }   

        if (["+", "-", "*", "/"].includes(s[i]) || i === s.length - 1) {

            console.log(i, s[i])

            if (sign == "+") {

                stack.push(num);

            } else if (sign == "-") {

                stack.push(-num);

            } else if (sign == "*") {

                // Our multiplication step: the stack.pop()

                // will provide the last number we encountered.

                stack.push(stack.pop() * num)                

            } else {

                // Division

                stack.push(parseInt(stack.pop() / num))

            }

            num = 0;

            sign = s[i];

        }

    }