一、棧（stack）
1、棧的特點
棧(Stack)是一種線性存儲結構，它具有如下特點：
【Note】：
（1）棧中的資料元素遵守”先進後出”(First In Last Out)的原則，簡稱FILO結構。
（2）限定隻能在棧頂進行插入和删除操作。
棧在計算機中應用相當廣泛，包括遞歸的調用和傳回、二叉樹和森林的周遊、調用子程式及從子程式傳回、表達式的轉換和求值、CPU的中斷處理等等。
2、棧的相關概念
（1）棧頂（top()）與棧底：允許元素插入與删除的一端稱為棧頂，另一端稱為棧底。
（2）壓棧( push() )：棧的插入操作，叫做進棧，也稱壓棧、入棧。
（3）彈棧( pop() )：棧的删除操作，也叫做出棧。
棧的實作可以使用數組和連結清單。
二、棧的應用之表達式求值
1、逆波蘭表達式簡介
假定給定一個隻 包含 加、減、乘、除，和括号的算術表達式，你怎麼編寫程式計算出其結果。問題是：在表達式中，括号，以及括号的多層嵌套 的使用，運算符的優先級不同等因素，使得一個算術表達式在計算時，運算順序往往因表達式的内容而定，不具規律性。 這樣很難編寫出統一的計算指令。
使用逆波蘭算法可以輕松解決。他的核心思想是将普通的中綴表達式轉換為字尾表達式。
轉換為字尾表達式的好處是：
- 去除原來表達式中的括号，因為括号隻訓示運算順序，不是完成計算必須的元素。
- 使得運算順序有規律可尋，計算機能編寫出代碼完成計算。雖然字尾表達式不利于人閱讀，但利于計算機處理。
2、将中綴表達式轉換成字尾式（逆波蘭表達式）
1. 從左到右讀進中序表達式的每個字元。
2. 如果讀到的字元為操作數，則直接輸出到字尾表達式中。
3. 如果遇到“)”，則彈出棧内的運算符，直到彈出到一個“(”,兩者互相抵消。
4. “(”的優先級在棧内比任何運算符都小，任何運算符都可以壓過它，不過在棧外卻是優先級最高者。
5. 當運算符準備進入棧内時，必須和棧頂的運算符比較，如果外面的運算符優先級高于棧頂的運算符的優先級，則壓棧；如果優先級低于或等于棧頂的運算符的優先級，則彈棧。直到棧頂的運算符的優先級低于外面的運算符優先級或者棧為空時，再把外面的運算符壓棧。
6. 中綴表達式讀完後，如果運算符棧不為空，則将其内的運算符逐一彈出，輸出到字尾表達式中。
//比較lhs的優先級是否不高于rhs，rhs表示棧頂的符号
bool priority(const char &lhs, const char &rhs)
{
if (rhs == '(')//左括号在棧外優先級最高
return false;
if (lhs == '+' || lhs == '-')
return true;
if ((lhs == '*' || lhs == '/') && (rhs == '*' || rhs == '/'))
return true;
return false;
}
//将中綴表達式轉換成字尾式（逆波蘭表達式）
string exchange(const string &str)
{
vector<char> vec;
string res;
stack<char> st;//操作符堆棧
for (int i = ; i < str.size(); ++i)
{
if (isdigit(str[i]))//如果是數字，直接輸出到後序表達式中
{
vec.push_back(str[i]);
}
else//如果是符号,需要與棧頂的元素進行比較
{
if (st.empty() || str[i] == '(')//小括号在棧外優先級最高，直接壓棧
st.push(str[i]);
else
{
if (str[i] == ')')//遇到右括号，則彈棧，直到遇到左括号，兩者互相抵消
{
while (!st.empty() && st.top() != '(')
{
vec.push_back(st.top());
st.pop();
}
st.pop();
}
else//遇到的是其他操作符
{
if (priority(str[i], st.top()))//優先級比棧頂元素低
{
while (!st.empty())
{
vec.push_back(st.top());
st.pop();
}
st.push(str[i]);
}
else//優先級比棧頂元素高，壓棧
{
st.push(str[i]);
}
}
}
}
}
while (!st.empty())//如果堆棧不為空，則将其中的元素全部彈出
{
vec.push_back(st.top());
st.pop();
}
for (auto v : vec)
res += v;
return res;
}
3、字尾表達式求值
字尾表達式具有和字首表達式類似的好處，沒有優先級的問題。
1. 直接讀取表達式，如果遇到數字就壓棧。
2. 如果遇到運算符，就彈出兩個數進行運算，随後再将運算結果壓棧。
//定義四則運算
int operate(int first, int second, char op)
{
int res = ;
switch (op)
{
case '+':
res = first + second;
break;
case '-':
res = first - second;
break;
case '*':
res = first*second;
break;
case '/':
res = first / second;
break;
default:
break;
}
return res;
}
int calculate(string input)
{
stack<int> st;//操作數堆棧
for (auto &s : input)
{
if (isdigit(s))//如果是數字就壓棧
{
st.push(s - '0');
}
else//遇到字元就彈出兩個操作數進行運算
{
int a = st.top();
st.pop();
int b = st.top();
st.pop();
st.push(operate(b, a, s));
}
}
return st.empty() ? : st.top();//最後的結果為棧頂元素
}
int main(int argc, char const *argv[])
{
string str = "1+(3+4)*5-2";
cout << exchange(str) << endl;
cout << calculate(exchange(str)) << endl;
system("pause");
return ;
}
三、棧的應用之括号比對
括号比對在很多字元串處理的場景中時常被用到，諸如各大IDE括号不比對的錯誤提示，編譯器編譯時檢查應該成對出現的括号是否符合要求等，在這裡我們就直接使用一種比較正常，但效率不差的方法去解決括号比對的問題就行了。
Description: 給定一個字元串，其中的字元隻包含三種括号：花括号{ }、中括号[ ]、圓括号( )，即它僅由 “( ) [ ] { }” 這六個字元組成。設計算法，判斷該字元串是否有效，即字元串中括号是否比對。括号比對要求括号必須以正确的順序配對，如“{ [ ] ( ) }” 或 “[ ( { } [ ] ) ]” 等為正确的格式，而 “[ ( ] )” 或 “{ [ ( ) }” 或 “( { } ] )” 均為不正确的格式。
定義一個棧，遇到左括号就壓棧，當遇到一個右括号時，首先棧頂元素是否是左括号，如果是的則對棧進行pop操作表明頂部元素已被比對，否則為不比對情況，直接傳回false。當整個字元串周遊結束，我們就可以通過判斷該棧是否為空來判斷整個字元串中的符号是否比對。
具體代碼如下：
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(int argc, char const *argv[])
{
string str;
getline(cin,str);
stack<char> st;
int l = str.size();
int flag = ;
for (int i= ; i<l ; ++i)
{
switch(str[i])
{
case '(' : st.push(str[i]) ; break;
case '[' : st.push(str[i]) ; break;
case '{' : st.push(str[i]) ; break;
case ')' :
if(st.top() == '(')
st.pop();
else
flag = ;
break;
case ']' :
if(st.top() == '[')
st.pop();
else
flag = ;
break;
case '}' :
if(st.top() == '{')
st.pop();
else
flag = ;
break;
}
}
if(!flag)
{
cout << "no" << endl;
}
else
{
if(!st.empty())
{
cout << "no" << endl;
}
else
{
cout << "yes" << endl;
}
}
system("pause");
return ;
}