Basic Calculator Ii - Leetcode Solution

Problem Statement:

Given a string s which represents an expression, evaluate this expression and return its value.

The expression is composed of several terms separated by the + or - operator. Each term is either an integer or a variable.

To evaluate the expression, replace each variable with its integer value and perform the specified arithmetic operation.

The expression contains only lowercase English letters, +, -, *, / operators, digits, and whitespace ' '.

Example 1:

Input: s = "3+2*2" Output: 7

Example 2:

Input: s = " 3/2 " Output: 1

Example 3:

Input: s = " 3+5 / 2 " Output: 5

Solution:

To solve this problem, we can use the concept of a stack. We can store the operands in the stack and keep track of the previous operator.

Step 1: Initialize the stack and current operand to 0 and the previous operator to '+'

Step 2: Remove all the whitespace characters from the string s.

Step 3: Loop through the string s and perform the following operations for each character:

• If the character is a digit, append it to the current operand.
• If the character is an operator (+, -, *, /), perform the following operations:
• Evaluate the previous operation (current operand and previous operator) and push the result to the stack.
• Update the current operand to 0 and previous operator to the current operator.
• If the character is a space, skip it.
• If the character is the last character of the string, evaluate the final operation (current operand and previous operator) and push the result to the stack.

Step 4: Calculate the final result by adding all the elements in the stack.

Code:

class Solution { public: int calculate(string s) { stack<int> st; char op = '+'; int operand = 0;

    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            operand = (operand * 10) + (c - '0');
        }
        if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {
            if (op == '+') {
                st.push(operand);
            } else if (op == '-') {
                st.push(-operand);
            } else if (op == '*') {
                int temp = st.top() * operand;
                st.pop();
                st.push(temp);
            } else if (op == '/') {
                int temp = st.top() / operand;
                st.pop();
                st.push(temp);
            }
            
            operand = 0;
            op = c;
        }
    }
    
    int result = 0;
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    
    return result;
}

};

1