错误:deque迭代器不可解引用

Question

我正在尝试创建一个程序，将算术表达式从中缀转换为后缀形式。只要我不调用"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;
}       

Answer 1

stack使用container实现，因为stack是container adaptor，所以默认使用deque。在你的代码中可能有一行——你在空的stack上调用pop/top，这是不允许的。

trace show，错误在Token +之后。问题在这里:

   else if (token.getType() == OPERATOR)
    {
        Token topToken = stack.top();

您尝试从空stack到top，因为stack在情况下，在OPERATOR令牌之前只有NUMBER令牌，是空的。

Answer 2

您在空堆栈上调用top，只需遵循您的测试代码。

1. 从空堆栈开始
2. 如果你遇到一个VALUE，你不改变堆栈
3. 遇到OPERATOR，试图访问stack.top()

Answer 3

我也遇到过这个问题。我认为问题出在这类代码中:

    else if (token.getType() == CLOSE)
    {
        token = stack.top();
        stack.pop();
        while (token.getType() != OPEN)
        {
            postfix.push_back(token);
            token = stack.top();
            stack.pop();
        }
    }

问题是'token'是对顶部的引用，而不是副本。因此，在完成令牌处理之前，您无法弹出堆栈。在我的例子中，它通常仍然有效，因为信息仍然存在，但随后它会在奇怪的时间崩溃。你需要以一种不同的方式组织这段代码，只有在你完成'token'的工作后才会弹出。

可能是这样的:

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
}