The Basic Calculator in C/C++

Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

O(n) time, O(1) space

The operator * and / have higher priority over + and -. However, we might consider using + and – as a group separator. For example,

1 + 2 – 3 * 5 can be grouped as +1, +2, -(3*5). The answer would be to add the group values along the scan. At first, the sign is + by default, if we meet an operator, we store it, if we meet numbers, we store it as an intermediate number. We add the number to the final value if the current oper is + or -. Otherwise, we need to multiply/divide it with the previous value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    int calculate(string s) {
        int r = 0;
        char oper = '+';
        int tmp = 0;
        int i = 0;
        while (i < s.length()) {
            if (s[i] != ' ') {
                if (s[i] >= '0' && s[i] <= '9') {
                    int num = 0;
                    while (i < s.length() && s[i] >= '0' && s[i] <= '9') {
                        num = num * 10 + s[i] - '0';
                        i ++;
                    }
                    if (oper == '+' || oper == '-') {
                        r += tmp;
                        tmp = num * (44 - oper); // 43 = +, 45 = -
                    } else if (oper == '*') {
                        tmp *= num;
                    } else {
                        tmp /= num;
                    }
                    continue;
                } else {
                    oper = s[i];
                }
            }
            i ++;
        }
        return r + tmp;
    }
};

class Solution {
public:
    int calculate(string s) {
        int r = 0;
        char oper = '+';
        int tmp = 0;
        int i = 0;
        while (i < s.length()) {
            if (s[i] != ' ') {
                if (s[i] >= '0' && s[i] <= '9') {
                    int num = 0;
                    while (i < s.length() && s[i] >= '0' && s[i] <= '9') {
                        num = num * 10 + s[i] - '0';
                        i ++;
                    }
                    if (oper == '+' || oper == '-') {
                        r += tmp;
                        tmp = num * (44 - oper); // 43 = +, 45 = -
                    } else if (oper == '*') {
                        tmp *= num;
                    } else {
                        tmp /= num;
                    }
                    continue;
                } else {
                    oper = s[i];
                }
            }
            i ++;
        }
        return r + tmp;
    }
};

You can also build the reverse polish expression, which is a more generalized solution that can be used to evaluate the expression containing () brackets.

–EOF (The Ultimate Computing & Technology Blog) —