Basic Calculator II medium

Problem Statement

Evaluate a string expression representing a basic arithmetic expression, where the operators are +, -, *, and /. The expression consists of non-negative integers and the aforementioned operators. Assume that the given expression is always valid and the integer values will be in the range [0, 2³¹ - 1]. The expression does not contain parentheses. Division between two integers should truncate toward zero.

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. Integer division truncates the decimal part.

Steps

1. Initialization: Initialize stack to store numbers and result to store the accumulated result. Also, initialize prevOperand to store the last calculated number and operator to store the last used operator.
2. Iteration: Iterate through the input string s, character by character.
3. Space Handling: Skip whitespace characters.
4. Number Handling: If a digit is encountered, build the current number by concatenating digits until a non-digit character is found. Convert the built number string to an integer.
5. Operator Handling: If an operator (+, -, *, /) is encountered:
   • Perform the calculation based on the precedence of the operators. Multiplication and division have higher precedence than addition and subtraction.
   • If the current operator has higher or equal precedence to the previous operator, perform the calculation using prevOperand and the current number. Update prevOperand and operator.
   • Otherwise (current operator has lower precedence), push the prevOperand and the operator onto the stack. Then, update prevOperand and operator.
6. Post-Iteration Calculation: After the iteration, process any remaining values in the stack and incorporate prevOperand.
7. Return Result: Return the final accumulated result.

Explanation

The solution employs a stack to handle operator precedence. Multiplication and division are handled immediately when encountered because they have higher precedence. Addition and subtraction are handled later, either after the iteration is completed or when a higher-precedence operator is met. This approach avoids the need for explicit parentheses handling in the given problem's constraints.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int Calculate(string s) {
        Stack<int> stack = new Stack<int>();
        int result = 0;
        int prevOperand = 0;
        char operatorSign = '+';

        for (int i = 0; i < s.Length; i++) {
            char currentChar = s[i];
            if (char.IsDigit(currentChar)) {
                int currentNumber = 0;
                while (i < s.Length && char.IsDigit(s[i])) {
                    currentNumber = currentNumber * 10 + (s[i] - '0');
                    i++;
                }
                i--; // Adjust index to account for the extra increment

                if (operatorSign == '+') {
                    prevOperand = currentNumber;
                } else if (operatorSign == '-') {
                    prevOperand = -currentNumber;
                } else if (operatorSign == '*') {
                    prevOperand = prevOperand * currentNumber;
                } else if (operatorSign == '/') {
                    prevOperand = prevOperand / currentNumber;
                }
            } else if (currentChar != ' ') {
                if (operatorSign == '+')
                {
                    stack.Push(prevOperand);
                }
                else if (operatorSign == '-')
                {
                    stack.Push(prevOperand);
                }
                operatorSign = currentChar;
            }

        }
        while(stack.Count > 0){
            result += stack.Pop();
        }
        result += prevOperand;
        return result;
    }
}

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, if all the operators are '+' or '-'. The stack can grow to the size of the number of operators. In the best case (e.g., all multiplications), the space complexity is O(1).