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;
}

};

1class Solution {
2public:
3    int calculate(string s) {
4        int len = s.size(), sign = 1, result = 0;
5        stack<int> nums;
6        for (int i = 0; i < len; i++) {
7            if (isdigit(s[i])) {
8                int tmp = s[i] - '0';
9                while (i + 1 < len && isdigit(s[i + 1])) {
10                    tmp = tmp * 10 + (s[++i] - '0');
11                }
12                result += sign * tmp;
13            } else if (s[i] == '+') {
14                sign = 1;
15            } else if (s[i] == '-') {
16                sign = -1;
17            } else if (s[i] == '(') {
18                nums.push(result);
19                nums.push(sign);
20                result = 0;
21                sign = 1;
22            } else if (s[i] == ')') {
23                result = result * nums.top();
24                nums.pop();
25                result += nums.top();
26                nums.pop();
27            }
28        }
29        return result;
30    }
31};