Evaluate Expression

See the original problem on HackerRank.

You are given an expression in Reverse Polish Notation (RPN) and you have to evaluate it.

Input Format

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

Output Format

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())
We've worked on this challenge in these gyms: modena  padua  milan  barcelona  turin 
comments powered by Disqus