stack - 堆栈分配如何匹配左右括号

Question

我已经一个星期想弄清楚如何完成这项任务了。它有点不清楚如何将我的 if 语句与堆栈连接起来。

这是我的代码，它由 3 个文件组成

分配问题是，括号和括号应该匹配，这意味着如果我们有左括号，那么后面应该是右括号，否则会说无效。

我会很高兴任何提示或修复。

cstack.h 文件

#include <iostream>

class FullStack{};

class EmptyStack{};


class cstack

{

private:
    int top;        // Index to top of the stack
    char data[21];      // The stack

public:
    cstack();       // Class constructor
    void Push(char);    // Push an item onto the stack
    void Pop();     // Pop an item from the stack
    bool Top();
    bool IsEmpty();     // Return true if stack is empty
    bool IsFull();      // Return true if stack is full


};

cstack.cpp 文件

   #include <iostream>
   #include "cstack.h"
   #include <stack>
   #include <cstring>
   using namespace std;



   cstack::cstack()
   {
top = -1;
   }

   bool cstack::IsEmpty()
   {
return (top == -1);
   }

   bool cstack::IsFull()
   {
return (top == 21);
   }

   void cstack::Push(char newItem)
   {
if (IsFull())
{
    throw FullStack();

}
top++;
data[top] = newItem;
    }


    void cstack::Pop()
    {
if(IsEmpty())
{
    throw EmptyStack();
}
top--;
    }


    bool cstack::Top()
    {
if (IsEmpty())
{
    throw EmptyStack();
}   

return data[top];

    }

测试.cpp 文件

   #include <iostream>
   #include <iomanip>
   #include <cstring>
   using namespace std;
   #include "cstack.h"

   bool isValidExpression (cstack&, char*);

   int main (void)
   {    
char expression[21];
cstack stack1;

cout<< "Enter an expression: ";
cin >>expression;

if (isValidExpression (stack1, expression))
{
    cout << "\nIt's a valid expression\n\n";
}
else
{
    cout << "\nIt's NOT a valid expression\n\n";
}
system("pause");    
return 0;
}

bool isValidExpression (cstack& stackA, char* strExp)
 {


for(int i = 0; i < 21 ; i++)
{   


     if( strExp[stackA.Top()] == '[' || strExp[stackA.Top()] == '{' ||                       strExp[stackA.Top()] == '(')
    {
        stackA.Push( strExp[i] );

    }



        if( strExp[stackA.Top()] == ']' || strExp[stackA.Top()] == '}' || strExp[stackA.Top()] == ')')
    {



        if(strExp[i] == '[' && strExp[stackA.Top()] == ']')
        {
            return true;

        }else 

        {
        return false;


    }

}
}
return true;
    }

Answer 1

对于这个问题，你通常这样做：

• 从输入中获取每个字符
• 推动堆栈上的每个左括号
• 如果你得到一个右括号，请检查堆栈的顶部元素。
  • 如果该元素是右左括号，则将其从堆栈中删除。
  • 如果该元素不是右左括号，则返回 false。

正如 Nikhil 在评论中提到的，通常pop()应该返回弹出的元素，但在下面的代码中我使用了你的堆栈。

for(int i = 0; i < 21 ; i++)
{   


 if(strExp[i] == '[' || strExp[i] == '{' || strExp[i] == '(')
{
    stackA.Push( strExp[i] );

}



    if( strExp[i] == ']')
    {
       if(!stackA.IsEmpty && stackA.Top() == '[')
       {
         stackA.Pop();
       } else {
                return false;
       }
    }

    if( strExp[i] == '}')
    {
       if(!stackA.IsEmpty && stackA.Top() == '{')
       {
         stackA.Pop();
       } else {
                return false;
       }
    }

    if( strExp[i] == ')')
    {
       if(!stackA.IsEmpty && stackA.Top() == '(')
       {
         stackA.Pop();
       } else {
                return false;
       }
    }

}

return true;

编辑：当我们找到匹配的右括号时使用'pop（）'时，我们确保在堆栈顶部总是有最后一个打开的括号。您可以关闭该括号或打开另一个括号，但不能关闭较早的括号。

当您找到一个右括号并且有一个空堆栈时，就会发生您描述的错误。所以你必须先检查一下。if(!stackA.IsEmpty && stackA.Top == '['). 请参阅我编辑的代码。通常使用此代码“[]”应该是有效的，如果我发现另一个错误，我会仔细检查并告诉你。