Стековая программа на C ++

Question

Я хочу реализовать код в моей программе, где он угадывает, работает ли данный ряд операций и соответствующие возвращаемые значения из входного файла как стек. Другими словами, вывод полностью определяется входным файлом.

Текстовый файл (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

Ожидаемый вывод ( из входного файла):

stack
not stack
stack

Однако я застрял на том, как реализовать эту функцию в моем текущем коде.

Если кто-нибудь может помочь мне в достижении ожидаемого результата выше или дать мне несколько советов, я был бы очень признателен!

Выполняется код ...

#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();
}

Токовый выход

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

Программа проверки стека (без входного файла)

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

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

Answer 1

Выполните операции INSERT и REMOVE, как указано в текстовом файле. Результатом является «стек», если все операции удаления возможны (не происходят, когда стек пуст), а операнд каждой операции удаления равен фактическому значению, полученному из вашего стека.

ОБНОВЛЕНО 2020- 02-29

Невозможно создать два отдельных массива для операций INSERT и REMOVE и обработать их независимо, поскольку результат зависит от того, как операции чередуются. Например,

INSERT 1
INSERT 2
REMOVE 2
REMOVE 1

должно привести к stack, но если мы переместим одну операцию REMOVE вверх:

INSERT 1
REMOVE 2
INSERT 2
REMOVE 1

, результат станет not stack. Это означает, что вам нужно обрабатывать операции в том же порядке, в каком они отображаются в файле.

Общая структура кода:

  ifstream inFile;
  inFile.open("StackTest.txt");

  int num;
  while (inFile >> num) {  // Read number of INSERT/REMOVE in each test set
    stack<int> s;
    bool isStack = true;
    for (int i = 0; i < num; i++) {
       // Read and process all INSERT/REMOVE operations in this test set 
       // Set isStack to false if not stack behavior detected
    }
    cout << (isStack ? "stack" : "not stack") << endl;
  }
  inFile.close();

Когда мы читаем операции из ввода файл мы пытаемся их выполнить. Операции INSERT должны выполняться как есть, проверки не требуются.

      if (operation == "INSERT") {
        s.push(argument);
      }

Операции REMOVE требуют выполнения двух проверок: пуст ли стек и содержит ли вершина стека то же число, что и аргумент операции УДАЛИТЬ. Если одна из проверок не удалась, мы устанавливаем для isStack значение false.

      if (operation == "REMOVE") {
        if (s.empty() || s.top() != argument) {
          isStack = false;
        }
        if (!s.empty()) {
          s.pop ();
        }
      }

Объединяя это вместе, мы получаем:

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

int main () {
  ifstream inFile;
  inFile.open("StackTest.txt");
  int num;
  while (inFile >> num) {
    stack<int> s;
    bool isStack = true;
    for (int i = 0; i < num; i++) {
      string operation;
      int argument;
      inFile >> operation >> argument;
      if (!isStack)
        continue;
      if (operation == "INSERT") {
        s.push(argument);
      }
      else if (operation == "REMOVE") {
        if (s.empty() || s.top() != argument) {
          isStack = false;
        }
        if (!s.empty()) {
          s.pop ();
        }
      }
    }
    cout << (isStack ? "stack" : "not stack") << endl;
  }
  inFile.close();
}

Еще одна вещь, которую стоит упомянуть: после того, как мы прочитали Имя операции и ее аргумент из файла мы проверяем

      if (!isStack)
        continue;

Это утверждение не требуется, оно существует только для повышения производительности. Если мы уже обнаружили, что данный набор тестов не соответствует стеку, нам не нужно выполнять все оставшиеся операции в этом наборе тестов, мы просто пропускаем их. Вы можете безопасно удалить это утверждение, не влияя на результат.