Basic Calculator hard

Problem Statement

Evaluate a given string expression representing a basic calculator. The expression contains digits, '+', '-', '(', ')', and spaces. The expression should be evaluated according to standard mathematical order of operations (parentheses first).

Example 1

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

Example 2

Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23

Steps

1. Stack-based Approach: We'll use a stack to handle operator precedence and parentheses. The stack will store both numbers and operators.

2. Iterate through the expression: Process the string character by character.

3. Number Handling: If a digit is encountered, build a number until a non-digit character is found.

4. Operator Handling: If an operator ('+', '-', '(', ')') is found:

   • For '+' and '-': Push the operator onto the stack.
   • For '(': Push it onto the stack.
   • For ')': Evaluate expressions within the parentheses by repeatedly popping operators and operands from the stack until a '(' is encountered. Then discard the '('.

5. Evaluation: After the iteration, evaluate the remaining operators and operands on the stack to get the final result.

Explanation

The core idea is to leverage a stack to manage the order of operations. Parentheses create nested sub-expressions. By using a stack, we can process these sub-expressions recursively (implicitly through the stack operations). When we hit a closing parenthesis, we evaluate everything within that parenthesis before continuing with the main expression. The algorithm efficiently handles both addition and subtraction while respecting operator precedence implied by parentheses.

Code

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int calculate(string s) {
    stack<long long> nums; // Use long long to handle potential integer overflow
    stack<char> ops;
    long long num = 0;
    char sign = '+'; // Initialize with '+' to handle leading numbers

    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        }
        if (!isdigit(c) && c != ' ' || i == s.length() - 1) { //Handle end of string as well
            if (sign == '+') {
                nums.push(num);
            } else if (sign == '-') {
                nums.push(-num);
            }
            num = 0;
            if (!ops.empty() && (c == '+' || c == '-')) {
                while (!ops.empty()) { //Handles precedence of + and -
                    char op = ops.top();
                    ops.pop();
                    long long num2 = nums.top(); nums.pop();
                    long long num1 = nums.top(); nums.pop();
                    nums.push(op == '+' ? num1 + num2 : num1 - num2);
                }
            }
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.top() != '(') {
                    char op = ops.top();
                    ops.pop();
                    long long num2 = nums.top(); nums.pop();
                    long long num1 = nums.top(); nums.pop();
                    nums.push(op == '+' ? num1 + num2 : num1 - num2);
                }
                ops.pop(); //Pop the '('
            }else if (c == '+' || c == '-') {
                ops.push(c);
            }
            sign = c;

        }
    }
    long long res = 0;
    while (!nums.empty()) {
        res += nums.top();
        nums.pop();
    }
    return res;
}

int main() {
    string s = "(1+(4+5+2)-3)+(6+8)";
    cout << calculate(s) << endl; // Output: 23
    return 0;
}

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, where n is the length of the input string. The stack could potentially store all the numbers and operators in the expression if it's deeply nested. In the average case, it would be less than O(n).