C++理解问题——链表和栈

Question

我必须编写一个代码，使用堆栈 和链表 检查括号是否平衡。这是我的代码，是我使用类里面的许多教程和 powerpoint 演示文稿制作的，同时也得到了我 friend 的一点帮助。但是，任何人都可以逐行解释“int pop”和“check”部分下发生的事情(我不理解作为评论部分)？我在理解 c++ 的这一部分(已实现的堆栈和 l.lists)时遇到了问题，而且我没有任何人可以解释它并且没有时间。我尝试了很多东西，但我真的不明白。附言代码正常工作谢谢大家!

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

struct node 
{
   char data;
   node *link;
};

int pop(node *&stack)  //node that points to address of a stack?
{
    char result;
    node *top=new node; //how can i explain this?
    top=stack; //why are we equalizing top with stack?
    result=top->data;//i dont understand
    stack=top->link;//dont understand   
    delete top; 
    return result; 
}

bool Pairs(char openP,char closedP)
{
if(openP == '(' && closedP == ')') return true;
else if(openP == '{' && closedP == '}') return true;
else if(openP == '[' && closedP == ']') return true;
else return false;
}

bool Check(string exp) 
{
   int i=0;
   node *stack=NULL;
    while(exp[i]) 
    {
        if(exp[i]=='(' || exp[i]=='[') 
           {
                node *neww=new stack;//dont understand
                neww->data=exp[i];//dont understand
                neww->link=stack; //-II- 
                stack=neww; //-II-
            }
        if(exp[i]==')' || exp[i]==']')
          {
             if(stack==NULL)
                return 0; 
             else if (Pairs(pop(stack), exp[i])==0) //what does mean this part in parentheses? 
                return 0;                           
          }
        i++;
    }
    if(stack==NULL)
        return 1;
    else
        return 0;
} 

int main()
{
    string exp;
    cout<<"Enter parentheses:\n";
    cin>>exp;
    if(Check(exp)!=0)
        cout<<"P. are  balanced";
    else 
        cout<<"P. are not balanced";  
    return 0;
}    

Answer 1

我推荐以下方法:

• 考虑忽略语言细节的算法。堆栈是正确的方法，但在您想出算法之前，您无需考虑如何实现您的堆栈。

• 决定您需要一个给定的数据结构后，在发明您自己的数据结构之前问问自己它是否已经存在于 C++ (std::stack) 中。

• 使用 C++ 习惯用法而不是 C 习惯用法(即使用迭代器 begin() 和 end() 而不是索引)除此之外，这将防止您的 exp[i] 错误。

• 不要让一个类(class)做不止一件事。如果你需要一个堆栈，那么创建一个堆栈类而不是让你的解析类参与堆栈实现。首先，它可以更轻松地考虑检查算法，其次，堆栈类可以在其他地方重用。

大体上，您的解决方案将使用迭代器检查字符串的字符，并使用std::stack<字符>。任何地方都不需要new 或指针。