Basic Calculator II medium

Problem Statement

Evaluate a string expression representing a basic calculator with addition, subtraction, multiplication, and division operations. The expression consists of non-negative integers and the four operations. Spaces are allowed between numbers and operators. The division operator / should represent integer division.

Example 1

Input: s = "3+2*2" Output: 7 Explanation: 3 + 2 * 2 = 7

Example 2

Input: s = " 3/2 " Output: 1 Explanation: 3 / 2 = 1

Steps

1. Initialization: Initialize a stack stack to store operands and a variable result to accumulate the result. Initialize a variable sign to 1 (representing a positive number). We'll use sign to handle negative numbers implicitly.

2. Iteration: Iterate through the input string s.

   • Whitespace: Ignore whitespace characters.
   • Digit: If a digit is encountered, build a number by concatenating digits until a non-digit character is found. Convert the accumulated number string to an integer.
   • Operator:
     • If an operator + or - is found: Push the current result * sign onto the stack, update result to 0, and set sign to 1 if + or -1 if -.
     • If an operator * or / is found: Perform the operation (* or /) on the top element of the stack and the current number. Push the result back onto the stack. Then set result to 0 and sign to 1.

3. Final Calculation: After iterating through the string, push the result * sign onto the stack. Then, sum up all the elements in the stack to get the final result.

Explanation

The algorithm employs a stack and handles operator precedence implicitly. Multiplication and division have higher precedence because they are processed immediately when encountered. Addition and subtraction are handled by accumulating results in result and pushing it onto the stack when a + or - is encountered. The sign variable simplifies handling positive and negative numbers.

Code

def calculate(s: str) -> int:
    stack = []
    result = 0
    sign = 1  # 1 for positive, -1 for negative

    for i, c in enumerate(s):
        if c.isdigit():
            num = 0
            while i < len(s) and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            result += num * sign
            i -= 1  # Adjust index to avoid skipping the next character.

        elif c == '+':
            stack.append(result * sign)
            result = 0
            sign = 1
        elif c == '-':
            stack.append(result * sign)
            result = 0
            sign = -1
        elif c == '*':
            stack.append(result * sign)
            result = 0
            next_num = 0
            while i+1 < len(s) and s[i+1].isdigit():
                i += 1
                next_num = next_num * 10 + int(s[i])
            result = stack.pop() * next_num
            sign = 1
        elif c == '/':
            stack.append(result * sign)
            result = 0
            next_num = 0
            while i+1 < len(s) and s[i+1].isdigit():
                i += 1
                next_num = next_num * 10 + int(s[i])

            result = int(stack.pop() / next_num)
            sign = 1



        #ignore whitespace
        elif c == ' ':
            continue
    stack.append(result * sign)
    return sum(stack)

Complexity

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
• Space Complexity: O(n) in the worst case, where the stack might store all operands if the expression is a long chain of additions and subtractions. However, in practice, the stack size will usually be much smaller than n.