Polish notation/expression is also known as ‘prefix notation’ where the numbers are preceded by its operator (placed in the front). For example, “3 * 5” transformed to polish notation will become “* 3 5”. The distinguishing feature of polish notation is that it eliminates the need of brackets, which are used to change to priority of the computation. For example, “5 − (6 * 7)” will be transformed to “− 5 * 6 7”. Polish notations/expressions are the fundamental in evaluation of mathematical expressions, which is a commonly used technique in most compilers/interpreters. To evaluate the expression, it is easy but the constructing process from the infix notation. Infix notation is the common arithmetic and logical formula notation, for example, 3 + 4. The reverse Polish notation places the operator after numbers, for example, 3 5 * is the same as 3 * 5. You are required to evaluate the reverse polish notation given the numbers are all integers and the operators are plus, minus, multiply and divide only.
Algorithm to Evaluate Reverse Polish Notation
The polish notation and reverse polish notation are similar. Both can be solved by same algorithm (just different directions). We need a stack (First In Last Out data structure) where we store the intermediate numbers. We can evaluate this expression one pass. When we meet numbers, we simply push them to stack otherwise we pop two numbers from the stack and compute the value (base on the current operator), and push the intermediate result back to the stack. When reaching the end of the expression, there should be only 1 element/number in the stack, which is the answer. If not, the polish expression may be corrupted or incomplete.
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 | class Solution { public: int evalRPN(vector &tokens) { stack<int> nums; int len = tokens.size(); for (int i = 0; i < len; i ++) { string x = tokens[i]; if ((x == "+") || (x == "-") || (x == "*") || (x == "/")) { // pop two numbers off the stack int a = nums.top(); nums.pop(); int b = nums.top(); nums.pop(); // evaluate and push the result back switch (x[0]) { case '+': nums.push(a + b); break; case '-': nums.push(b - a); break; case '*': nums.push(b * a); break; case '/': nums.push(b / a); break; } } else { // push a number into the stack int n; istringstream(x) >> n; nums.push(n); } } if (!nums.empty()) { int xx = nums.top(); while (nums.size()) { nums.pop(); } return xx; } return 0; // error occurs } }; |
class Solution {
public:
int evalRPN(vector &tokens) {
stack<int> nums;
int len = tokens.size();
for (int i = 0; i < len; i ++) {
string x = tokens[i];
if ((x == "+") || (x == "-") || (x == "*") || (x == "/")) {
// pop two numbers off the stack
int a = nums.top();
nums.pop();
int b = nums.top();
nums.pop();
// evaluate and push the result back
switch (x[0]) {
case '+': nums.push(a + b); break;
case '-': nums.push(b - a); break;
case '*': nums.push(b * a); break;
case '/': nums.push(b / a); break;
}
} else { // push a number into the stack
int n;
istringstream(x) >> n;
nums.push(n);
}
}
if (!nums.empty()) {
int xx = nums.top();
while (nums.size()) {
nums.pop();
}
return xx;
}
return 0; // error occurs
}
};Since the problem says only 4 operators are possible ‘+’, ‘-‘, ‘*’ and ‘/’, therefore, we can check each element to see if it is a operator, otherwise, it is a number. Therefore, in this case, we don’t need to provide complex is_number implementation and of course it is quicker.
We use istringstream(x) >> n; to convert string x to number n using istringstream.
A better/cleaner implementation using the map to map the operator to each lambda function or std::function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: int evalRPN(vector<string>& tokens) { unordered_map<string, function<int(int, int)>> ops = { {"+", [](int x, int y) -> int { return x + y; }}, {"-", [](int x, int y) -> int { return x - y; }}, {"*", [](int x, int y) -> int { return x * y; }}, {"/", [](int x, int y) -> int { return x / y; }}, }; stack<int> data; for (auto &s: tokens) { if (ops.count(s)) { int y = data.top(); data.pop(); int x = data.top(); data.pop(); data.push(ops[s](x, y)); } else { data.push(stoi(s)); } } return data.top(); } }; |
class Solution {
public:
int evalRPN(vector<string>& tokens) {
unordered_map<string, function<int(int, int)>> ops = {
{"+", [](int x, int y) -> int { return x + y; }},
{"-", [](int x, int y) -> int { return x - y; }},
{"*", [](int x, int y) -> int { return x * y; }},
{"/", [](int x, int y) -> int { return x / y; }},
};
stack<int> data;
for (auto &s: tokens) {
if (ops.count(s)) {
int y = data.top();
data.pop();
int x = data.top();
data.pop();
data.push(ops[s](x, y));
} else {
data.push(stoi(s));
}
}
return data.top();
}
};In Python, we can directly use the operator functions:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def evalRPN(self, tokens: List[str]) -> int: operators = {'+': add, '-': sub, '*': mul, '/': truediv} stack = [] for t in tokens: if t in operators: right = stack.pop() left = stack.pop() stack.append(int(operators[t](left, right))) else: stack.append(int(t)) return stack[0] |
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operators = {'+': add, '-': sub, '*': mul, '/': truediv}
stack = []
for t in tokens:
if t in operators:
right = stack.pop()
left = stack.pop()
stack.append(int(operators[t](left, right)))
else:
stack.append(int(t))
return stack[0]See also: Teaching Kids Programming – Evaluate Reverse Polish Notation
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C/C++ Coding Exercise - Reverse Words in a String - LeetCode Online Judge - Using Stack
Next Post: C/C++ Frequent Pointer Mistakes
