Проверьте, равны ли две строки с использованием стеков

#c #stack #lifo

#c #стек #lifo #c

Вопрос:

Цель состоит в том, чтобы иметь две строки, в которых в этой строке есть кнопка обратного пробела, представленная как < . Однако выходные данные двух строк с по-разному расположенной кнопкой backspace должны быть равными.

Для InputsEqual функции она в основном извлекает верхний элемент из стека, когда видит кнопку backspace.

Я протестировал это с другим файлом, но он по-прежнему не работает. Не могли бы вы, пожалуйста, просмотреть этот код?

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

bool EqualStacks(stack<char> a, stack<char> b);
bool InputsEqual(string inputA, string inputB);

int main()
{
    string inputA = "abcde<<";
    string inputB = "abcd<e<";

    if(InputsEqual(inputA,inputB))
    {
        cout << "Inputs Equal.n";
    }
    else
    {
        cout << "Inputs are NOT Equal.n";
    }
    return 0;
}

bool EqualStack(stack<char> a, stack<char> b)
{
    for(int i = 0; i < a.size(); i  )
    {
        if(a.top() == b.top())
        {
            a.pop();
            b.pop();
        }
    }
    return (a.empty() amp;amp; b.empty()) ? true:false;
} 

//If both stacks are empty, they equal
bool InputsEqual(string inputA,string inputB) 
{
    stack<char> aStack;
    stack<char> bStack;
    // string inputA;
    // cout << "Please enter a string. Press < if you want to delete something"
    // cin >> inputA; 
    for(int i = 0 ; i < inputA.length()   1; i  )
    {
        if(inputA[i] != '')
        {    
            if(inputA[i] != '<')
            {
                aStack.push(inputA[i]);
            }
            else if(!aStack.empty())
            {
                aStack.pop();
            }
            else
            {  
                aStack.pop();
            }         
        }
    }

    for(int i = 0 ; i < inputB.length()   1; i  )
    {
        if(inputB[i] != '') 
        {
            if(inputB[i] != '<')
            {    
                bStack.push(inputA[i]);
            }
            else if(!bStack.empty())
            {
                bStack.pop();
            }
            else
            {  
                bStack.pop();
            }
        }
    }

    return (EqualStack(aStack,bStack));
} 
  

//Вывод: строки не равны

Комментарии:

1. Добро пожаловать в Stack Overflow. Потратьте несколько минут на чтение ericlippert.com/2014/03/05/how-to-debug-small-programs советы по отладке вашего кода.

2. Несвязанный (я думаю): else { aStack.pop(); } кажется, это плохая идея. Добраться туда можно, только если стек пуст. Следовательно, нечего всплывать. Бум.

Ответ №1:

У вас есть две конкретные проблемы, нарушающие ваш код.

Первое заключается в том, что во второй копии вашего цикла в InputsEqual() вы вводите значение inputA[i] там, где оно должно указывать inputB[i].

 bStack.push(inputA[i]); // should be inputB!
  

Во-вторых, в EqualStack() вы вызываете.size() на каждой итерации, сравнивая ее с i. Проблема в том, что вы также сжимаете стек, вызывая.pop() при совпадении. Это приводит к преждевременному прерыванию цикла for, оставляя стеки непустыми.

Быстрое решение — изменить цикл на end, когда a пусто, вот так:

 for(int i = 0; !a.empty(); i  ) // fixed
  

вместо:

 for(int i = 0; i < a.size(); i  ) // broken
  

Я также хотел бы указать на несколько других вещей, которые можно было бы очень быстро устранить:

 return (a.empty() amp;amp; b.empty()) ? true:false; // redundant
return a.empty() amp;amp; b.empty(); // better
  

и:

 else if(!aStack.empty())
{
    aStack.pop(); // you call it if the stack is empty
}
else
{
    aStack.pop(); // and if its not, which is redundant!
}
  

насколько я могу судить, pop (), похоже, не определен для пустых контейнеров, поэтому проверка того, пуст ли стек перед его вызовом, была бы хорошей практикой, просто завершающий оператор pop() не нужен! Просто удалите это, и все будет хорошо.

Наконец, вы можете избежать inputAorB[i] != », если вы просто проверите наличие inputAorB.length() вместо length() 1 в цикле, так что:

 for(int i = 0 ; i < inputA.length()   1; i  )
{
    if(inputA[i] != '')
    {
        if(inputA[i] != '<')
        {
            aStack.push(inputA[i]);
        }
        else if(!aStack.empty())
        {
            aStack.pop();
        }
    }
}
  

может быть сокращен до:

 for(int i = 0 ; i < inputA.length(); i  )
{
    if(inputA[i] != '<')
    {
        aStack.push(inputA[i]);
    }
    else if(!aStack.empty())
    {
        aStack.pop();
    }
}
  

Возможно, потребуется дополнительная очистка, но я решил просто указать на наиболее вопиющие из них. Удачи с вашим проектом!

Ответ №2:

Вы никогда не будете сравнивать все элементы стека i < a.size() суть вашего цикла заключается в оценке каждой итерации, но вы также изменяете размер a каждой итерации. Таким образом, сравнения с каждой итерацией являются:

  • 0<3
  • 1<2
  • 2<2

Таким образом, это остановится после 2 сравнений.

Таким образом, в конце цикла return (a.empty() amp;amp; b.empty()) ? true:false; будет возвращен false результат, потому что в стеке все еще есть элементы.

Вместо вашего цикла for вы могли бы просто использовать цикл while:

 while(!a.empty() amp;amp; !b.empty()) {
  if(a.top() == b.top())
  {
    a.pop();
    b.pop();
  } else {
    break;
  }
}