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())
|