C++的反向波兰符号计算器

Question

我正在尝试使用字符串作为参数，用C++编码RPN算法。 我正在使用堆栈和字符串进行读取。
我知道算法是如何工作的，但我没有得到正确的结果，我总是得到 0。这是我的代码：

#include <iostream>
#include <stack>
#include <sstream>
#include <vector>
#include <string>
using namespace std;
float RPN(string s) {
stack<int> p;
int n1, n2;
string values[s.size()];
for (unsigned int i = 0; i < s.size(); i++)
values[i] = s.at(i);
for (unsigned int i = 0; i < s.size(); i++) {
if (s.at(i) != '+' || s.at(i) != '-' || s.at(i) != '*'
|| s.at(i) != '/') {
int n;
istringstream(values[i]) >> n;
p.push(n);
}
else {
n1 = p.top();
p.pop();
n2 = p.top();
p.pop();
switch (s.at(i)) {
case '+':
p.push(n1 + n2);
break;
case '-':
p.push(n2 - n1);
break;
case '*':
p.push(n1 * n2);
break;
case '/':
p.push(n2 / n1);
break;
}
}
}
if (p.size()) {
int resul = p.top();
while (p.size())
p.pop();
return resul;
}
return 0;
}

这是调用方法：

void callRPN() {
string s1 = "56-";
string s2 = "65-";
string s3 = "843+2*-";
string s4 = "62+83-*4/";
cout << s1 << " valor: " << RPN(s1) << endl;
cout << s2 << " valor: " << RPN(s2) << endl;
cout << s3 << " valor: " << RPN(s3) << endl;
cout << s4 << " valor: " << RPN(s4) << endl;
}

控制台结果：

56- valor: 0
65- valor: 0
843+2*- valor: 0
62+83-*4/ valor: 0

我的代码中有什么错误？如果有人能帮助我，我将不胜感激。谢谢。

Answer 1

至少一个主要问题是输入无效(它们不是正确的反向波兰符号)，并且您不检查无效输入。

关于算法的几点：

int resul = p.top();
// At this point, p.size() should be 1 - it should only contain the answer.
// If it's anything other than 1, the expression you were passed is wrong
// and you should throw an exception.
while (p.size())
p.pop();

此外，在执行此操作时，您应该检查以确保堆栈上有足够的项目：

n1 = p.top();
p.pop();
n2 = p.top();
p.pop();

如果没有足够的，则应引发异常，因为这意味着输入无效。

至少某些反向波兰语表示法输入不正确，具体取决于它们的解释方式。例如，56-应该解释为5 - 6还是56 -？如果是后者，则以下内容不正确：

62+83-*4/

这实际上应该出于与上述相同的原因引发异常。尝试通过此进行跟踪;当你做62 +，例如，62加什么？在反向波兰符号中62 + 83的正确方法是62 83 +.此时，堆栈应包含145且仅包含145(这意味着此时执行-或*无效)。如果您尝试执行(62 + 83) / 4，正确的编码是：

62 83 + 4 /

目前还不清楚-*部分应该做什么，原因与我上面提到的相同。

所以，实际上，这应该验证输入。

也许更重要的是，以下内容是不正确的：

if (s.at(i) != '+' || s.at(i) != '-' || s.at(i) != '*'
|| s.at(i) != '/') {
int n;
istringstream(values[i]) >> n;
p.push(n);
}

您应该在此处将||替换为&&;如果它不是任何运算符，则希望将其推送到堆栈上。在这种情况下，它只会在不是+运算符时推送到堆栈上(这意味着，例如，如果它是-运算符，它将尝试推送到堆栈上)。