由网友(难过了，闭眼倾听周围的声音，让自己沉浸在喧嚣中)分享简介：我正在尝试创建一个将算术表达式从中缀形式转换为后缀形式的程序.只要我不调用infixToPostFix"函数，程序就可以正常运行.但是当我尝试运行以下代码时，我得到一个崩溃和错误deque iterator not dereferenceable".我找不到任何取消引用运算符，所以我不确定出了什么问题:I'm try...

我正在尝试创建一个将算术表达式从中缀形式转换为后缀形式的程序.只要我不调用infixToPostFix"函数，程序就可以正常运行.但是当我尝试运行以下代码时，我得到一个崩溃和错误deque iterator not dereferenceable".我找不到任何取消引用运算符，所以我不确定出了什么问题:

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:

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

推荐答案

stack 是使用 container 实现的，因为 stack 是 容器适配器，默认使用deque.可能在您的代码的一行中 - 您在空 stack 上调用 pop/top，这是不允许的.

stack is implemented using container, since stack is container adaptor, by default deque is used. In probably one line of your code - you call pop/top on empty stack, that is not allowed.

trace 显示，该错误在 Token + 之后.问题就在这里:

trace show, that error is after Token +. Problem is here:

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

您尝试从空 stack 中 top，因为 stack 以防万一，之前只有 NUMBER 标记OPERATOR 令牌，为空.

You try to top from empty stack, since stack in case, where is only NUMBER token before OPERATOR token, is empty.