algoadvance

Leetcode 227. Basic Calculator II

Problem Statement

The problem is “227. Basic Calculator II” from LeetCode. The task is to implement a basic calculator to evaluate a simple expression string.

The expression string contains the following non-negative integers and operators +, -, *, /. The expression string is guaranteed to be valid and does not contain any leading or trailing spaces. Each integer in the string is non-negative and always less than 2^31. The return value should be an integer.

Additional Rules:

  1. You should not use the eval function in Python.
  2. You must handle multiple digit numbers and follow the standard order of operations (i.e., * and / before + and -).
  3. You must handle spaces between characters and numbers.

Here’s an example:

Clarifying Questions

  1. Question: Should we handle negative numbers in the input?
    • Clarification: No, all numbers are non-negative.
  2. Question: Should we consider floating-point division or integer division?
    • Clarification: Integer division, as it involves only non-negative integers.
  3. Question: Can we assume that the input string is always valid as per the problem statement?
    • Clarification: Yes, the input string is always valid.

Strategy

  1. Initialize Variables:
    • Use a stack to handle the intermediate results.
    • Use a currentNumber to keep track of multi-digit numbers.
  2. Scan the String:
    • Traverse the string character by character.
    • If the character is a digit, update currentNumber.
    • If the character is an operator, push the previous currentNumber based on the last operator to the stack, then update the operator.
    • If it’s the end of the string, do the same as above.
  3. Maintain the Order of Operations:
    • For + and -: Push the number directly to the stack.
    • For * and /: Perform immediate operations with the top of the stack.
  4. Final Calculation:
    • Sum up all the numbers left in the stack to get the result.

Code

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

class Solution {
public:
    int calculate(std::string s) {
        int n = s.size();
        std::stack<int> stk;
        char lastOperator = '+';
        int currentNumber = 0;

        for (int i = 0; i < n; ++i) {
            char ch = s[i];
            if (isdigit(ch)) {
                currentNumber = currentNumber * 10 + (ch - '0');
            }
            if ((!isdigit(ch) && !isspace(ch)) || i == n - 1) {
                if (lastOperator == '+') {
                    stk.push(currentNumber);
                } else if (lastOperator == '-') {
                    stk.push(-currentNumber);
                } else if (lastOperator == '*') {
                    int top = stk.top();
                    stk.pop();
                    stk.push(top * currentNumber);
                } else if (lastOperator == '/') {
                    int top = stk.top();
                    stk.pop();
                    stk.push(top / currentNumber);
                }
                lastOperator = ch;
                currentNumber = 0;
            }
        }

        int result = 0;
        while (!stk.empty()) {
            result += stk.top();
            stk.pop();
        }

        return result;
    }
};

int main() {
    Solution sol;
    std::string input = "3+2*2";
    int result = sol.calculate(input);
    std::cout << "Result: " << result << std::endl; // Output: 7

    return 0;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI