Basic Calculator hard

Problem Statement

Evaluate a given expression represented as a string. The expression consists of non-negative integers, +, -, *, / operators, and parentheses. The expression should be evaluated according to the standard order of operations (PEMDAS/BODMAS). You may assume the given expression is always valid.

Example 1

Input: s = "1 + 1" Output: 2

Example 2

Input: s = " 2-1 + 2 " Output: 3

Steps and Explanation

This problem requires a recursive approach with a stack to handle operator precedence and parentheses. The solution uses a recursive helper function to evaluate expressions within parentheses. The main algorithm iterates through the input string:

1. Whitespace Handling: Ignore leading/trailing spaces and spaces between operators and operands.

2. Number Parsing: Accumulate digits to form numbers.

3. Operator Handling: When an operator (+, -, *, /) is encountered, perform the operation based on the current stack top and the parsed number. The order of operations is implicitly handled by the stack's LIFO nature. Multiplication and division have higher precedence, which is automatically handled because they are processed immediately upon encountering them.

4. Parentheses Handling: When an opening parenthesis '(' is encountered, recursively call the helper function to evaluate the subexpression within the parentheses. The result is pushed onto the stack.

5. Stack Operations: The stack holds intermediate results. For addition and subtraction, the number is simply pushed. For multiplication and division, the top of the stack is popped, the operation is performed, and the result is pushed back.

6. Final Result: After processing the entire string, the sum of all elements in the stack is the final result.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int Calculate(string s) {
        Stack<int> stack = new Stack<int>();
        int sign = 1; // 1 for +, -1 for -
        int num = 0;

        for (int i = 0; i < s.Length; i++) {
            char c = s[i];

            if (char.IsDigit(c)) {
                num = num * 10 + (c - '0');
            } else if (c == '+') {
                stack.Push(sign * num);
                num = 0;
                sign = 1;
            } else if (c == '-') {
                stack.Push(sign * num);
                num = 0;
                sign = -1;
            } else if (c == '(') {
                stack.Push(sign); // Save the current sign
                stack.Push(0); // Placeholder for subexpression result
                sign = 1;
                num = 0; // Reset number for the subexpression
            } else if (c == ')') {
                int subexpressionResult = calculateSubExpression(stack);
                stack.Push(sign * subexpressionResult); 
                num = 0;
                sign = 1;
            }
            
             else if (c == '*' || c == '/') {
                int prev = stack.Pop();
                int result;
                if (c == '*') result = prev * num;
                else result = prev / num;

                stack.Push(result);
                num = 0;
             }
        }
        stack.Push(sign * num); // Handle the last number

        int result1 = 0;
        while(stack.Count > 0) {
            result1 += stack.Pop();
        }

        return result1;
    }

    private int calculateSubExpression(Stack<int> stack) {
        int result = 0;
        int sign = stack.Pop(); // Retrieve the sign before the parenthesis
        while (stack.Count > 0 && stack.Peek() != 0) {  // 0 is a placeholder
            result += stack.Pop();
        }
        stack.Pop(); //Remove the placeholder 0
        return result * sign;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once. The recursive call for parentheses processing doesn't increase the overall time complexity beyond linear because each parenthesis pair is processed only once.
• Space Complexity: O(n) in the worst case, due to the stack. The stack's size can grow proportionally to the depth of nested parentheses in the input string.