Multiplication and Division with Parentheses

We've been focusing on adding and subtracting, but now let's tackle multiplication and division when they're tossed into the mix with parentheses. The challenge is to keep processing our string expression from left to right while still honoring the parentheses and the order of operations. So, let's rethink our approach a bit.

The "Aha" Moment: View Multiplication as Extended Addition

Imagine you're staring at the expression "4*(3+2)". We naturally get drawn to the parentheses and think about tackling that first. But what if we reframe it? Instead of seeing it as "4 multiplies (3+2)", think of it as "0 add (4 * 5)".

Why the Reframe Works

This reframe works because it turns a nested operation into a linear one. The operation that seemed nested within the parentheses is now another operation in the queue. And because we've flattened it out, we can handle it with a left-to-right pass through the string, just like we did with simpler expressions.

Leveraging the Stack for this Reframe

The stack data structure comes to our rescue here. As we go through the string, we keep track of numbers and operations, as usual. But now, when we encounter a parenthesis, we use the stack to "remember" the operation that was happening right before we dove into the parenthesis. This enables us to "flatten" the nested operation into a linear one.

1if ch == "(":
2    # We can still leverage the stack that we're using
3    # by recreating the parentheses expression within the stack
4    stack.append(sign)
5    stack.append('(')
6    # Reset to plus to add the parentheses expression results
7    sign = '+'

Unpacking the Parentheses

When we exit the parenthesis, we unpack the operations and numbers we've stored and perform the calculation. This way, the result of "3+2" in "4*(3+2)" becomes just another number in our queue of operations.

1if ch == ')':
2    # Complete our parentheses expression 
3    num, item = 0, stack.pop()
4    while item != '(':
5        num += item
6        item = stack.pop()
7    sign = stack.pop()

Python: Implementing the Strategy

In Python, let's walk through the code step-by-step:

1. Initialize Variables: We start by initializing our variables. The variable num will hold the number we're currently parsing, stack will hold our numbers and signs, and sign will hold the current operation (addition by default).

   PYTHON

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

2. Loop Through the String: We'll loop through each character in the string. For the last iteration, we append a '+' to ensure we process all numbers.

   PYTHON

   1for i, ch in enumerate(s + '+'):

3. Detect Numbers: If the character is numeric, we build the current number.

   PYTHON

   1if ch.isnumeric():
   2    num = num * 10 + int(ch)

4. Handling Parentheses: When we encounter an open parenthesis, we push the current sign and parenthesis to the stack, and then reset sign to '+'.

   PYTHON

   1if ch == "(":
   2    stack.append(sign)
   3    stack.append('(')
   4    sign = '+'

5. Handle Operations and Close Parenthesis: When we encounter any operator or close parenthesis, we perform the respective operation.

   PYTHON

   1if ch in "+-*/)" or i == len(s) - 1:
   2    if sign == "+":
   3        stack.append(num)
   4    elif sign == "-":
   5        stack.append(-num)
   6    elif sign == "*":
   7        stack.append(stack.pop() * num)
   8    elif sign == '/':
   9        stack.append(int(stack.pop() / num))

6. Close Parenthesis Logic: If we encounter a close parenthesis, we process the numbers within the parenthesis and sum them up.

   PYTHON

   1if ch == ')':
   2    num, item = 0, stack.pop()
   3    while item != '(':
   4        num += item
   5        item = stack.pop()
   6    sign = stack.pop()

7. Reset for Next Loop: Finally, we reset num and sign for the next iteration.

   PYTHON

   1else:
   2    num = 0
   3    sign = ch

8. Sum it Up: At the end, our stack will contain the numbers we need to sum to get the answer.

   PYTHON

   1return sum(stack)

9. Test the Function: We'll use an example to test our function.

   PYTHON

   1print(calculator("4*(3+2)"))  # Output should be 20

xxxxxxxxxx

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

function calculator(s) {

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

    s += '+';

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

        const ch = s[i];

        if (!isNaN(ch)) {

            num = num * 10 + parseInt(ch);

        }

        if (ch === "(") {

            stack.push(sign);

            stack.push('(');

            sign = '+';

        }

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

            if (sign === "+") {

                stack.push(num);

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

                stack.push(-num);

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

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

            } else {

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

            }

            if (ch === ')') {

                num = 0;

                let item = stack.pop();

                while (item !== '(') {

                    num += item;

                    item = stack.pop();