algoadvance

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

Note:

Example 1:

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

Example 2:

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

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

Clarifying Questions

  1. Can the expression have negative numbers?
    • No, the prompt suggests the given expression is always valid and involves only non-negative numbers.
  2. Are there any parentheses in the expression?
    • No, the expression will not contain any parentheses.
  3. Will there be any spaces in the input string?
    • Yes, spaces might be present in the input string, and they should be ignored.
  4. What operations are supported?
    • The operations supported are addition (+), subtraction (-), multiplication (*), and division (/).

Strategy

To evaluate the expression, we will use the following approach:

  1. Initialize a stack to keep track of numbers.
  2. We need to maintain a current number and an operation.
  3. Iterate over each character of the string:
    • If the character is a digit, construct the full number.
    • If the character is an operator or the end of the string is reached:
      • Apply the current number to the stack based on the last seen operation (+, -, *, /).
      • Update the operation to the current character and reset the current number.
  4. After processing all characters, sum up the numbers in the stack to get the result.

Code

def calculate(s: str) -> int:
    if not s:
        return 0
    
    stack = []
    current_number = 0
    operation = '+'
    length = len(s)
    
    for i in range(length):
        char = s[i]
        
        if char.isdigit():
            current_number = current_number * 10 + int(char)
        
        # if the char is not a digit and is not a space, or it is the end of the string
        if (not char.isdigit() and char != ' ') or i == length - 1:
            if operation == '+':
                stack.append(current_number)
            elif operation == '-':
                stack.append(-current_number)
            elif operation == '*':
                stack[-1] = stack[-1] * current_number
            elif operation == '/':
                stack[-1] = int(stack[-1] / current_number)
            
            operation = char
            current_number = 0
    
    return sum(stack)

# Examples
print(calculate("3+2*2"))   # Output: 7
print(calculate(" 3/2 "))   # Output: 1
print(calculate(" 3+5 / 2 ")) # Output: 5

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the string. This is because we are iterating over the string once and performing constant-time operations within the loop.

Space Complexity

The space complexity of this solution is (O(n)) due to the stack, which in the worst case, can store up to all the numbers from the expression.

Try our interview co-pilot at AlgoAdvance.com