Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Basic Calculator II

Try it yourself
MediumProblemExternal link

Description

You get a string s holding an arithmetic expression: non-negative integers joined by +, -, * and /, with any number of spaces between them. Return its value.

The usual rules apply. * and / are done before + and -, and operators at the same level go left to right. Division between integers truncates toward zero, so 7 / 2 is 3.

The expression is always valid, and every value along the way fits in a 32-bit signed integer. You may not use a built-in function that evaluates a string as code, such as eval().

Examples

Example 1

Input: s = "3+2*2"

Output: 7

Explanation: Multiply first: 2 * 2 = 4, then 3 + 4 = 7.

Example 2

Input: s = " 3/2 "

Output: 1

Explanation: 3 / 2 is 1.5, truncated toward zero to 1.

Example 3

Input: s = " 3+5 / 2 "

Output: 5

Explanation: Divide first: 5 / 2 = 2, then 3 + 2 = 5.

Example 4

Input: s = "14-3*4/5"

Output: 12

Explanation: Multiply and divide left to right: 3 * 4 = 12, then 12 / 5 = 2, truncated. Then 14 - 2 = 12.

Constraints

  • 1 ≤ s.length ≤ 3 × 10^5
  • s consists of integers and operators (+, -, *, /) separated by some number of spaces
  • s represents a valid expression
  • All the integers in the expression are non-negative integers in the range [0, 2^31 - 1]
  • The answer is guaranteed to fit in a 32-bit integer

Editorial

Brute Force

Intuition

Do it the way you would on paper. Split the string into numbers and operators. While a * or / is left, apply the first one: its two numbers and the operator become one number. Then do the same with + and -. The one number left is the answer.

Going left to right within a level matters: 12 / 2 * 3 is 18, and doing the * first would give 2.

Step-by-Step Explanation

Let's trace s = "14-3*4/5":

  1. Split the string into tokens: 14 - 3 * 4 / 5, 4 numbers and 3 operators.
  2. The first * or / is 3 * 4, which is 12. Now 14 - 12 / 5.
  3. The first * or / is 12 / 5, which is 2.4, truncated to 2. Now 14 - 2.
  4. No * or / is left, so now + and -. The first one is 14 - 2, which is 12. Only 12 is left: the answer.

Apply One Operator at a Time — The tokens about to combine are amber; the number they become is green.

Algorithm

  1. Read s once, collecting the numbers in nums and the operators in ops, so that ops[k] sits between nums[k] and nums[k + 1].
  2. For the level * /, then the level + -: walk k along ops. If ops[k] is in the level, replace nums[k] with nums[k] ops[k] nums[k + 1] and delete nums[k + 1] and ops[k]; the next operator has moved into place k, so check k again. Otherwise move on.
  3. Return nums[0].

Code

class Solution {
public:
    int calculate(string s) {
        vector<long long> nums;                  // ops[k] sits between nums[k] and nums[k + 1]
        vector<char> ops;
        long long num = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (isdigit(c)) num = num * 10 + (c - '0');
            bool isOp = c == '+' || c == '-' || c == '*' || c == '/';
            if (isOp || i == (int)s.size() - 1) {   // a number ends here
                nums.push_back(num);
                if (isOp) ops.push_back(c);
                num = 0;
            }
        }
        for (string level : {"*/", "+-"}) {     // the tighter level first
            size_t k = 0;
            while (k < ops.size()) {
                if (level.find(ops[k]) != string::npos) {   // the first operator of this level still there
                    nums[k] = combine(nums[k], ops[k], nums[k + 1]);
                    nums.erase(nums.begin() + k + 1);       // everything after it moves one place left
                    ops.erase(ops.begin() + k);
                } else {
                    k++;
                }
            }
        }
        return (int)nums[0];
    }

private:
    long long combine(long long a, char op, long long b) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        if (op == '*') return a * b;
        return a / b;                            // truncates toward zero
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        nums, ops = [], []                        # ops[k] sits between nums[k] and nums[k + 1]
        num = 0
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if c in "+-*/" or i == len(s) - 1:    # a number ends here
                nums.append(num)
                if c in "+-*/":
                    ops.append(c)
                num = 0
        for level in ("*/", "+-"):                # the tighter level first
            k = 0
            while k < len(ops):
                if ops[k] in level:               # the first operator of this level still there
                    nums[k] = self.combine(nums[k], ops[k], nums[k + 1])
                    del nums[k + 1]               # everything after it moves one place left
                    del ops[k]
                else:
                    k += 1
        return nums[0]

    def combine(self, a, op, b):
        if op == "+":
            return a + b
        if op == "-":
            return a - b
        if op == "*":
            return a * b
        return int(a / b)                         # truncate toward zero

class Solution {
    public int calculate(String s) {
        List<Long> nums = new ArrayList<>();          // ops.get(k) sits between nums k and k + 1
        List<Character> ops = new ArrayList<>();
        long num = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            boolean isOp = "+-*/".indexOf(c) >= 0;
            if (isOp || i == s.length() - 1) {       // a number ends here
                nums.add(num);
                if (isOp) ops.add(c);
                num = 0;
            }
        }
        for (String level : new String[] {"*/", "+-"}) {   // the tighter level first
            int k = 0;
            while (k < ops.size()) {
                if (level.indexOf(ops.get(k)) >= 0) {      // the first operator of this level still there
                    nums.set(k, combine(nums.get(k), ops.get(k), nums.get(k + 1)));
                    nums.remove(k + 1);                    // everything after it moves one place left
                    ops.remove(k);
                } else {
                    k++;
                }
            }
        }
        return (int) (long) nums.get(0);
    }

    private long combine(long a, char op, long b) {
        if (op == '+') return a + b;
        if (op == '-') return a - b;
        if (op == '*') return a * b;
        return a / b;                                      // truncates toward zero
    }
}

var calculate = function(s) {
    const nums = [], ops = [];               // ops[k] sits between nums[k] and nums[k + 1]
    let num = 0;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c >= "0" && c <= "9") num = num * 10 + Number(c);
        const isOp = "+-*/".includes(c);
        if (isOp || i === s.length - 1) {    // a number ends here
            nums.push(num);
            if (isOp) ops.push(c);
            num = 0;
        }
    }
    for (const level of ["*/", "+-"]) {      // the tighter level first
        let k = 0;
        while (k < ops.length) {
            if (level.includes(ops[k])) {    // the first operator of this level still there
                nums[k] = combine(nums[k], ops[k], nums[k + 1]);
                nums.splice(k + 1, 1);       // everything after it moves one place left
                ops.splice(k, 1);
            } else {
                k++;
            }
        }
    }
    return nums[0];
};

function combine(a, op, b) {
    if (op === "+") return a + b;
    if (op === "-") return a - b;
    if (op === "*") return a * b;
    return Math.trunc(a / b);                // truncate toward zero
}

Complexity Analysis

Time Complexity: O(n²)

Each operator applied deletes from the middle of a list, and everything after it moves one place left: O(n) per operator, for up to n / 2 operators.

Space Complexity: O(n)

The lists of numbers and operators.

Why This Approach Is Not Efficient

With 3 × 10^5 characters there can be 1.5 × 10^5 operators, and every one of them shifts the rest of the list: about 10^10 moves (over the time limit in Python and JavaScript).

Look at when a * or / can be applied: as soon as the number after it is read. Nothing to its right binds tighter, and the * and / before it in the same term are already done. Only + and - have to wait, and they wait in a simple way: their terms are added up at the end. So read the string once, apply each * and / on the spot, and keep the terms on a stack.

Better Approach - One Pass With a Stack of Terms

Intuition

Split the expression at + and - and it falls into terms: 14-3*4/5 has the terms 14 and -3*4/5. Every * and / belongs to one term, and the answer is the sum of the terms.

Read s left to right and remember op, the operator before the number being read (an unwritten + before the first). When a number ends, op says what to do with it: after +, push it as a new term; after -, push its negative; after * or /, combine it with the term on top of the stack. At the end, add up the stack.

Step-by-Step Explanation

Let's trace s = "14-3*4/5":

  1. 14 comes after +: push 14. The stack holds 14.
  2. 3 comes after -: push −3. The stack holds 14, −3.
  3. 4 comes after *: pop −3, push −3 × 4 = −12. The stack holds 14, −12.
  4. 5 comes after /: pop −12, push −12 / 5 = −2, truncated toward zero. The stack holds 14, −2.
  5. That's the end of s. Add up the terms: 14 + (−2) = 12.

The −3 was pushed as a negative, so −3 × 4 / 5 truncates to −2, the same as −(12 / 5): truncating toward zero treats both signs alike.

Calculating 14-3*4/5 — The number being applied is highlighted in s; the stack holds the terms to add up.

Algorithm

  1. Start with an empty stack, num = 0 and op = '+'.
  2. For each index i: if s[i] is a digit, num = num * 10 + digit.
  3. If s[i] is an operator, or i is the last index, the number has ended. Apply op to it: push num, push -num, or pop the top and push it times or divided by num. Then op = s[i] and num = 0.
  4. Return the sum of the stack.

Code

class Solution {
public:
    int calculate(string s) {
        vector<long long> terms;                 // the numbers to add up at the end
        long long num = 0;
        char op = '+';                           // the operator before the number being read
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (isdigit(c)) num = num * 10 + (c - '0');   // a number can have several digits
            if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {   // an operator, or the end
                if (op == '+') terms.push_back(num);
                else if (op == '-') terms.push_back(-num);
                else if (op == '*') terms.back() *= num;
                else terms.back() /= num;        // truncates toward zero
                op = c;
                num = 0;
            }
        }
        long long sum = 0;
        for (long long t : terms) sum += t;
        return (int)sum;
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        terms, num, op = [], 0, "+"          # terms: the numbers to add up at the end
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)      # a number can have several digits
            if c in "+-*/" or i == len(s) - 1:   # an operator, or the end: apply the one before this number
                if op == "+":
                    terms.append(num)
                elif op == "-":
                    terms.append(-num)
                elif op == "*":
                    terms.append(terms.pop() * num)
                else:
                    terms.append(int(terms.pop() / num))   # truncate toward zero
                op, num = c, 0
        return sum(terms)

class Solution {
    public int calculate(String s) {
        Deque<Integer> terms = new ArrayDeque<>();       // the numbers to add up at the end
        int num = 0;
        char op = '+';                                    // the operator before the number being read
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');   // a number can have several digits
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {   // an operator, or the end
                if (op == '+') terms.push(num);
                else if (op == '-') terms.push(-num);
                else if (op == '*') terms.push(terms.pop() * num);
                else terms.push(terms.pop() / num);       // truncates toward zero
                op = c;
                num = 0;
            }
        }
        int sum = 0;
        for (int t : terms) sum += t;
        return sum;
    }
}

var calculate = function(s) {
    const terms = [];                        // the numbers to add up at the end
    let num = 0;
    let op = "+";                            // the operator before the number being read
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c >= "0" && c <= "9") num = num * 10 + Number(c);   // a number can have several digits
        if ("+-*/".includes(c) || i === s.length - 1) {          // an operator, or the end
            if (op === "+") terms.push(num);
            else if (op === "-") terms.push(-num);
            else if (op === "*") terms.push(terms.pop() * num);
            else terms.push(Math.trunc(terms.pop() / num));      // truncate toward zero
            op = c;
            num = 0;
        }
    }
    return terms.reduce((a, b) => a + b, 0);
};

Complexity Analysis

Time Complexity: O(n)

Each character is read once, and each number does one push, or one pop and one push.

Space Complexity: O(n)

Up to one term per number on the stack.

Why This Approach Is Not Efficient

The stack keeps every term until the end, which is O(n) extra space.

But it only ever changes at the top: * and / rewrite the top term, and + or - push a new one. A term below the top is never touched again; it just waits to be added. So add it in the moment it's covered, and the stack shrinks to two numbers.

Optimal Approach - Running Sum and Last Term

Intuition

Keep two numbers in place of the stack: result, the sum of the terms that are finished, and last, the term still being built (the stack's top).

A number after * or / joins last. A number after + or - starts a new term, which means the old last is finished: add it to result, then set last to the new number (negated after -). At the end, last is finished too, so the answer is result + last.

Step-by-Step Explanation

Let's trace s = "14-3*4/5":

  1. 14 starts the first term, last = 14.
  2. 3 comes after -: a new term starts, so result becomes 0 + 14 = 14, and last is −3.
  3. 4 comes after *: last becomes −3 × 4 = −12.
  4. 5 comes after /: last becomes −12 / 5 = −2, truncated toward zero.
  5. That's the end of s: the answer is result + last = 14 + (−2) = 12.

Keep the Sum and the Last Term — Green characters are in result; the highlighted ones are the term in last.

Algorithm

  1. Start with result = 0, last = 0, num = 0 and op = '+'.
  2. For each index i: if s[i] is a digit, num = num * 10 + digit.
  3. If s[i] is an operator, or i is the last index: after + or -, add last to result and set last to num or -num; after * or /, multiply or divide last by num. Then op = s[i] and num = 0.
  4. Return result + last.

Code

class Solution {
public:
    int calculate(string s) {
        long long result = 0;                    // the sum of the finished terms
        long long last = 0;                      // the term still being built
        long long num = 0;
        char op = '+';                           // the operator before the number being read
        for (int i = 0; i < (int)s.size(); i++) {
            char c = s[i];
            if (isdigit(c)) num = num * 10 + (c - '0');
            if ((!isdigit(c) && c != ' ') || i == (int)s.size() - 1) {   // an operator, or the end
                if (op == '+' || op == '-') {
                    result += last;              // a new term starts, so the last one is finished
                    last = op == '+' ? num : -num;
                } else if (op == '*') {
                    last *= num;
                } else {
                    last /= num;                 // truncates toward zero
                }
                op = c;
                num = 0;
            }
        }
        return (int)(result + last);
    }
};

class Solution:
    def calculate(self, s: str) -> int:
        result = 0                                # the sum of the finished terms
        last = 0                                  # the term still being built
        num, op = 0, "+"                          # op: the operator before the number being read
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            if c in "+-*/" or i == len(s) - 1:    # an operator, or the end
                if op in "+-":
                    result += last                # a new term starts, so the last one is finished
                    last = num if op == "+" else -num
                elif op == "*":
                    last *= num
                else:
                    last = int(last / num)        # truncate toward zero
                op, num = c, 0
        return result + last

class Solution {
    public int calculate(String s) {
        int result = 0;                                   // the sum of the finished terms
        int last = 0;                                     // the term still being built
        int num = 0;
        char op = '+';                                    // the operator before the number being read
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {   // an operator, or the end
                if (op == '+' || op == '-') {
                    result += last;                       // a new term starts, so the last one is finished
                    last = op == '+' ? num : -num;
                } else if (op == '*') {
                    last *= num;
                } else {
                    last /= num;                          // truncates toward zero
                }
                op = c;
                num = 0;
            }
        }
        return result + last;
    }
}

var calculate = function(s) {
    let result = 0;                          // the sum of the finished terms
    let last = 0;                            // the term still being built
    let num = 0;
    let op = "+";                            // the operator before the number being read
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c >= "0" && c <= "9") num = num * 10 + Number(c);
        if ("+-*/".includes(c) || i === s.length - 1) {          // an operator, or the end
            if (op === "+" || op === "-") {
                result += last;              // a new term starts, so the last one is finished
                last = op === "+" ? num : -num;
            } else if (op === "*") {
                last *= num;
            } else {
                last = Math.trunc(last / num);   // truncate toward zero
            }
            op = c;
            num = 0;
        }
    }
    return result + last;
};

Complexity Analysis

Time Complexity: O(n)

One pass over s, with constant work per character.

Space Complexity: O(1)

Four variables, however long s is.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Forgetting the last number. if c in "+-*/":

On s = "3+2*2" it returns 5; the answer is 7. A number is applied only when the operator after it arrives, so the last one is never applied unless the loop also acts at the end of the string.

Dividing with Python's //. terms.append(terms.pop() // num)

On s = "14-3/2" it returns 12; the answer is 13. A subtracted term is pushed as a negative number, and Python's // rounds down: -3 // 2 is -2, but the problem truncates toward zero, -1. Use int(a / b).

Taking a space for an operator. if not c.isdigit() or i == len(s) - 1:

On s = "3 + 5" it crashes with ZeroDivisionError: division by zero; the answer is 8. Testing not c.isdigit() also fires on a space. The space then becomes the pending operator, so what comes next falls through to the last branch, division, here by a num of 0. Act only on +, -, * and /, and at the end.

Where This Pattern Is Taught

This problem practises evaluating an expression with a stack. It's taught in Evaluating Expressions with Stacks, along with the shunting yard, which handles brackets and more levels of precedence.