11.3 String Parsing

227. Basic Calculator II

Problem Description

Given a string containing addition, subtraction, multiplication, and division of integers, calculate the result. Division truncates towards zero.

Input and Output Example

Input is a valid arithmetic string, and output is an integer representing the result.

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

In this example, since division has a higher priority than addition, the result is 5 rather than 4.

Solution Explanation

If we prepend a + sign to the left of the string, it doesn't change the result, and the string can be divided into multiple pairs of <operator, number>. This allows us to process the string from left to right. Since multiplication and division have higher precedence than addition and subtraction, we need an intermediate variable to store results of high-priority operations.

This type of problem also tests edge cases, such as strings without operators or with multiple spaces.

C++

// Helper function to parse a number starting from position i.
int parseNum(const string& s, int& i) {
    int num = 0, n = s.length();
    while (i < n && isdigit(s[i])) {
        num = 10 * num + (s[i++] - '0');
    }
    return num;
}

// Main function
int calculate(string s) {
    char op = '+';
    long global_num = 0, local_num = 0;
    int i = -1, n = s.length();
    while (++i < n) {
        if (s[i] == ' ') {
            continue;
        }
        long num = parseNum(s, i);
        switch (op) {
            case '+':
                global_num += local_num;
                local_num = num;
                break;
            case '-':
                global_num += local_num;
                local_num = -num;
                break;
            case '*':
                local_num *= num;
                break;
            case '/':
                local_num /= num;
                break;
        }
        if (i < n) {
            op = s[i];
        }
    }
    return global_num + local_num;
}

Python

from typing import Tuple

# Helper function to parse a number starting from position i.
# Returns (number, next position i)
def parseNum(s: str, i: int) -> Tuple[int, int]:
    num, n = 0, len(s)
    while i < n and s[i].isdigit():
        num = 10 * num + int(s[i])
        i += 1
    return (num, i)

# Main function
def calculate(s: str) -> int:
    op = "+"
    global_num, local_num = 0, 0
    i, n = 0, len(s)
    
    while i < n:
        if s[i] == " ":
            i += 1
            continue
        
        num, i = parseNum(s, i)
        
        match op:
            case "+":
                global_num += local_num
                local_num = num
            case "-":
                global_num += local_num
                local_num = -num
            case "*":
                local_num *= num
            case "/":
                # int() performs truncation towards zero, unlike // for negatives.
                local_num = int(local_num / num)
        
        if i < n:
            op = s[i]
            i += 1

    return global_num + local_num