C++ 错误：deque 迭代器不可解引用
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16977349/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Error: deque iterator not dereferenceable
提问by user1824518
I'm trying to create a program that converts an arithmetic expression from infix to postfix form. As long as I don't call the "infixToPostFix" function, the program runs fine. But when I try to run the following code, I get a crash and error "deque iterator not dereferenceable". I can't find any dereferencing operators, so I'm not sure what's wrong:
我正在尝试创建一个程序，将算术表达式从中缀形式转换为后缀形式。只要我不调用“infixToPostFix”函数，程序就可以正常运行。但是，当我尝试运行以下代码时，出现崩溃和错误“deque iterator not dereferenceable”。我找不到任何解引用运算符，所以我不确定出了什么问题：
// infixToPostfixTest.cpp
#include "Token.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// infix to postfix function prototype
void infixToPostfix(vector<Token> &infix, vector<Token> &postfix);
// priority function prototype
int priority(Token & t);
// printing a Token vector
void printTokenVector(vector<Token> & tvec);
int main() {
// Experiment
//--------------------------------------------------
vector<Token> infix;
// a + b * c - d / e % f
//
infix.push_back(Token(VALUE,5.0)); // a
infix.push_back(Token(OPERATOR,'+'));
infix.push_back(Token(VALUE,6.0)); // b
infix.push_back(Token(OPERATOR,'*'));
infix.push_back(Token(VALUE,7.0)); // c
cout << "Infix expression: ";
printTokenVector(infix);
vector<Token> postfix; // create empty postfix vector
infixToPostfix(infix, postfix); // call inToPost to fill up postfix vector from infix vector
cout << "Postfix expression: ";
printTokenVector(postfix);
cout << endl << endl;
return 0;
}
// printing a Token vector
void printTokenVector(vector<Token> & tvec)
{
int size = tvec.size();
for (int i = 0; i < size; i++) {
cout << tvec[i] << " ";
}
cout << endl;
}
int priority(Token & t) // assumes t.ttype is OPERATOR, OPEN, CLOSE, or END
{
char c = t.getChar();
char tt = t.getType();
if (c == '*' || c == '/')
return 2;
else if (c == '+' || c == '-')
return 1;
else if (tt == OPEN)
return 0;
else if (tt == END)
return -1;
else
return -2;
}
void infixToPostfix(vector<Token> &infix, vector<Token> &postfix)
{
stack<Token> stack;
postfix.push_back(END);
int looper = 0;
int size = infix.size();
while(looper < size) {
Token token = infix[looper];
if (token.getType() == OPEN)
{
stack.push(token);
}
else if (token.getType() == CLOSE)
{
token = stack.top();
stack.pop();
while (token.getType() != OPEN)
{
postfix.push_back(token);
token = stack.top();
stack.pop();
}
}
else if (token.getType() == OPERATOR)
{
Token topToken = stack.top();
while ((!stack.empty()) && (priority(token) <= priority(topToken)))
{
Token tokenOut = stack.top();
stack.pop();
postfix.push_back(tokenOut);
topToken = stack.top();
}
stack.push(token);
}
else if (token.getType() == VALUE)
{
postfix.push_back(token);
}
else
{
cout << "Error! Invalid token type.";
}
looper = looper + 1;
}
while (!stack.empty())
{
Token token = stack.top();
stack.pop();
postfix.push_back(token);
}
}
//Token.h
#ifndef TOKEN_H
#define TOKEN_H
#include <iostream>
using namespace std;
enum TokenType { OPEN, CLOSE, OPERATOR, VARIABLE, VALUE, END };
class Token {
public:
Token (TokenType t, char c) : ttype(t), ch(c) { }
Token (TokenType t, double d) : ttype(t), number(d) { }
Token (TokenType t) : ttype(t) { }
Token () : ttype (END), ch('?'), number(-99999999) { }
TokenType getType() {return ttype;}
char getChar() {return ch;}
double getNumber() {return number;}
private:
TokenType ttype;
char ch;
double number;
};
ostream & operator << (ostream & os, Token & t) {
switch (t.getType()) {
case OPEN:
os << "("; break;
case CLOSE:
os << ")"; break;
case OPERATOR:
os << t.getChar(); break;
case VARIABLE:
os << t.getChar(); break;
case VALUE:
os << t.getNumber(); break;
case END:
os << "END" ; break;
default: os << "UNKNOWN";
}
return os;
}
回答by ForEveR
stackis implemented using container, since stackis container adaptor, by default dequeis used. In probably one line of your code - you call pop/topon empty stack, that is not allowed.
stack是使用 实现的container，因为stack是container adaptor，默认情况下deque使用。在您的代码中可能有一行 - 您调用pop/topempty stack，这是不允许的。
traceshow, that error is after Token +.
Problem is here:
trace显示，该错误是在Token +. 问题在这里：
else if (token.getType() == OPERATOR)
{
Token topToken = stack.top();
You try to topfrom empty stack, since stackin case, where is only NUMBERtoken before OPERATORtoken, is empty.
您尝试topfrom empty stack，因为stack如果只有NUMBERtoken 之前的OPERATORtoken 是空的。
回答by themel
You are calling top on empty stack, just follow the code for your test.
您正在空堆栈上调用 top ，只需按照测试代码进行操作即可。
- you start with an empty stack
- you encounter a VALUE, you don't change stack
- you encounter an OPERATOR and attempt to access stack.top()
- 你从一个空栈开始
- 你遇到一个 VALUE，你不改变堆栈
- 你遇到一个 OPERATOR 并试图访问 stack.top()
回答by Jiminion
I ran into this problem too. I think the problem is in this sort of code:
我也遇到了这个问题。我认为问题出在这种代码中：
else if (token.getType() == CLOSE)
{
token = stack.top();
stack.pop();
while (token.getType() != OPEN)
{
postfix.push_back(token);
token = stack.top();
stack.pop();
}
}
The problem is that 'token' is a reference to the top, not a copy. So you can't pop the stack until you are done working with token. In my case, it often still worked because the information was still present, but then it would crash at weird times. You need to organize this code in a different way to pop only after you done working with 'token'.
问题是“令牌”是对顶部的引用，而不是副本。因此，在完成使用令牌之前，您无法弹出堆栈。就我而言，它通常仍然有效，因为信息仍然存在，但它会在奇怪的时间崩溃。您需要以不同的方式组织此代码以仅在您完成使用“令牌”后才能弹出。
Maybe something like:
也许是这样的：
else if (token.getType() == CLOSE)
{
token = stack.top();
Token saveToken = new Token(token); // Or something like this...
stack.pop();
while (saveToken.getType() != OPEN)
{
postfix.push_back(saveToken);
token = stack.top();
delete saveToken; // ugh
Token saveToken = new Token(token);
stack.pop();
}
delete saveToken; //ugh
}
