0

目标是有两个字符串，在这个字符串中，有一个退格按钮，表示为<。但是，具有不同位置退格按钮的两个字符串的输出应该相等。

对于该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));
}

//输出：字符串不相等

4

2 回答 2

1

您有两个具体问题破坏了您的代码。

第一个是在 InputsEqual() 循环的第二个副本中，将 inputA[i] 的值推送到应该说 inputB[i] 的位置。

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

其次，在 EqualStack() 中，您在每次迭代时调用 a.size()，同时将其与 i 进行比较。问题是您还可以通过在匹配时调用 a.pop() 来缩小堆栈。这会导致 for 循环提前中止，使堆栈不为空。

一个快速的解决方法是在 a 为空时将循环更改为结束，如下所示：

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.length() 而不是 length() + 1，则可以避免 inputAorB[i] != '\0' ，因此：

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

可能有更多的清理工作，但我想我只是指出更明显的那些。祝你的项目好运！

于 2019-03-03T06:37:54.327 回答
0

您永远不会比较堆栈的所有元素，i < a.size()您的循环会评估每次迭代，但您也会更改a每次迭代的大小。所以每次迭代的比较是：

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

因此它将在 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;
  }
}
于 2019-03-03T06:31:09.113 回答