{x}
blog image

Basic Calculator II

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 [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

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

 

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 231 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

Solution Explanation: Basic Calculator II

This problem requires evaluating a mathematical expression string containing integers and the four basic arithmetic operators (+, -, *, /). We cannot use built-in evaluation functions like eval(). The solution uses a stack-based approach to handle operator precedence implicitly.

Algorithm:

  1. Initialization: We maintain a stack (stk) to store numbers and a variable sign to keep track of the current operator (+, -, *, /). The initial sign is '+'. We also use a variable v to accumulate the current number being parsed.

  2. Iteration: The code iterates through the input string s.

    • If a digit is encountered, it's added to v to build the current number.
    • If a non-digit character (+, -, *, /) or the end of the string is reached:
      • The current number v is processed based on the current sign:
        • '+': v is pushed onto the stack.
        • '-': -v (the negation of v) is pushed onto the stack.
        • '*': The top element of the stack is popped, multiplied by v, and the result is pushed back onto the stack.
        • '/': Similar to multiplication, but division is performed. Integer division (truncation towards zero) is used.
      • The sign is updated to the newly encountered operator.
      • v is reset to 0 to start accumulating the next number.

  3. Final Calculation: After iterating through the entire string, the stack contains numbers that need to be added (or subtracted, depending on whether the numbers were initially positive or negative). The sum of the stack elements is calculated and returned as the final result.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the input string s. The algorithm iterates through the string once. The stack operations (push and pop) take constant time on average.

  • Space Complexity: O(n) in the worst case. The space used by the stack can grow up to the size of the input string if the expression contains many numbers. In best-case scenarios (e.g., a simple addition), the space used would be minimal.

Code Examples (with detailed comments):

The provided code solutions in Python, Java, C++, Go, and C# all implement the same algorithm, using different language syntax and data structures (stacks). They are functionally equivalent. The comments within the code enhance understanding. For instance, the Python solution highlights the use of a match statement for clarity. The Java solution shows the use of Deque for stack implementation, while C++ leverages the standard stack container. The Go solution provides a concise implementation of the algorithm, and the C# uses a struct to handle the operations more clearly. All illustrate the core logic of the stack-based approach effectively.