Search code examples
c++iteratorqueue

Why did the queue stop traversing at the median element?

When I try to check the correction of my postfix expression, the output values performed disrupted at the middle of the elements in the queue. There is not any reminders from the IDE but it is certain that some problems exist within my code. Why did it happen?

This is my test code:

int main(){
    op['('] = 0;
    op['+'] = op['-'] = 1;
    op['*'] = op['/'] = 2;
    while(getline(cin,str),str != "0"){//save the nifix expression
        for(string::iterator it = str.begin();it != str.end();it++){//checking progress
            if(*it == ' ') str.erase(it);
        }
        while(!s.empty()) s.pop();
        Change();
        /*printf("%d.2f\n",Cal());*/
        node t;
        printf("%d\n",q.size());
        for(int i = 0;i<q.size() && !q.empty();i++){
            t = q.front();
            if(t.flag == true){
                printf("%.0f ",t.num);
            }else{
                printf("%c ",t.op);
            }
            printf("%d\n",q.size());
                q.pop();
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

And this is my screenshot of the input expression and output value: the output values

Solution

  • Lets start with a complete, but simple example with the same loop logic:

    #include <iostream>
#include <queue>
using namespace std;
int main()
{
    //Make a queue
    queue<int> q;
    // put a few items in it
    for (int count = 1 ; count < 6; count++) q.push(count);

    // run asker's logic
    for (int index = 0; index < q.size() && !q.empty(); index++)
    {
        cout << "Index: " << index << ',' << " Queue size: " << q.size() << endl;
        q.pop();
    }
    return 0;
}

    This gives the following output:

    Index: 0, Queue size: 5
Index: 1, Queue size: 4
Index: 2, Queue size: 3

    From this we can see as the loop runs the index goes up and the size of the queue goes down. They meet at the middle and the loop stops.

    Simple solution: Get rid of the index and loop until empty.

    #include <iostream>
#include <queue>
using namespace std;
int main()
{
    //Make a queue
    queue<int> q;
    // put a few items in it
    for (int count = 1 ; count < 6; count++) q.push(count);

    // run asker's logic
    for (int index = 0; !q.empty(); index++)
    {
        cout << "index: " << index << ',' << " Queue size: " << q.size() << endl;
        q.pop();
    }
    return 0;
}

    Now the output is

    index: 0, Queue size: 5
index: 1, Queue size: 4
index: 2, Queue size: 3
index: 3, Queue size: 2
index: 4, Queue size: 1

    And we can simplify things further because we don't give a crap about the index at all

    #include <iostream>
#include <queue>
using namespace std;
int main()
{
    //Make a queue
    queue<int> q;
    // put a few items in it
    for (int count = 1 ; count < 6; count++) q.push(count);

    // run asker's logic
    while (!q.empty())
    {
        cout << "Queue size: " << q.size() << endl;
        q.pop();
    }
    return 0;
}