Basic Calculator II medium

Problem Statement

Evaluate a given string expression s that contains numbers and the operators '+', '-', '*', and '/'. The expression should be evaluated according to the standard order of operations (multiplication and division have higher precedence than addition and subtraction). Spaces may appear in the expression.

Example 1

Input: s = "3+2*2" Output: 7 Explanation: This should be evaluated as 3 + (2 * 2) = 7

Example 2

Input: s = " 3/2 " Output: 1 Explanation: This should be evaluated as 3 / 2 = 1 (integer division).

Steps

1. Tokenization: Split the input string into tokens (numbers and operators). We'll use a helper function for this.
2. Two-Stack Evaluation: Use two stacks: one for numbers (numStack) and one for operators (opStack).
3. Iterate through Tokens: Process each token:
   • If it's a number, push it onto numStack.
   • If it's an operator:
     • While opStack is not empty and the precedence of the current operator is less than or equal to the precedence of the top operator in opStack, perform the operation using the top two numbers from numStack.
     • Push the current operator onto opStack.
4. Final Calculation: After processing all tokens, perform any remaining operations in opStack.

Explanation

The algorithm utilizes the principle of a two-stack evaluation for arithmetic expressions. The precedence of operators is implicitly handled by the while loop in step 3. Multiplication and division are handled before addition and subtraction because they have higher precedence. Integer division is naturally handled by C++'s division operator.

Code

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

using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

int calculate(int a, int b, char op) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    if (op == '/') return a / b; // Integer division
    return 0; 
}

int calculate(string s) {
    stack<int> numStack;
    stack<char> opStack;
    stringstream ss(s);
    string token;

    while (ss >> token) {
        if (isdigit(token[0])) {
            numStack.push(stoi(token));
        } else {
            while (!opStack.empty() && precedence(token[0]) <= precedence(opStack.top())) {
                int b = numStack.top(); numStack.pop();
                int a = numStack.top(); numStack.pop();
                char op = opStack.top(); opStack.pop();
                numStack.push(calculate(a, b, op));
            }
            opStack.push(token[0]);
        }
    }

    while (!opStack.empty()) {
        int b = numStack.top(); numStack.pop();
        int a = numStack.top(); numStack.pop();
        char op = opStack.top(); opStack.pop();
        numStack.push(calculate(a, b, op));
    }

    return numStack.top();
}

int main() {
    string s1 = "3+2*2";
    string s2 = " 3/2 ";
    string s3 = " 3+5 / 2 "; //test case added
    cout << calculate(s1) << endl; // Output: 7
    cout << calculate(s2) << endl; // Output: 1
    cout << calculate(s3) << endl; //Output: 5

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once for tokenization and once for evaluation.
• Space Complexity: O(n) in the worst case, due to the stacks which could potentially store all the numbers and operators. In practice, the space used is often much less than n.