Basic Calculator II

 

Problem Description: Given a string s representing a valid expression containing only non-negative integers, the four basic arithmetic operators (+, -, *, and /), and empty spaces, evaluate the expression and return the result.

Example:

python
# Example usage of the function
s = "3+2*2"
print(calculate(s))  # Output: 7

1. Clarify the problem: Before starting, let's ask some clarifying questions to ensure we fully understand the problem requirements:

  • Are parentheses allowed in the expression?
  • Is the input always a valid expression, or should we handle invalid expressions as well?

2. Analyze the problem: Let's break down the problem to better understand its components:

  • Input: A string s representing a valid expression.
  • Output: The evaluated result of the expression.
  • Constraints: The input expression contains only non-negative integers, the four basic arithmetic operators (+, -, *, and /), and empty spaces.

3. Design an algorithm: To solve this problem, we can use a stack to keep track of the intermediate results while parsing the expression. We iterate through the characters in the expression string and perform the corresponding operations based on the encountered operators.

Here's an outline of the algorithm:

  1. Initialize a stack to store the intermediate results.
  2. Initialize variables num and operator to track the current number and operator.
  3. Iterate through each character in the expression string s.
  4. If the character is a digit, update the current number by multiplying it by 10 and adding the numeric value of the character.
  5. If the character is an operator or the last character of the expression, perform the previous operation based on the last operator encountered.
    • If the last operator was +, push num onto the stack.
    • If the last operator was -, push -num onto the stack.
    • If the last operator was *, multiply the top element of the stack by num and update the stack.
    • If the last operator was /, divide the top element of the stack by num and update the stack.
    • Set num to 0 and update the operator to the current character.
  7. After iterating through all characters, sum up the elements in the stack to get the final result.

4. Explain your approach: We will use a stack to keep track of the intermediate results while parsing the expression. By iterating through the characters in the expression and performing the corresponding operations based on the encountered operators, we can evaluate the expression and obtain the final result.

5. Write clean and readable code:

Here's an implementation of the algorithm in Python:

python
def calculate(s):
    stack = []
    num = 0
    operator = "+"

    for i in range(len(s)):
        if s[i].isdigit():
            num = num * 10 + int(s[i])

        if (not s[i].isdigit() and s[i] != " ") or i == len(s) - 1:
            if operator == "+":
                stack.append(num)
            elif operator == "-":
                stack.append(-num)
            elif operator == "*":
                stack.append(stack.pop() * num)
            elif operator == "/":
                stack.append(int(stack.pop() / num))

            num = 0
            operator = s[i]

    return sum(stack)

6. Test your code: Now, let's test the code with the example usage and some additional test cases:

python
# Example test case
s = "3+2*2"
print(calculate(s))  # Output: 7

# Additional test cases
s = " 3/2 "
print(calculate(s))  # Output: 1

s = " 3+5 / 2 "
print(calculate(s))  # Output: 5

s = "14-3/2"
print(calculate(s))  # Output: 13

7. Optimize if necessary: The given solution has a time complexity of O(n), where n is the length of the input expression string. This is because we iterate through each character in the string once. This is already an optimal solution for this problem.

8. Handle error cases: The given code assumes that the input expression is valid and adheres to the given constraints. However, it doesn't handle cases where the expression is invalid. Error handling strategies can be discussed with the interviewer.

9. Discuss complexity analysis:

  • Time complexity: The algorithm has a time complexity of O(n), where n is the length of the input expression string. This is because we iterate through each character in the string once.
  • Space complexity: The space complexity is O(n) in the worst case, where n is the length of the input expression string. This is because the stack can store at most n/2 elements if all the digits in the expression are single-digit numbers.
Next Post Previous Post