好家伙,寫題,題目代碼在最后
來吧,
1.堆疊
堆疊（stack）又名堆疊，它是一種運算受限的線性表，限定僅在表尾進行插入和洗掉操作的線性表，
這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，
向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；
從一個堆疊洗掉元素又稱作出堆疊或退堆疊，它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素， ——百度百科
上圖
總之,我們記住這玩意"先進后出"就行了
舉個栗子,(假設水倒入杯子后不會流動)
就像你燒了一壺水,拿個杯子倒水,然后喝了一口
你喝的第一口水是你最后倒進去的
而你最先倒進去的水在最下面
最后倒進去的水最先喝到
最先倒進去的最后喝到
這就是先進后出了
(是不是拿固體舉例子會比較好...)
方法以及標識:
//頭檔案
#include <stack>
//實體化字符型別的堆疊
stack <char> sta;
常用方法:
1.1.sta.top()方法
函式用于訪問堆疊頂元素
1.2.sta.pop()
函式用于移除堆疊頂元素
1.3.sta.size()
函式回傳堆疊元素的數量，堆疊元素的數量是指堆疊的大小，
堆疊元素的大小是非常重要的資訊，因為基于它我們可以推斷出許多其他內容，例如所需的空間等，
1.4.sta.push(new_obj)
函式用于在堆疊頂添加新元素
1.5.sta.empty()
函式用于測驗容器是否為空
2.題目如下:
輸入一串字串，該字串只能由各種不同的括號組成，設計演算法，測驗該字串中的括號是否匹配，
如：“({[]})”該字串中括號是匹配的，字串“[{{}(”是不匹配的，要求采用堆疊的思想來完成該題目
2.1.分析一波題目:
我們用堆疊去解決這個題目(不然為什么會有上面的內容)
這種對稱的題目用堆疊來做就是很舒服
利用堆疊的先進后出的特點，我們可以進行左右括號的匹配，“（）{}”,在右括號“）}”左邊最近的左括號必須是相對應的“（{”，否則就不合法
先把左半邊的括號全部入堆疊,然后按入堆疊的反順序依次去查對應右括號,(如先入"{("那么就先查")}")
若果出現不匹配,則回傳false,
每次匹配一對正確的括號，就要將其出堆疊，為后面的括號騰出空間，
上代碼:
#include <iostream>
#include <stack>
using namespace std;
bool isValid(string s) {
stack <char> sta;
char c,b;
int l=s.length();
for(int i=0;i<l;i++)
{
//將所有的左半邊括號入堆疊
if(s[i]=='(' || s[i]=='[' || s[i]=='{')
{
sta.push(s[i]);
}
//對后面的元素逐一檢查
//三種情況
//1.堆疊空了,回傳false
//2.成功匹配,將成功匹配的字符出堆疊
//3.其他情況,回傳false
else if(s[i]==')')
{
if(sta.empty())
return false;
else if(c=sta.top(),c=='(')
sta.pop();
else
return false;
}
else if(s[i]==']')
{
if(sta.empty())
return false;
else if(c=sta.top(),c=='[')
sta.pop();
else
return false;
}
else if(s[i]=='}')
{
if(sta.empty())
return false;
else if(c=sta.top(),c=='{')
sta.pop();
else
return false;
}
}
if(sta.empty())
return true;
else
return false;
}
int main()
{
string s;
cin>>s;
//輸入字符
bool b=true;
b=isValid(s);
if(b==true)
cout << "true";
else cout << "false";
return 0;
}
輸入樣例:
輸入: ({}(000))
輸出: true
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538169.html
標籤：其他