basic-calc

Problem

Analysis

  • we need to skip spaces
  • we can use a recursive function since each expression is a subproblem
1
2
3
4
4-3+6-(45+6-(77 - 5) + 3) is equivalent to
4-3+6-45-6+77-5+3
      ^---------- negative
          ^------- positive since two negatives

So we can keep track of the sign changes

Attempt

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    /*
     Contains -1's
     */
    int getsign(vector<int>& v) {
        int sign = 1;
        for (int e: v) {
            sign *= e;
        }
        return sign;
    }
    int getnum(string s, int& i) {
        string n;
        while (i < s.size() && isdigit(s[i])) {
            n+=s[i];
            i++;
        }
        return stoi(n);
    }
public:
    int calculate(string s) {
        vector<int> signs;
        for (int i = 0; i < s.size(); i++) {
            if (isdigit(s[i])) {
                num = getnum(s, i)
                sum += sign * num;
            } else if (s[i] == '(') {
                // when we start a new group
                // we calculate the new sign to
                // apply
                // first push the last sign we e
                signs.push_back(sign);
                sign = getsign(signs);

                // skip over any extra '('?
                //while (i < s.size() && s[i] == '(') i++;

            } else if (s[i] == ')') {
                // we need to pop the signs stack
                signs.pop_back();
                // todo skip over extra ')'?
            } else if (s[i] == '-') {
                sign = -1;
            } else if (s[i] == '+') {
                sign = 1;
            }
        }
    }
};

ATtempt 2

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


class Solution {
    /*
     Contains -1's
     */
    int getsign(vector<int>& v) {
        int sign = 1;
        for (int e: v) {
            sign *= e;
        }
        return sign;
    }
    int getnum(string s, int& i) {
        string n;
        while (i < s.size() && isdigit(s[i])) {
            n+=s[i];
            i++;
        }
        return stoi(n);
    }
public:
    int calculate(string s) {
        vector<int> signs = {1};
        int sum = 0;
        int num = 0;
        int sign = 1;
        for (int i = 0; i < s.size(); i++) {
            if (isdigit(s[i])) {
                num = getnum(s, i);
                sum += sign * num;
                cout << "d = " << sign * num << endl;
            } else if (s[i] == '(') {
                // when we start a new group
                // we calculate the new sign to
                // apply
                // first push the last sign we e
                signs.push_back(sign);
                //sign = getsign(signs);

                // skip over any extra '('?
                //while (i < s.size() && s[i] == '(') i++;

            } else if (s[i] == ')') {
                // we need to pop the signs stack
                signs.pop_back();
                // todo skip over extra ')'?
            } else if (s[i] == '-') {
                sign = signs.back() * -1;
            } else if (s[i] == '+') {
                sign = signs.back();
            }
        }
        return sum;
    }
};

Note about performance

TODO