Reverse Polish Notation Solution C++


  • 1
    H

    This is not an optimal solution, just want to share a different idea.
    Transfer the expression to Reverse Polish Notation.
    The merit of this solution is that it can be easily expanded to calculate more complicated expression.
    Related to 150. Evaluate Reverse Polish Notation

    class Solution {
    public:
        int calculate(string s) {
            stack<int> calc;
            vector<int> rpn;
            int num = -1;
            unordered_map<char, int> p{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; // precedence of operator
            
            // Transfer to RPN
            for (auto c : s) {
                if (isdigit(c)) num = num == -1 ? c-'0' : num*10+(c-'0');
                else {
                    if (num != -1) {
                        rpn.push_back(num);
                        num = -1;
                    }
                    if (c != ' ') {
                        while (!calc.empty() and p[-calc.top()] >= p[c])
                            rpn.push_back(calc.top()), calc.pop();
                        calc.push(-c);  // use negative number to denote operators,
                    }                   // since all the operands are guaranteed to be non-negative
                }
            }
            if (num != -1) rpn.push_back(num);    // last number
            while (!calc.empty())
                rpn.push_back(calc.top()), calc.pop();
            
            // Calculate RPN
            for (auto op : rpn) {
                if (op >= 0) calc.push(op);
                else {
                    int op2 = calc.top();
                    calc.pop();
                    int op1 = calc.top();
                    calc.pop();
                    if (-op == '+') calc.push(op1+op2);
                    else if (-op == '-') calc.push(op1-op2);
                    else if (-op == '*') calc.push(op1*op2);
                    else if (-op == '/') calc.push(op1/op2);
                }
            }
            return calc.top();
        }
    };

Log in to reply
 

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