Code challenges from C++ interviews. Reverse Polish notation (RPN)

Introduction

Recently at one of the interviews for a position of С++ developer I was asked to solve the task about RPN. I found this task quite interesting for me and decided to present my solution. Besides that the optimal solution uses one of the widespread approach that should be known.

Task description and conditions

Have the function with the following signature:

std::string CalculateRpnExpression(std::string str);          

Read str which will be an arithmetic expression composed of only positive integers and the operators: +, -, *, /. The input expression will be in postfix notation (RPN). Return the result of arithmetic operation. Return "error" in case of errors in input string. Don't worry about overflows, the input string assumes to have operands and result of expression that are not exceed the int limits.

What is RPN

Reverse Polish Notation (RPN) is a method for representing expressions in which the operator symbol is placed after the arguments being operated on.

For instance:

(2 + 12) / 7 = 2; // regular expression  
2 12 + 7 / = 2; // RPN  

(4 + 5) * (2 + 1) = 27; // regular expression  
4 5 + 2 1 + * = 27; // RPN        

Basically, it is not very widespread form of math expression, but it has a quite significant benefit that any expression can be represented without brackets and also it helps to get rid of misunderstandings in priority of operations.

Thoughts and finding approach

From the description of RPN we can highlight that the math operator is always placed after the operands and the number of operands for the corresponding math operator is also equal to 2.

1.Taking into account this fact we can make a first conclusion on the way of finding an approach. It is necessary to iterate through the given string, convert given numbers into the integer values and save it in some additional data structure until the sign will be encountered.

2. Since the only two last operands will be applied for the math operation when the sign is encountered, the best data structure that can be used is stack. I won't pay much attention to the stack data structure, there are a lot of information in an open sources. There is also a corner case here. If the stack contains less than 2 operands, then our function should return "error" value.

3. The signs can be placed inside the unordered set, because there is a limited number of these signs and the complexity of finding in unordered set is O(1). When the sign encountered, it is necessary to get 2 operands from stack and make a calculation. There is one more corner case here. If we have a "/" sign, then the operand №2 should not be equal to zero, otherwise the program should return "error" string.

4. After proceeding the calculation, it is necessary to put the result back to stack.

All the previous steps should be placed inside the cycle and proceeding while the end of the string is not reached.

Finally, the result of calculation will be presented on the top of the stack. There is a corner case here, that should be proceeded. If stack contains more than 1 value, it means that some of the operands remained intact. It means that there is an error exists in input string and our program should return "error" as in task conditions was mentioned.

Below is an example of how does the expression is calculated using stack. Let's consider the example that was mentioned in previous paragraph:

(4 + 5) * (2 + 1) = 27; // regular expression

4 5 + 2 1 + * = 27; // RPN

Proposed solution (C++)

#include <iostream>
#include <string>
#include <stack>
#include <unordered_set>

using namespace std;

string reverseNotation(string& s)
{
    string currNum;
    // avoid string copying. Max int contains 10 symbols (decimal)
    currNum.reserve(10); 
    unordered_set<char> signs {'+', '-', '*', '/'};

    stack<int> st;

    for (int i = 0; i < s.length(); i++)
    {
        // sign found
        if (signs.find(s[i]) != signs.end())
        {
            if (st.size() < 2) // wrong operation
            {
                return "error";
            }

            int operand1, operand2, result;
            operand2 = st.top();
            st.pop();
            operand1 = st.top();
            st.pop();

            if (s[i] == '+')  // add
            {
                result = operand1 + operand2;
            }
            else if (s[i] == '-')  // sub
            {
                result = operand1 - operand2;
            }
            else if (s[i] == '*')  // multiply
            {
                result = operand1 * operand2;
            }
            else  // devide
            {
                if (operand2 == 0)
                {
                    return "error";
                }
                result = operand1 / operand2;
            }

            st.push(result);
        }
        else if (s[i] == ' ')  // space found
        {
            if (!currNum.empty())
            {
                st.push(stoi(currNum));
                currNum.erase();
            }
        }
        else  // it is digit
        {
            currNum.push_back(s[i]);
        }
    }

    if (st.size() != 1)
    {
        return "error";
    }
    return to_string(st.top());
}
        

Conclusion

The proposed approach has the following properties:

Time complexity - O(N)

Additional space usage - O(N)

The most important thing that can be extracted from this task is the using of additional stack data structure, that allows us to save the operands in necessary sequence and get it back properly. It is known and very spread approach for finding solution to algorithmic tasks.

One more thing is using of unordered set for storing the signs, that allows to find it in O(1) time.

I can't promise that it is the most beautiful and optimal solution, but I received a positive feedback. Hope that the provided information was helpful for you.