# Reverse Polish Notation Solution C++

• 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();
}
};``````

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