custom made queue/stack - having problems

[JAGgededgeOB172]

Hi,

I'm having issues with a program that concept-wise sounds very simple. The program should read in data from a text file (attached a2.txt), and perform stack and queue operations upon the data. The data consists of long math problems, dealing with order-of-operations.

The correct output that should be appearing is attached as "Correct_Output".
The incorrect output that I keep getting now is attached as "Incorrect_Output".

The reason I have a proper output, is because, at one point I had a working program that utilized the built-in stacks & queues of C++.

The program has been modified to use my own created stacks & queues - this is when I am getting an incorrect output now. Therefore I believe I have a problem with my own created stacks and queue, but I can't tell what's wrong with them. (I need my own stacks and queues because it's for a college class, otherwise I'd be done already :)).

Thank you very much for your time.

And here of course is my code as of now.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <ctype.h>
#include <cmath>

using namespace std;

const int SIZE = 255;

class charqueue
{
private:
    char queue[SIZE];
    char start, end;
public:
    charqueue();
    void push(char &input);
    void pop();
    bool empty();
    char front();
    int size();
};
    charqueue::charqueue()
    {
        end = 0;
        start = end;
        for(int count = 0; count < SIZE; count++)
            queue[count] = 0;
    }
    void charqueue::push(char &input)
    {
        int end_test = end + 1;
        if(end_test == start || (end_test == SIZE && start == 0))
        {
            //cout << "Queue is full." << endl;
            return;
        }
        end++;
        if(end == SIZE)
            end = 0; // cycle around
        queue[end] = input;
    }
    void charqueue::pop()
    {
        if(start == end)
        {
            //cout << "Queue is empty." << endl;
            return;                    // or some other error indicator
        }
        start++;
        if(start == SIZE)
            start = 0;       // cycle around
        return;
    }
    bool charqueue::empty()
    {
        if(start == end)
            return (true);
        else
            return (false);
    }
    char charqueue::front()
    {
        char front;
        front = queue[start];
        return (front);
    }
    int charqueue::size()
    {
        int test;
        if(start < end)
        {
            test = end - start;
            test += 1;
            return (test);
        }
        else if(end < start)
        {
            test = start - end;
            test = SIZE - test;
            test += 1;
            return (test);
        }
        else
            return 0;
    }

class charstack
{
private:
    char stack[SIZE];
    int stack_top;
public:
    charstack();
    void push(char &s);
    void pop();
    bool empty();
    char top();
};
    charstack::charstack()
    {
        stack_top = 0;
        for(int count_1 = 0; count_1 < SIZE; count_1++)
            stack[count_1] = 0;
    }
    void charstack::push(char &s)
    {
        int stack_test = stack_top + 1;
        if(stack_test == SIZE)
        {
            //cout << "Stack is full." << endl;
            return;
        }
        stack[stack_top] = s;
        stack_top++;
        return;
    }
    void charstack::pop()
    {
        if(stack_top == 0)
        {
            //cout << "Stack underflow." << endl;
            return;
        }
        stack_top--;
        return;
    }
    bool charstack::empty()
    {
        if(stack_top == 0)
            return true;
        else
            return false;
    }
    char charstack::top()
    {
        if(stack_top == 0)
        {
            //cout << "Stack is empty." << endl;
            return 0;
        }
        char top;
        top = stack[stack_top];
        return (top);
    }
    
class floatstack
{
private:
    float fltstack[SIZE];
    int stack_top_flt;
public:
    floatstack();
    void push(float &f);
    void pop();
    bool empty();
    float top();
};
    floatstack::floatstack()
    {
        stack_top_flt = 0;
        for(int count_2 = 0; count_2 < SIZE; count_2++)
            fltstack[count_2] = 0;
    }
    void floatstack::push(float &f)
    {
        if(stack_top_flt == SIZE)
        {
            //cout << "Stack is full." << endl;
            return;
        }
        fltstack[stack_top_flt] = f;
        stack_top_flt++;
        return;
    }
    void floatstack::pop()
    {
        if(stack_top_flt == 0)
        {
            //cout << "Stack underflow." << endl;
            return;
        }
        stack_top_flt--;
        return;
    }
    bool floatstack::empty()
    {
        if(stack_top_flt == 0)
            return true;
        else
            return false;
    }
    float floatstack::top()
    {
        if(stack_top_flt == 0)
        {
            //cout << "Stack is empty." << endl;
            return 0;
        }
        int top;
        top = fltstack[stack_top_flt];
        return (top);
    }

charqueue INFIX_TO_POSTFIX(ifstream &, char []);
float EVALUATE_POSTFIX(charqueue &);
int precedence(char);

int main()
{
    ifstream inFile;
    inFile.open("a2.txt"); //attempts to open read file, and tests for existance
    if(inFile.is_open())
           cout << "File Exists." << endl << endl;
    else
           cout << "File does not exist." << endl << endl;
           
    charqueue bigqueue;
    char dataary[SIZE] = {0};
    float total_count[SIZE] = {0};
    int count_3 = 0;
    float sum = 0;
    
    while(!inFile.eof())
    {       
        bigqueue = INFIX_TO_POSTFIX(inFile, dataary);   //Function call
        total_count[count_3] = EVALUATE_POSTFIX(bigqueue);
        count_3++;
    }
    for(int count_loop = 0; count_loop < count_3; count_loop++)
        sum += total_count[count_loop];

    cout << "The answers for each math problem all add up to: " << sum << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

charqueue INFIX_TO_POSTFIX(ifstream &Filein, char *dataarray) //function, Filein is just the name of my text file read stream
{
    
    charstack prestack;
    charqueue prequeue;

    string data;  //string created to store the input read line
    getline(Filein, data);    //program reads file, stores read line as the string, data
    cout << "The original infix expression is: " << data << endl; //output read string
    int arrayLength = data.length();  //set a counter
    char temp;    //temporary variable
      
    for(int i = 0; i < arrayLength; i++) //for loop set up to step through the character array, one character at a time
    {
          dataarray[i] = data[i]; //Here's the key line, I equate each position in the string to equate to the character array

          if(isdigit(dataarray[i]))   //Here on out is where the processing of the character array begins....
              prequeue.push(dataarray[i]);//output content(Next) to Queue;
                
          else if(dataarray[i] == '(')
              prestack.push(dataarray[i]);
                
          else if(dataarray[i] == ')')
          {
              if(prestack.empty() == false)
              {
                  while(prestack.top() != '(')
                  {
                      temp = prestack.top();
                      prequeue.push(temp);
                      prestack.pop();
                      if(prestack.empty() == true)
                      {
                          break;
                      }                              //POP the content in Stack to Queue until “(“ is reached,
                  }
              }
              prestack.pop();                                             //POP it but not to Queue; break;
          }
         
          else if(dataarray[i] == '+' || '-' || '*' || '/' || '^')
          {
              if(prestack.empty() == false)
              {
                  while(precedence(prestack.top()) >= precedence(dataarray[i]))                      //while(PRE(TOP) >= PRE(Next))
                  {
                      temp = prestack.top();
                      prequeue.push(temp);
                      prestack.pop();
                      if(prestack.empty() == true)
                      {
                          break;
                      }
                  }
              }
              prestack.push(dataarray[i]);
          }
          
          else
              cout << "There was an error in the operation, please restart." << endl;
    }
      
    while(prestack.empty() == false)                                            //while(PRE(TOP) >= PRE(Next))
    {
          temp = prestack.top();
          prequeue.push(temp);
          prestack.pop();
    }
    return prequeue;
}

int precedence(char swap)
{
    int compare;
    switch(swap)
    {
        case '^': compare = 3;
        break;
        case '/': 
        case '*': compare = 2;
        break;
        case '+':
        case '-': compare = 1;
        break;
        case '(':
        case ')': compare = 0;
        break;
    }
    return compare;
}

float EVALUATE_POSTFIX(charqueue &postqueue)
{
    floatstack poststack;
    int queueLength;
    char var[1];
    float temp, var_1, temp1, temp2, final;
    queueLength = postqueue.size();
    cout << "The converted infix expression is: ";

    for(int count = 0; count < queueLength; count++)
    {   
        cout << postqueue.front();
        if(isdigit(postqueue.front()))
        {
            var[0] = postqueue.front();
            var_1 = atof(var);
            poststack.push(var_1);
        }

        else if(postqueue.front() == '+' || '-' || '*' || '/' || '^')
        {
            temp2 = poststack.top();
            poststack.pop();
            temp1 = poststack.top();
            poststack.pop();
            switch(postqueue.front())
            {
                case '+': temp = temp1 + temp2;
                    break;
                case '-': temp = temp1 - temp2;
                    break;
                case '*': temp = temp1 * temp2;
                    break;
                case '/': temp = temp1 / temp2;
                    break;
                case '^': temp = pow(temp1, temp2);
                    break;
                default: cout << "There was a glitch in the operation, press any key to terminate.";
            }
            poststack.push(temp);
        }
        postqueue.pop();
    }
    final = poststack.top();
    cout << endl << "The postfix operation answer is: " << final << endl << endl;
    return final;
}

[Salem]

> else if(postqueue.front() == '+' || '-' || '*' || '/' || '^')
Nope, try again.
Yes it's valid code, but it sure doesn't do what you want it to do.

[JAGgededgeOB172]

Ok, I've updated my code and scrapped the array design I was using in my classes. I am now using linked lists to manage my stack and queue (I have two stack classes, but the only thing different between them are data types I'm pushing to them (char, float, etc)).

My output now is cleaner, but still incorrect, I'm just getting a bunch of '+' signs or '/' signs now (see Incorrect_output.jpg) I should also note that I'm outputting the correct number of outputs, but again they're all '+' signs. Again I'm thinking something is wrong with my classes, but I still don't see it now.

I'll reattach everything necessary for convenience.

Thanks for your time!

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <ctype.h>
#include <cmath>

using namespace std;

const int SIZE = 100;

struct charnode
{
    char value;
    float flt_value;
    charnode *next;
};

class charqueue
{
private:
    charnode *temp, *temp1, *temp2;
    charnode *head;
    int test;
public:
    charqueue();
    void push(char input);
    void pop();
    bool empty();
    char front();
    int size();
};
    charqueue::charqueue()
    {
        head = NULL;
    }
    void charqueue::push(char input)
    {
        temp = new charnode;
        temp->value = input;
        temp->flt_value = 0;
        temp->next = NULL;
        if(head == NULL)
            head = temp;
        else
        {
            temp1 = head;
            while(temp1->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1 = temp1->next;
            }
            temp1->next = temp;
        }
        return;
    }
    void charqueue::pop()
    {
        temp = head;
        head = head->next;
        delete temp;
        return;
    }
    bool charqueue::empty()
    {
        if(head == NULL)
            return (true);
        else
            return (false);
    }
    char charqueue::front()
    {
        if(head == NULL)    //linked list gets created as a1.txt is read from
            return 0;
        else
        {
            temp1 = head;
            while(temp1->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1 = temp1->next;
            }
        }
        return (temp1->value);
    }
    int charqueue::size()
    {
        if(head == NULL)    //linked list gets created as a1.txt is read from
            return 0;
        else
        {
            test = 1;
            temp1 = head;
            while(temp1->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1 = temp1->next;
                test++;
            }
        }
        return (test);
    }

class charstack
{
private:
    charnode *temp_chrstck, *temp1_chrstck, *temp2_chrstck;
    charnode *head_chrstck;
public:
    charstack();
    void push(char &s);
    void pop();
    bool empty();
    char top();
};
    charstack::charstack()
    {
        head_chrstck = NULL;
    }
    void charstack::push(char &s)
    {
        temp_chrstck = new charnode;
        temp_chrstck->value = s;
        temp_chrstck->flt_value = 0;
        temp_chrstck->next = NULL;
        if(head_chrstck == NULL)
            head_chrstck = temp_chrstck;
        else
        {
            temp1_chrstck = head_chrstck;
            while(temp1_chrstck->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1_chrstck = temp1_chrstck->next;
            }
            temp1_chrstck->next = temp_chrstck;
        }
        return;
    }
    void charstack::pop()
    {
        if(head_chrstck == NULL)
           return;
        else
        {
            temp1_chrstck = head_chrstck;
            if(temp1_chrstck->next == NULL)
            {
                delete temp1_chrstck;
                head_chrstck = NULL;
            }
            else
            {
                while(temp1_chrstck->next != NULL)
                {
                    temp2_chrstck = temp1_chrstck;
                    temp1_chrstck = temp1_chrstck->next;
                }
            delete temp1_chrstck;
            temp2_chrstck->next = NULL;
            }
        }
        return;
    }
    bool charstack::empty()
    {
        if(head_chrstck == NULL)
            return true;
        else
            return false;
    }
    char charstack::top()
    {
        if(head_chrstck == NULL)    //linked list gets created as a1.txt is read from
            return 0;
        else
        {
            temp1_chrstck = head_chrstck;
            while(temp1_chrstck->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1_chrstck = temp1_chrstck->next;
            }
        }
        return (temp1_chrstck->value);
    }
    
class floatstack
{
private:
    charnode *temp_fltstck, *temp1_fltstck, *temp2_fltstck;
    charnode *head_fltstck;
public:
    floatstack();
    void push(float &f);
    void pop();
    bool empty();
    float top();
};
    floatstack::floatstack()
    {
        head_fltstck = NULL;
    }
    void floatstack::push(float &f)
    {
        temp_fltstck = new charnode;
        temp_fltstck->flt_value = f;
        temp_fltstck->value = 0;
        temp_fltstck->next = NULL;
        if(head_fltstck == NULL)
            head_fltstck = temp_fltstck;
        else
        {
            temp1_fltstck = head_fltstck;
            while(temp1_fltstck->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1_fltstck = temp1_fltstck->next;
            }
            temp1_fltstck->next = temp_fltstck;
        }
        return;
    }
    void floatstack::pop()
    {
        if(head_fltstck == NULL)
           return;
        else
        {
            temp1_fltstck = head_fltstck;
            if(temp1_fltstck->next == NULL)
            {
                delete temp1_fltstck;
                head_fltstck = NULL;
            }
            else
            {
                while(temp1_fltstck->next != NULL)
                {
                    temp2_fltstck = temp1_fltstck;
                    temp1_fltstck = temp1_fltstck->next;
                }
            delete temp1_fltstck;
            temp2_fltstck->next = NULL;
            }
        }
        return;
    }
    bool floatstack::empty()
    {
        if(head_fltstck == NULL)
            return true;
        else
            return false;
    }
    float floatstack::top()
    {
        if(head_fltstck == NULL)    //linked list gets created as a1.txt is read from
            return 0;
        else
        {
            temp1_fltstck = head_fltstck;
            while(temp1_fltstck->next != NULL)     //loops to step through the linked list as it gets created
            {
                temp1_fltstck = temp1_fltstck->next;
            }
        }
        return (temp1_fltstck->flt_value);
    }

charqueue INFIX_TO_POSTFIX(ifstream &, char []);
float EVALUATE_POSTFIX(charqueue &);
int precedence(char);

int main()
{
    ifstream inFile;
    inFile.open("a2.txt"); //attempts to open read file, and tests for existance
    if(inFile.is_open())
           cout << "File Exists." << endl << endl;
    else
           cout << "File does not exist." << endl << endl;

    charqueue bigqueue;
    char dataary[SIZE] = {0};
    float total_count[SIZE] = {0};
    int count_3 = 0;
    float sum = 0;
    
    while(!inFile.eof())
    {       
        bigqueue = INFIX_TO_POSTFIX(inFile, dataary);   //Function call
        total_count[count_3] = EVALUATE_POSTFIX(bigqueue);
        count_3++;
    }
    for(int count_loop = 0; count_loop < count_3; count_loop++)
        sum += total_count[count_loop];

    cout << "The answers for each math problem all add up to: " << sum << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

charqueue INFIX_TO_POSTFIX(ifstream &Filein, char *dataarray) //function, Filein is just the name of my text file read stream
{
    charstack prestack;
    charqueue prequeue;
    
    string data;  //string created to store the input read line
    getline(Filein, data);    //program reads file, stores read line as the string, data
    cout << "The original infix expression is: " << data << endl; //output read string
    int arrayLength = data.length();  //set a counter
    char dummy;    //temporary variable
      
    for(int i = 0; i < arrayLength; i++) //for loop set up to step through the character array, one character at a time
    {   
          dataarray[i] = data[i]; //Here's the key line, I equate each position in the string to equate to the character array

          if(isdigit(dataarray[i]))   //Here on out is where the processing of the character array begins....
              prequeue.push(dataarray[i]);//output content(Next) to Queue;
                
          else if(dataarray[i] == '(')
              prestack.push(dataarray[i]);
                
          else if(dataarray[i] == ')')
          {
              if(prestack.empty() == false)
              {
                  while(prestack.top() != '(')
                  {
                      dummy = prestack.top();
                      prequeue.push(dummy);
                      prestack.pop();
                      if(prestack.empty() == true)
                          break;
                  }
              }
              prestack.pop();                                             //POP it but not to Queue; break;
          }
         
          else
          {
              if(prestack.empty() == false)
              {
                  while(precedence(prestack.top()) >= precedence(dataarray[i]))                      //while(PRE(TOP) >= PRE(Next))
                  {
                      dummy = prestack.top();
                      prequeue.push(dummy);
                      prestack.pop();
                      if(prestack.empty() == true)
                          break;
                  }
              }
              prestack.push(dataarray[i]);
          }
    }
      
    while(prestack.empty() == false)                                            //while(PRE(TOP) >= PRE(Next))
    {
          dummy = prestack.top();
          prequeue.push(dummy);
          prestack.pop();
    }
    return (prequeue);
}

int precedence(char swap)
{
    int compare;
    switch(swap)
    {
        case '^': compare = 3;
        break;
        case '/': 
        case '*': compare = 2;
        break;
        case '+':
        case '-': compare = 1;
        break;
        case '(':
        case ')': compare = 0;
        break;
    }
    return (compare);
}

float EVALUATE_POSTFIX(charqueue &postqueue)
{
    floatstack poststack;
    int queueLength;
    char var[1];
    float sub, var_1, sub1, sub2, final;
    queueLength = postqueue.size();
    cout << "The converted infix expression is: ";

    for(int j = 0; j < queueLength; j++)
    {   
        cout << postqueue.front();
        if(isdigit(postqueue.front()))
        {
            var[0] = postqueue.front();
            var_1 = atof(var);
            poststack.push(var_1);
        }
        
        else
        {
            sub2 = poststack.top();
            poststack.pop();
            sub1 = poststack.top();
            poststack.pop();
            switch(postqueue.front())
            {
                case '+': sub = sub1 + sub2;
                    break;
                case '-': sub = sub1 - sub2;
                    break;
                case '*': sub = sub1 * sub2;
                    break;
                case '/': sub = sub1 / sub2;
                    break;
                case '^': sub = pow(sub1, sub2);
                    break;
                default: cout << "There was a glitch in the operation, press any key to terminate.";
            }
            poststack.push(sub);
        }
        postqueue.pop();
    }
    final = poststack.top();
    cout << endl << "The postfix operation answer is: " << final << endl << endl;
    return final;
}

[JAGgededgeOB172]

I just figured it out, my queue.front function was not working properly. Thank you for taking time to respond to my thread Salem.

I will now close this thread.....