对于计算机专业的学生来说,他们一定会很熟悉一句话:程序设计 = 算法 + 数据结构。而根据笔者的理解,所谓程序设计其实就是为了编程解决实际问题,所谓算法是一种解决问题某种思维的方法,但是思维需要得到编程实践,这就需要基于数据结构。一个好的数据结构能够让我们更快更高效得处理数据,有些模拟性、数学背景并不深厚的的问题,仅仅基于高效的数据结构就可以解决。那么这一章节,我们就单独将队列、栈、双端队列拿出来,结合具体的题目,看看它们是如何灵活的运用到解题策略当中的。
考虑到笔者在《入门经典》和《啊哈算法》中对几种简单的线性结构已经有所介绍,这里便不再赘述其概念和STL的用法。主要通过具体的题目来进行提高运用的能力。
不匹配括号问题:
小括号:().
中括号:[]
大括号:{}
现在给出一个由三种括号组成字符串,请编程判断三种括号是否匹配。
示例输入值:
3
()()
({[}])
({}[(){}])
示例输出值:
YES
NO
YES
分析:如果进行模拟,过程会变得非常麻烦而且非常不好设计。但是如果我们基于栈的数据结构,会发现会使问题变得异常简便。因为括号匹配的法则和栈“后入先出”的特点刚好吻合。我们只需要将所有的左括号依次入栈,一旦遇到右括号,我们将之与栈顶元素进行匹配,如果匹配,栈顶元素出栈,否则,完成判断。
简单的参考代码如下。
bool wellMatched(const string& formula)
{
const string opening("({["),closing(")}]"); stack<char> openStack;
for(int i = ;i < formula.size();++i)
{
if(opening.find(formula[i]) != -)
openStack.push(formula[i]);//左括号,压栈
else//右括号,进行匹配
{
if(openStack.empty()) return false;//此时栈空,匹配失败
if(opening.find(openStack.top()) != closing.find(formula[i])) return false;//不匹配 openStack.pop();//弹出栈顶元素
} return openStack.empty();//遍历字符串所有字符,如果栈空,匹配成功
}
}