C++ 中的反向波兰表示法

Question

我目前正在尝试为作业编写 RPN 计算器，但遇到了一些问题。方法 evaluateCountdown 旨在接收一个字符串，该字符串包含以逆波兰表示法编写的数学表达式，它意味着 return 将表达式计算为双精度的结果。

例如：字符串“3.0 4.0 + 2.0 *”应该 return 14.0 作为双精度值。

#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();
   }
}

在以下 4 项测试中，我只通过了 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;
}

这是我运行测试的输出。

通过：评估'3.0 4.0 +'，得到7.0
失败：评估为“3.0 4.0 - 4.0 +”，预期为 3.0，但得到 -1
失败：评估“3.0 4.0 - 2.0 *”期望 -2.0，但得到 -1
失败：评估为“100 20 / 4 +”，预期为 9，但得到 5

我从我的结果中可以看出，for 循环只遍历向量的前 3 个元素，但我不确定为什么。

Answer 1

拆分字符串按预期工作，问题是您错误地管理了堆栈上的值。与其尝试重新读取（并重新解析！）字符串向量中的值（在最坏的情况下，这可能会导致将运算符评估为双精度值，从而导致异常），您应该从中获取已解析的值堆栈，应用运算符并将结果推回，如下：

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

此时重要：因为这是一个堆栈，你先压入第一个操作数，最后压入第二个操作数，所以你也需要以相反的顺序弹出！

关于您的代码的一些其他问题：

浮点值不允许进行精确的数学运算，即使像 0.1 这样简单的值也不能精确表示，因为它在二进制中是周期性的，因此所有浮点数学运算都可能存在舍入问题——因此您 cannot compare for exact (in-) equality.
如果您没有任何可跳过的内容，则不需要所有这些 continues – 无论如何，任何后续代码都包含在 else 中。
main 中所有那些不必要的大括号使代码阅读起来非常不方便，您应该删除它们。当然 answer 将被多次定义，但这可以通过简单地在后续调用中删除声明来解决（double a = e(); a = e();）。
应用上面的更改，您可以使用基于范围的循环来简化循环：
for(auto& s : rpnStringVector) 并在循环体内评估 s（如果您愿意，可以给它另一个名称...) 而不是 rpnStringVector[i].

您似乎打算将函数作为 class (class CountdownSolution {) 的成员，实际上是无效代码，因为您永远不会关闭此 class – 您可以从中获利以避免重复代码并通过避免复制来提高效率：

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;
    }
};

承认，必须使用 std::from_chars 太好了...如果您不喜欢，可以将 std::string_view 恢复为 std::string（仍然是所有 const 参考），再次使用 std::stod。然后再次复制子字符串，但一次只复制一个（并且保留向量）。但是该函数可能会抛出异常，并且您之后可能仍会保持 class 可重用，因此您应该这样做：

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;
}

最终建议：不要只是复制粘贴，你不会从中学到任何东西（但如果你这样做，不是我的问题......），试着理解，然后自己重新写。如果不清楚，请随时发表评论；）

C++ 中的反向波兰表示法

Reverse Polish Notation in C++

c++

stack

rpn

vector

calculator