LeetCode_Tasks/0227. Basic Calculator ll.cpp at master · DimitarDTsonev/LeetCode_Tasks · GitHub

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Task: https://leetcode.com/problems/basic-calculator-ii/description/

#include<iostream>
#include<string>
#include<stack>
#include<vector>

// Standart solution using stack:
int calculate(std::string s) {
    s += '+';
    std::stack<int> stk;

    long long int ans = 0, curr = 0;
    char sign = '+';

    for(int i=0; i<s.size(); i++){
        if(isdigit(s[i])) {
            curr = curr*10 + (s[i]-'0');
        }
        else if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/'){
            if(sign == '+') {
                stk.push(curr);
            }
            else if(sign == '-') {
                stk.push(curr*(-1));
            }
            else if(sign == '*'){
                int num = stk.top();
                stk.pop();
                stk.push(num*curr);
            }
            else if(sign == '/'){
                int num = stk.top();
                stk.pop();
                stk.push(num/curr);
            }
            curr = 0;
            sign = s[i];
        }
    }

    while(stk.size()){
        ans += stk.top();
        stk.pop();
    }

    return ans;
}

// Faster method using vector:
//int calculate(std::string s) {
    //     char op = '+';
    //     int curr = 0;
    //     std::vector<int> stk;

    //     for (int i = 0; i < s.size(); ++i) {

    //         if(isdigit(s[i])) curr = curr*10 + (s[i] - '0');

    //         if(i==s.size()-1 || s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/'){
    //             if (op == '+') stk.push_back(curr);
    //             else if (op == '-') stk.push_back(curr*(-1));
    //             else if (op == '*'){
    //                 int num = stk.back();
    //                 stk.pop_back();
    //                 stk.push_back(num * curr);
    //             }
    //             else if (op == '/'){
    //                 int num = stk.back();
    //                 stk.pop_back();
    //                 stk.push_back(num / curr);
    //             }

    //             curr = 0;
    //             op = s[i];
    //         }
    //     }
    //     return accumulate(stk.begin(), stk.end(), 0);
//}

int main(){
    // Example 1:
    std::string e1("3+2*2");
    std::cout << calculate(e1) << std::endl;

    // Example 2:
    std::string e2("3/2");
    std::cout << calculate(e2) << std::endl;

    // Example 3:
    std::string e3("3+5/2");
    std::cout << calculate(e3) << std::endl;

    return 0;
}