Stack Program

[Orion98]

I'm currently writing a program where it guesses whether or not the given series of operations and corresponding return values from an input file are operating as a stack. In other words, the output is fully determined by the input file.

The text file (StackTest.txt):

4
INSERT 2
INSERT 1
REMOVE 1
REMOVE 2
6
INSERT 5
INSERT 10
INSERT 12
REMOVE 10
REMOVE 5
REMOVE 12
2
INSERT 8
REMOVE 8

However, I'm stuck on how to implement this feature into my current code.

The code I wrote so far takes individual input for the stack. It outputs what value is being inserted and removed while it shows whether or not the stack is empty, shows the top value of the stack and the stack size in the end.

If anyone can help me out on how to achieve the expected output below. I would really appreciate it!

My Code:

#include <iostream>
#include <cstdlib>
using namespace std;

// define default capacity of the stack
#define SIZE 10

// Class for stack
class stack
{
	int *arr;
	int top;
	int capacity;

public:
	stack(int size = SIZE); 	// constructor
	~stack();   				// destructor

	void push(int);
	int pop();
	int peek();

	int size();
	bool isEmpty();
	bool isFull();
};

// Constructor to initialize stack
stack::stack(int size)
{
	arr = new int[size];
	capacity = size;
	top = -1;
}

// Destructor to free memory allocated to the stack
stack::~stack()
{
	delete arr;
}

// Utility function to add an element x in the stack
void stack::push(int x)
{
	if (isFull())
	{
		cout << "OverFlow\nProgram Terminated\n";
		exit(EXIT_FAILURE);
	}

	cout << "INSERT " << x << endl;
	arr[++top] = x;
}

// Utility function to pop top element from the stack
int stack::pop()
{
	// check for stack underflow
	if (isEmpty())
	{
		cout << "UnderFlow\nProgram Terminated\n";
		exit(EXIT_FAILURE);
	}

	cout << "REMOVE " << peek() << endl;

	// decrease stack size by 1 and (optionally) return the popped element
	return arr[top--];
}

// Utility function to return top element in a stack
int stack::peek()
{
	if (!isEmpty())
		return arr[top];
	else
		exit(EXIT_FAILURE);
}

// Utility function to return the size of the stack
int stack::size()
{
	return top + 1;
}

// Utility function to check if the stack is empty or not
bool stack::isEmpty()
{
	return top == -1;	// or return size() == 0;
}

// Utility function to check if the stack is full or not
bool stack::isFull()
{
	return top == capacity - 1;	// or return size() == capacity;
}

// main function
int main()
{
	stack pt(4);

	pt.push(5);
	pt.push(10);
	pt.push(12);
	pt.push(3);

	pt.pop();
    pt.pop();
    pt.pop();

	if (pt.isEmpty())
		cout << "Stack is empty\n";
	else
		cout << "Stack is not empty\n";

    cout << endl;
    cout << "Top element is: " << pt.peek() << endl;
	cout << "Stack size is " << pt.size() << endl;

	return 0;
}

Current Output:

INSERT 5
INSERT 10
INSERT 12
INSERT 3
REMOVE 3
REMOVE 12
REMOVE 10
Stack is not empty

Top element is: 5
Stack size is 1

Expected Output(from input file):

stack
not stack
stack

[Enoizat]

Orion98, is this an assignment/homework?

A stack is a ‘LIFO’ (Last In, First Out) container. It means you can only remove items in an order which is the reverse of the inserting one.

To fulfil the requirements, you need to add a method which asks for the element to remove and check if it is the following one on the top. If the two values don’t match, than the requested behaviour doesn’t belong to stacks.

Please be careful with “using namespace std”: you’ve named your class “stack”.

[dhayden]

Your stack class looks good but I think you're using it wrong. When reading the input, if you see "INSERT" then you should push the value that follows it. If you see "REMOVE" then pop a value from the stack and compare it to the value that follows REMOVE in the input file. If they compare equal then it looks like a stack so far. Otherwise the input file does not represent a stack and you should just read the rest of the lines.

[Orion98]

I've been playing around with my code based on help from you guys @dhayden and @Enoizat, I think I understood where you guys were going, but I haven't achieved anything.

Original Code

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
using namespace std;

int main()
{
    ifstream inFile;
    string data;
    string command;
    int item;

    inFile.open("StackTest.txt");
    //cout << "Reading file..." << endl;

    stack <int> st;

    while(getline(inFile, data))
    {
        //cout << data << endl;

        inFile >> command;

        if(command == "INSERT")
        {
            /***/
            inFile >> item;
            st.push(item);

            //cout << item << " Pushed into stack" << endl;
        }
        else if(command == "REMOVE")
        {
            /***/
            st.pop();

            //cout << item << " Popped from stack" << endl;
        }
    }

    inFile.close();
}

However, I made another program that was able to validate a stack sequence, but only on input in the code, not from an input file.

New Code

#include <iostream>
#include <stack>
using namespace std;

bool validStackSeq(int pushed[], int popped[], int len)
{
    int j = 0;

    stack <int> pt;
    for(int i = 0; i < len; i++)
    {
        pt.push(pushed[i]);

        while (!pt.empty() && j < len && pt.top() == popped[j])
        {
            pt.pop();
            j++;
        }
    }

    return j == len;
}

int main()
{
   int pushed[] = {2, 1};
   int popped[] = {1, 2};
   int len = sizeof(pushed)/sizeof(pushed[0]);

   int pushed1[] = {5, 10, 12};
   int popped1[] = {12, 5, 10};
   int len1 = sizeof(pushed1)/sizeof(pushed1[0]);

   int pushed2[] = {8};
   int popped2[] = {8};
   int len2 = sizeof(pushed2)/sizeof(pushed2[0]);

   int pushed3[] = {1, 4};
   int popped3[] = {4};
   int len3 = sizeof(pushed3)/sizeof(pushed3[0]);

   cout << (validStackSeq(pushed, popped, len) ? "Stack" : "Not Stack") << endl;

   cout << (validStackSeq(pushed1, popped1, len1) ? "Stack" : "Not Stack") << endl;

   cout << (validStackSeq(pushed2, popped2, len2) ? "Stack" : "Not Stack") << endl;

   cout << (validStackSeq(pushed3, popped3, len3) ? "Stack" : "Not Stack") << endl;

   return 0;
}

Can you guys help me provide an example code that fixes my original code? It'll help me out a lot more.

[dhayden]

You're very close.

Let's look at the first sample input:

INSERT 2
INSERT 1
REMOVE 1
REMOVE 2

Line 3 says that it removes a 1 from the collection. If this is a stack, will the removed (popped) value be a 1? Why or why not?

How about for line 4. When you remove that item, will it be a 2?

How about the second sample input:

INSERT 5
INSERT 10
INSERT 12
REMOVE 10
REMOVE 5
REMOVE 12

At line 4 it removes 10. If this is a stack, will 10 be removed? Why or why not?

How can you test these conditions?

[thmm]

I would write a function that would break one line of input into a struct with a string and a number.

struct Pair
{
   string command;
   int num;
};

Pair parse_line(string input)
{
   // your code here
}

It will be easier to apply the commands.
Maybe like so:

getline(inFile, data);
Pair p = parse_line(data);
if (p.command == "INSERT")
  stack.push(p.num);

[Orion98]

I implemented the stack validation code into my original code and I think I'm on to something. It's not 100% correct though. Let me know what you think. I'll try out @Learner2 logic

Updated Code:

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
using namespace std;

// Function to check validity of stack sequence
bool validStackSeq(string input, int len)
{
    // maintain count of popped elements
    int j = 0;

    // an empty stack
    stack <int> s;
    for(int i = 0; i < len; i++)
    {
        s.push(input[i]);

        // check if appended value is next to be popped out
        while (!s.empty() && j < len && s.top() == input[j])
        {
            s.pop();
            j++;
        }
    }

    return j == len;
}

int main()
{
    ifstream inFile;
    string data;

    string command;
    int num;

    inFile.open("StackTest.txt");
    //cout << "Reading file..." << endl;

    stack <int> s;

    while(getline(inFile, data))
    {
        if(command == "INSERT")
        {
            s.push(num);
        }
        else if(command == "REMOVE")
        {
            s.pop();
        }

        num = sizeof(data)/sizeof(data[0]);

        cout << (validStackSeq(data, num) ? "Stack" : "Not Stack") << endl;
    }

    inFile.close();
}

Output:

Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack
Stack

[dhayden]

I implemented the stack validation code into my original code

Your stack validate routine doesn't compile with the stack class you first posted. The class isn't a template. And it doesn't have an empty() method (although it does have an isEmpty() method) and it doesn't have a top() method (although it does have a top member, although that member is private).

I think I'm on to something

I'm afraid not. validateStackSeq() will always return true. When I fix the problems above and feed the program this input:

Gilligan's Island
I Dream of Jeannie
Beverly Hills 90210
Keeping Up With the Kardashians

I get this output:

Stack
Stack
Stack
Stack

Line 54 looks like you're trying to get the size of the string (the input line). What does that have to do with anything?

Here's a version of main that sort of works:

// main function
int main()
{
    int numLines;
    while (cin >> numLines) {
        stack stk(numLines);    // stack will never be deeper than the number o\
f lines

        string command;
        int num;
        bool isValid = true;
        for (int i = 0; i<numLines; ++i) {
            cin >> command >> num;
            if (!isValid) {
                // We know it's invalid. Just skip
                // the remaining input lines.
                continue;
            }

            if (command == "INSERT") {
                stk.push(num);
            } else if (command == "REMOVE") {
                if (num != stk.pop()) {
                    isValid = false;
                }
            } else {
                cout << "Unknown command " << command << '\n';
            }
        }

         // Finally, generate the output
        if (isValid) {
            cout << "stack\n";
        } else {
            cout << "not stack\n";
        }
    }
        return 0;
}

I have intentionally left 2 bugs in here for you to fix.
1. If you try to pop from an empty stack, it will fail
2. If there is data left on the stack at the end of the test, it will think it's a stack.

[thmm]

I would structure the program a bit more.
Have a look at this skeleton:

#include <iostream>
#include <fstream>
#include <string>

struct Pair
{
   std::string command;
   int num;
};

Pair parse_line(const std::string& input)
{
  Pair p;
  // your code here
   
  return p;
}

void do_test(std::istream& is)
{
  // your code here
  // read the number of commands from is
  // read each command and parse it into a Pair
  // apply each command
  // write the output to std::cout    
}

int main()
{
  const int NUM_TESTS = 3;
  std::ifstream src("StackTest.txt");
  
  for (int i = 0; i < NUM_TESTS; i++)
  {
    do_test(src);
  }
    
}

[dhayden]

Breaking it up is a good idea, especially for a beginner.

One change I'd make to your suggestion though: the program doesn't need to know how many tests are in the input file. So maybe something like:

#include <iostream>
#include <fstream>
#include <string>

struct Pair
{
   std::string command;
   int num;
};

Pair parse_line(const std::string& input)
{
  Pair p;
  // your code here
   
  return p;
}

void do_test(std::istream& is, int numLines)
{
  for (int i=0; i<numLines; ++i) {
    // your code here
    // read one command and parse it into a Pair
    // apply the command
  }
  // write the output to std::cout    
}

int main()
{
   std::ifstream src("StackTest.txt");
   int numLines;
   while (src >> numLines) {
      do_test(src, numLines);
   } 
}

[Orion98]

I figured out the problem with my code. It was the way I was using the commands and how my file was being processed.

I learned that you cannot create two separate arrays for INSERT and REMOVE commands and process them independently, because the result depends on how the commands are interleaved.

I attached my code here that does what I needed it to do.

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
using namespace std;

int main()
{
     ifstream inFile;
     inFile.open("StackTest.txt");
     int num;

     while(!inFile.eof())
     {
          stack <int> s;
          bool stackSeq = true;
          inFile >> num;

          for(int i = 0; i < num; i++)
          {
               string cmd;
               int arg;

               inFile >> cmd >> arg;

               if(!stackSeq)
                   continue;

               // The INSERT commands should be performed as-is, no checks are required.
               if(cmd == "INSERT")
               {
                    s.push(arg);
               }
               
               // The REMOVE commands requires two checks to be performed: 
               // whether the stack is empty and whether the top of stack contains 
               // the same number as the argument of the REMOVE command. 
               // If either of the checks fail then we set isStack to false.
               else if(cmd == "REMOVE")
               {
                    if(s.empty() || s.top() != arg)
                    {
                         stackSeq = false;
                    }
                    if(!s.empty())
                    {
                         s.pop();
                    }
               }
          }

          cout << (stackSeq ? "stack" : "not stack") << endl;
     }

     inFile.close();
}