我必须编写一个代码,使用堆栈 和链表 检查括号是否平衡。 这是我的代码,是我使用类里面的许多教程和 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;
}
最佳答案
我推荐以下方法:
考虑忽略语言细节的算法。堆栈是正确的方法,但在您想出算法之前,您无需考虑如何实现您的堆栈。
决定您需要一个给定的数据结构后,在发明您自己的数据结构之前问问自己它是否已经存在于 C++ (std::stack) 中。
使用 C++ 习惯用法而不是 C 习惯用法(即使用迭代器 begin() 和 end() 而不是索引)除此之外,这将防止您的 exp[i] 错误。
不要让一个类(class)做不止一件事。如果你需要一个堆栈,那么创建一个堆栈类而不是让你的解析类参与堆栈实现。首先,它可以更轻松地考虑检查算法,其次,堆栈类可以在其他地方重用。
大体上,您的解决方案将使用迭代器检查字符串的字符,并使用 std::stack<字符>。任何地方都不需要new 或指针。
关于C++理解问题——链表和栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24239234/