My 188ms C++ solution using vector: looks messy but it works


  • 0
    T
    class Solution {
    private:
        vector<string> parse(string s)
        {
            int n = s.length();
            int i=0, j=0;
            vector<string> result;
            char cs[n+1];
            strcpy(cs, s.c_str());
            while(i<n)
            {
                if(cs[i] == ' ')
                {
                    i = i + 1;
                }
                else if(cs[i] == '+' || cs[i] == '-' || cs[i] == '(' || cs[i] == ')')
                {
                    string ts;
                    ts += cs[i];
                    result.push_back(ts);
                    i = i + 1;
                }
                else
                {
                    string s;
                    j=i;
                    while(cs[j] != '+' && cs[j] != '-' && cs[j] != ' ' && j<n && cs[j]!='(' && cs[j]!=')')
                    {
                        s = s + cs[j];
                        j = j + 1;
                    }
                    result.push_back(s);
                    i=j;
                }
            }
            return result;
        }
        
        vector<string> reverse(vector<string> temp)
        {
            vector<string> result;
            int n = temp.size();
            int i;
            for(i=0; i<n; i++)
                result.push_back(temp[n-i-1]);
            return result;
        }
        
        string simpleCalculate(vector<string> TEMP)
        {
            vector<string> temp = reverse(TEMP);
            int n = temp.size();
            int i;
            int value=atoi(temp[0].c_str());
            for(i=1; i<n; i = i+2)
            {
                if(temp[i] == "+")
                    value = value+atoi(temp[i+1].c_str());
                else if(temp[i] == "-")
                    value = value-atoi(temp[i+1].c_str());
            }
            return to_string(value);
        }
        
        string simpleCalculate2(vector<string> TEMP)
        {
            vector<string> temp = TEMP;
            int n = temp.size();
            int i;
            int value=atoi(temp[0].c_str());
            for(i=1; i<n; i = i+2)
            {
                if(temp[i] == "+")
                    value = value+atoi(temp[i+1].c_str());
                else if(temp[i] == "-")
                    value = value-atoi(temp[i+1].c_str());
            }
            return to_string(value);
        }
    public:
        int calculate(string s) {
            vector<string> str = parse(s);
            int n = str.size();
            int i;
            vector<string> stack;
            for(i=0; i<n; i++)
            {
                if(str[i] != ")")
                {
                    stack.push_back(str[i]);
                }
                else
                {
                    vector<string> temp;
                    while(stack.back() != "(")
                    {
                        temp.push_back(stack.back());
                        stack.pop_back();
                    }
                    stack.pop_back();
                    stack.push_back(simpleCalculate(temp));
                }
            }
            string final = simpleCalculate2(stack);
            return atoi(final.c_str());
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.