leetcode/basic-calculator/main.cpp at main · milosz275/leetcode · 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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <sstream>
#include <vector>
#include <stack>

using namespace std;

class Solution
{
public:
    int evaluate(int current_value, int total_value, char operation)
    {
        switch (operation)
        {
        case '+':
            total_value += current_value;
            break;
        case '-':
            total_value -= current_value;
            break;
        default:
            break;
        }
        return total_value;
    }

    int calculate(string s)
    {
        int total_value = 0;

        stringstream str_st(s);
        bool contains_opening_bracket = false;
        char current_sign;
        str_st >> current_sign;
        if (current_sign == '+' || current_sign == ')')
            throw runtime_error(string("Invalid syntax: s string starts with ") + current_sign);
        while (str_st >> current_sign)
        {
            if (current_sign == ')')
                throw runtime_error("Invalid syntax: closing bracket appears before opening bracket");
            if (current_sign == '(')
            {
                contains_opening_bracket = true;
                break;
            }
        }

        // base case - no brackets
        if (!contains_opening_bracket)
        {
            stringstream str_st(s);
            bool is_first = true;
            char operation = '\0';
            int current_value = 0;
            int current_radix_value = 1;

            while (str_st >> current_sign)
            {
                if (isdigit(current_sign))
                {
                    current_value *= current_radix_value;
                    current_value += atoi(string(1, current_sign).c_str());
                    current_radix_value *= 10;
                }
                else // current sign is a new operation
                {
                    current_radix_value = 1;

                    if (is_first)
                    {
                        if (operation == '-')
                            total_value -= current_value;
                        else
                            total_value += current_value;
                        current_value = 0;
                        is_first = false;
                    }
                    else // handle operation before overwriting
                    {
                        total_value = evaluate(current_value, total_value, operation);
                        current_value = 0;
                    }

                    operation = current_sign;
                }
            }

            // last number was not evaluated due to stream end
            return evaluate(current_value, total_value, operation);
        }
        else // recursive case
        {
            stack<int> bracket_indices;
            for (int i = 0; i < (int)s.size(); ++i)
            {
                if (s[i] == '(')
                    bracket_indices.push(i);
                else if (s[i] == ')')
                {
                    if (bracket_indices.empty())
                        throw runtime_error("Invalid syntax: unmatched closing bracket");

                    int start = bracket_indices.top(); // matching opening bracket index
                    bracket_indices.pop();

                    string inner_expression = s.substr(start + 1, i - start - 1);
                    int inner_result = calculate(inner_expression);

                    // merge evaluated part into original s
                    string left_part = s.substr(0, start); // before opening bracket
                    string right_part = s.substr(i + 1); // after closing bracket
                    s = left_part + to_string(inner_result) + right_part;

                    // update location after merging result
                    i = start - 1;
                }
            }

            if (!bracket_indices.empty())
                throw runtime_error("Invalid syntax: unmatched opening bracket");

            return calculate(s);
        }

        return total_value;
    }
};

int main()
{
    Solution sol;
    string s = "(1+(4+5+2)-3)+(6+8)";
    // string s = " 21-1 + 28 - 8-2";
    try
    {
        sol.calculate(s);
        //cout << s << " = " << sol.calculate(s) << endl;
    }
    catch (const std::runtime_error& ex)
    {
        cout << ex.what() << endl;
    }
    return 0;
}