C++ accepted solution stack


  • 0
    X
    //basic calculator II
    class Solution {
    public:
        int calculate(string s) {
            int n = s.length();
            int start = 0;
            int p = 0;
            while (start < n && s[start] == ' ') start++;
            stack<char> expressionStack;
            vector<string> reversePolandExpression;
            while (start < n) {
                p = start;
                if (isDigit(s[p])) {
                    while (p < n && isDigit(s[p])) p++;
                    reversePolandExpression.push_back(s.substr(start, p - start));
                } else if (isOperator(s[p])) {
                    if (expressionStack.empty()) {
                        expressionStack.push(s[p]);
                    } else {
                        while (!expressionStack.empty() && priority(expressionStack.top()) >= priority(s[p])) {
                            char c = expressionStack.top();
                            expressionStack.pop();
                            reversePolandExpression.push_back(string(1, c));
                        }
                        expressionStack.push(s[p]);
                    }
                    p++;
                }
                
                start = p;
                while (start < n && s[start] == ' ') start++;
            }
            
            //push all the things left in the stack
            while (!expressionStack.empty()) {
                char c = expressionStack.top();
                expressionStack.pop();
                reversePolandExpression.push_back(string(1, c));
            }
            
            stack<int> resultStack;
            //calculate the reverse poland expression
            for (auto str : reversePolandExpression) {
                if (str != "+" && str != "-" && str != "*" && str != "/") {
                    resultStack.push(stoi(str));
                } else {
                    int second = resultStack.top(); resultStack.pop();
                    int first = resultStack.top(); resultStack.pop();
                    if (str == "+") {
                        resultStack.push(first + second);
                    } else if (str == "-") {
                        resultStack.push(first - second);
                    } else if (str == "*") {
                        resultStack.push(first * second);
                    } else if (str == "/") {
                        resultStack.push(first / second);
                    }
                }
            }
            
            return resultStack.top();
            
        }
        
        bool isDigit(char c) {
            return c >= '0' && c <= '9';
        }
        
        bool isOperator(char c) {
            return c == '+' || c == '-' || c == '*' || c == '/';
        }
        
        int priority(char c) {
            if (c == '+' || c == '-') return 1;
            if (c == '*' || c == '/') return 2;
        }
    };

Log in to reply
 

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