Reverse Polish Notation in C++

Question

I am currently trying to write a RPN calculator for an assignment and I'm having some problems. The method evaluateCountdown is meant to take in a string containing a mathematical expression written in Reverse Polish Notation and it's meant to return the result of evaluating the expression as a double.

For example: string "3.0 4.0 + 2.0 *" should return 14.0 as a double.

#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <stack>
 
class CountdownSolution {

std::vector<std::string> stringToVector(const std::string newString,const char token)
{
 std::vector<std::string> stringVector;
 
 size_t posLast = 0, pos = 0;
 while((pos = newString.find(token, pos)) != std::string::npos)
 {
   if(newString[pos] != newString[posLast])
     stringVector.push_back(newString.substr(posLast, pos - posLast));
   posLast = ++pos;
 }
 if(newString[posLast] != 0)
   stringVector.push_back(newString.substr(posLast));
 
 return stringVector;
}
 
double evaluateCountdown(const std::string& rpnString) {
   std::vector<std::string> rpnStringVector = stringToVector(rpnString,' ');
   std::stack<double> rpnStack;
   int i = 0;
   double temp;
   for (std::vector<std::string>::iterator t=rpnStringVector.begin(); t!=rpnStringVector.end(); ++t)
   {
       if(rpnStringVector[i] == "+"){
           temp = std::stod(rpnStringVector[i-2])+std::stod(rpnStringVector[i-1]);
           rpnStack.pop();
           rpnStack.pop();
           rpnStack.push(temp);
           i++;
           continue;
       } else if(rpnStringVector[i] == "-"){
           temp = std::stod(rpnStringVector[i-2])-std::stod(rpnStringVector[i-1]);
           rpnStack.pop();
           rpnStack.pop();
           rpnStack.push(temp);
           i++;
           continue;
       } else if(rpnStringVector[i] == "*"){
           temp = std::stod(rpnStringVector[i-2])*std::stod(rpnStringVector[i-1]);
           rpnStack.pop();
           rpnStack.pop();
           rpnStack.push(temp);
           i++;
           continue;
       } else if(rpnStringVector[i] == "/"){
           temp = std::stod(rpnStringVector[i-2])/std::stod(rpnStringVector[i-1]);
           rpnStack.pop();
           rpnStack.pop();
           rpnStack.push(temp);
           i++;
           continue;
       } else {
           rpnStack.push(std::stod(rpnStringVector[i]));
           i++;
           continue;
       }
   }
   return rpnStack.top();
   }
}

Out of the following 4 tests I only pass 1.

#include <iostream>
using std::cout;
using std::endl;
 
#include <string>
 
int main() {
 
   int retval = 0;
  
   {
       double answer = evaluateCountdown(std::string("3.0 4.0 +"));
       if (answer == 7.0) {
           cout << "1) Pass: evaluated '3.0 4.0 +', got 7.0\n";
       } else {
           cout << "1) Fail: evaluated '3.0 4.0 +' expecting 7.0, but got " << answer << std::endl;
           ++retval;
       }
   }
  
   {
       double answer = evaluateCountdown(std::string("3.0 4.0 - 4.0 +"));
       if (answer == 3.0) {
           cout << "2) Pass: evaluated '3.0 4.0 - 4.0 +', got 3.0\n";
       } else {
           cout << "2) Fail: evaluated '3.0 4.0 - 4.0 +' expecting 3.0, but got " << answer << std::endl;
           ++retval;
       }
   }
  
   {
       double answer = evaluateCountdown(std::string("3.0 4.0 - 2.0 *"));
       if (answer == -2.0) {
           cout << "3) Pass: evaluated '3.0 4.0 - 2.0 *', got -2.0\n";
       } else {
           cout << "3) Fail: evaluated '3.0 4.0 - 2.0 *' expecting -2.0, but got " << answer << std::endl;
           ++retval;
       }
   }
      
 
   {
       double answer = evaluateCountdown(std::string("100 20 / 4 +"));
       if (answer == 9) {
           cout << "4) Pass: evaluated '100 20 / 4 +', got 9\n";
       } else {
           cout << "4) Fail: evaluated '100 20 / 4 +' expecting 9, but got " << answer << std::endl;
           ++retval;
       }
   }
 
   return retval;
}

This is my output of running the tests.

1. Pass: evaluated '3.0 4.0 +', got 7.0
2. Fail: evaluated '3.0 4.0 - 4.0 +' expecting 3.0, but got -1
3. Fail: evaluated '3.0 4.0 - 2.0 *' expecting -2.0, but got -1
4. Fail: evaluated '100 20 / 4 +' expecting 9, but got 5

I can see from my results that the for loop only iterates through the first 3 elements of the vector but I'm not sure why.

Answer 1

Splitting your string works as expected, the problem is that you incorrectly manage the values on the stack. Instead of trying to re-read (and re-parse!) the values from the string vector (which might, in worst case, lead to evaluate an operator as a double, resulting in an exception) you should fetch your already parsed values from stack, apply the operator and push the result back, as follows:

double o2 = rpnStack.top();
rpnStack.pop();
double o1 = rpnStack.top();
rpnStack.pop();
rpnStack.push(o1 <op> o2);

Important at this point: As this is a stack, you pushed the first operand first and the second one last, so you need to pop in inverse order as well!

Some further issues about your code:

1. Floating point values disallow for precise math, even such a simple value like 0.1 cannot be represented exactly as it is periodic in binary, so all floating point math potentially comes with rounding issues – and in consequence you cannot compare for exact (in-) equality.
2. You don't need all those continues if you don't have anything to skip anyway – any subsequent code is wrapped in an else anyway.
3. All those unnecessary braces within main make the code pretty inconvenient to read, you should drop them. Of course answer will then be multiply defined, but that can be solved by simply dropping the declaration on the subsequent calls (double a = e(); a = e();).
4. Applying the changes above you can simplify the loop with a range based loop:
   for(auto& s : rpnStringVector) and inside the loop body evaluate s (give it another name, if you like...) instead of rpnStringVector[i].

You seem to have intended the functions being member of a class (class CountdownSolution {), actually being invalid code as you never close this class – you could profit from to avoid duplicate code and get a bit more efficient by avoiding copies:

class CountdownSolution
{
public:
    // use std::string_view so that we can operate
    // without partial copies (sub-strings!) entirely:
    double evaluate(std::string_view const& expression)
    {
        size_t posLast = 0;
        size_t pos = 0;
        while((pos = expression.find(' ', pos)) != std::string::npos)
        {
            if(expression[pos] != expression[posLast])
            {
                // evaluate immediately instead of adding to function
                doEvaluate(expression.substr(posLast, pos - posLast));
            }
            posLast = ++pos;
        }
        if(expression[posLast] != 0)
        {
            doEvaluate(expression.substr(posLast));
            posLast = ++pos;
        }
        auto result = m_stack.top();
        // clear the stack so that we can re-use the instance!
        m_stack.pop();
        return result;
    }

private:
    std::stack<double> m_stack; // make the stack a member!

    void doEvaluate(std::string_view const& token)
    {
        if(token == "+")
        {
            // structured binding - need C++17 for
            // unpacks the pair being returned to op1 and op2
            auto [op1, op2] = popOperands();
            m_stack.push(op1 + op2);
        }
        else if(token == "-")
        {
            auto [op1, op2] = popOperands();
            m_stack.push(op1 - op2);
        }
        else if(token == "*")
        {
            auto [op1, op2] = popOperands();
            m_stack.push(op1 * op2);
        }
        else if(token == "/")
        {
            auto [op1, op2] = popOperands();
            m_stack.push(op1 / op2);
        }
        else
        {
            // as using std::string_view, we cannot use std::stod
            auto end = &token.back() + 1;
            double tmp;
            // from charconv header:
            auto [last, ec] = std::from_chars(&token.front(), end, tmp);
            if(ec != std::errc() || last != end)
            {
                // invalid string!
                // best: throw an exception!

                // but assure an empty stack before so that we
                // can re-use the instance!
                // too bad there's no `clear` for...
                m_stack = std::stack<double>();

                // SHOULDN'T throw THAT but too lazy to
                // select the appropriate exceptions...
                // leaving this to you!
                // (use different ones for different errors, see
                // https://en.cppreference.com/w/cpp/utility/from_chars)
                throw ec;
            }
            m_stack.push(tmp);
        }
    }

    std::pair<double, double> popOperands()
    {
        std::pair<double, double> result;
        // as explained already: need to pop second operand first!
        result.second = m_stack.top();
        m_stack.pop();
        result.first = m_stack.top();
        m_stack.pop();
        return result;
    }
};

Admitted, having to use std::from_chars is too nice... If you don't like, you can revert the std::string_views back to std::strings (still all const references), using std::stod again. You then copy the sub-strings again, but only one at a time (and you spare the vector). But that function can throw, and you might still keep your class re-usable afterwards, so you should do:

try
{
    m_stack.push(std::stod(token));
}
catch(...) // as we are re-throwing anyway we can catch unspecifically
{
    // clearing the stack again
    // that might fail on std::bad_alloc, but then we're out anyway... 
    m_stack = std::stack<double>();

    // just re-throw:
    throw;
}

Final recommendation: Don't just copy-paste, you won't learn anything from (but if you do so, not my problem...), try to understand, then re-write on your own. Feel free to leave a comment if something is unclear ;)