Посмотрите, равны ли две строки с использованием стеков - PullRequest
Новая
       27

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

0 голосов
/ 03 марта 2019

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

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

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

#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() && 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] != '\0')
        {    
            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] != '\0') 
        {
            if(inputB[i] != '<')
            {    
                bStack.push(inputA[i]);
            }
            else if(!bStack.empty())
            {
                bStack.pop();
            }
            else
            {  
                bStack.pop();
            }
        }
    }

    return (EqualStack(aStack,bStack));
}

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

Ответы [ 2 ]

0 голосов
/ 03 марта 2019

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

Во-первых, во второй копии вашего цикла в InputsEqual () вы передаете значение inputA [i], где должно быть указано inputB [i]. 

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

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

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

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

из: 

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

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

return (a.empty() && b.empty()) ? true:false; // redundant
return a.empty() && 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]! = '\ 0', если вы просто проверяете inputAorB.length () вместо length () + 1 вцикл, так что 

for(int i = 0 ; i < inputA.length() + 1; i++)
{
    if(inputA[i] != '\0')
    {
        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();
    }
}

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

0 голосов
/ 03 марта 2019

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

  • 0 <3 </li>
  • 1 <2 </li>
  • 2 <2 </li>

Так будетостановка после сравнения 2.

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

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

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