See the original problem on HackerRank.
You are given an expression in Reverse Polish Notation (RPN) and you have to evaluate it.
Space separated terms of the expression to evaluate (at least one element).
Constraints
Each numeric element fits an int32.
Any other token is either +, -, *, /
The result is guaranteed not to go beyond the int32 representation
The result of the expression evaluation, as a single number.
Solutions
The solution for this excercise would be to use a stack. When parsing each
element of the expression we’ll add the element to the stack if it’s a digit
or if it is an operation we’ll pop the last two elements of the stack, calculate
the new value and add it to the stack again. Once we don’t have any more elements
in the expression to parse the last and only element in the stack is our solution.
C++ with std::stack and map of operations
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
|
#include <stack>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
static const map<string, int(*)(int, int)> opToFn {
{ "+", [](int l, int r) { return l + r; } },
{ "-", [](int l, int r) { return l - r; } },
{ "*", [](int l, int r) { return l * r; } },
{ "/", [](int l, int r) { return l / r; } }
};
stack<int> args;
string operand;
while (cin >> operand)
{
auto it = opToFn.find(operand);
if (it == end(opToFn))
args.push(atoi(operand.data()));
else
{
auto r = args.top(); args.pop();
auto l = args.top(); args.pop();
args.push(it->second(l, r));
}
}
if (args.empty())
cout << 0;
cout << args.top();
}
|
Alternative C++ solution
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
|
#include <iostream>
#include <list>
#include <functional>
inline void applyOperation(std::function<int(int, int)> op, std::list<int>& stack) {
int r = stack.back(); stack.pop_back();
int l = stack.back(); stack.pop_back();
stack.push_back(op(l, r));
}
int main() {
std::list<int> stack;
std::string curr;
while (std::cin >> curr) {
switch (curr[0]) {
case '+': applyOperation(std::plus<int>(), stack); break;
case '-': applyOperation(std::minus<int>(), stack); break;
case '*': applyOperation(std::multiplies<int>(), stack); break;
case '/': applyOperation(std::divides<int>(), stack); break;
default: stack.push_back(std::stoi(curr)); break;
}
}
std::cout << stack.back() << std::endl;
return 0;
}
|
Javascript solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
function applyOperation(op, stack) {
const l = stack[stack.length - 2];
const r = stack[stack.length - 1];
stack.splice(-2, 2);
stack.push(op(l, r));
}
function processData(input) {
let stack = [];
input.split(' ').forEach(s => {
switch (s) {
case '+': applyOperation((l, r) => l + r, stack); break;
case '-': applyOperation((l, r) => l - r, stack); break;
case '*': applyOperation((l, r) => l * r, stack); break;
case '/': applyOperation((l, r) => Math.floor(l / r), stack); break;
default: stack.push(Number(s)); break;
}
});
return String(stack[0]);
}
|
Python solution
The following python solution leverages the operator module from the standard
library that implements usual operator as functions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import operator
op_map = {
'+': operator.add,
'/': operator.floordiv,
'*': operator.mul,
'-': operator.sub
}
stack = []
expression = input().split()
for x in expression:
if x.isdigit():
stack.append(int(x))
else:
op = op_map[x]
b, a = stack.pop(), stack.pop()
stack.append(op(a, b))
print(stack.pop())
|
Alternative Python solution
This alternative approach evaluates the RPN expression in place by repeatedly reducing the token list. Instead of pushing/popping on a stack, it scans the list with a small “three-item window”: whenever it finds two numbers followed by an operator, it computes that sub-expression and directly replaces the three tokens with the single result.
The process repeats until only one value remains. A small helper function, calc, performs the arithmetic and uses math.trunc(a / b) to implement division truncated toward zero (the convention typically expected in RPN problems), which differs from operator.floordiv that floors toward -∞. A safe numeric check (isdigit) avoids errors while scanning mixed number/operator windows.
Key differences vs the stack-based solution:
- No explicit stack: operates directly on the token list by reduction.
- Division semantics: uses
math.trunc (truncate toward zero) rather than operator.floordiv (floor), which matters for possible negative operands.
- Flow: relies on sliding-window pattern matching (
number number operator) instead of unconditional push/pop.
From a computational perspective, this reduction-based approach is less efficient than the stack method, but it still manages to pass all the unit tests.
Each reduction shortens the token list, but deleting and inserting elements in the middle of a Python list is an O(n) operation.
Since up to n reductions are needed (where n is the number of tokens), the overall worst-case complexity can grow to O(n²).
In contrast, the stack approach only performs O(1) operations per token, always yielding a linear O(n) complexity, and it is therefore preferred.
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
37
38
39
40
41
|
import math
# helper for arithmetic (division truncated toward zero)
def calc(op1, op2, token):
a = int(op1)
b = int(op2)
if token == "+": return a + b
if token == "-": return a - b
if token == "*": return a * b
if token == "/": return math.trunc(a / b)
def istoken(item):
return item in ["+", "-", "*", "/"]
def isdigit(item):
# True if item is an int or a numeric string (including negatives)
if isinstance(item, int):
return True
if isinstance(item, str):
int(item) # raises if not numeric
return True
return False
exp = input().split()
i = 0
while len(exp) != 1:
if isdigit(exp[i]) and isdigit(exp[i+1]) and istoken(exp[i+2]):
result = calc(exp[i], exp[i+1], exp[i+2])
del exp[i+2]; del exp[i+1]; del exp[i]
exp.insert(i, result)
elif isdigit(exp[i]) and isdigit(exp[i+1]) and isdigit(exp[i+2]):
if i + 3 < len(exp) and istoken(exp[i+3]):
result = calc(exp[i+1], exp[i+2], exp[i+3])
del exp[i+3]; del exp[i+2]; del exp[i+1]
exp.insert(i+1, result)
i = 0
else: # Keep the window going in case it is needed
i += 1
print(exp[0])
|