算法思想总结：栈

一、栈的经典应用：波兰表达式与逆波兰表达式

我们平时看到的 1+2*（3-4*5）+6/7 叫做中缀表达式，平时我们习惯用这个计算的原因是我们可以整体地去看到这个表达式并且清楚地知道各个运算符的优先级，但是计算机并不一定知道，因为他总是从前往后去遍历这个表达式。如上面这个例子，当按照计算机的逻辑去扫描了1+2的时候，并不敢直接去进行运算，因为可能后面存在一个优先级更高的操作符会优先进行计算。甚至有些时候还会出现括号这一种可以改变操作符优先级的符号！！所以这个时候，为了能够解决这个问题，就有了波兰表达式（前缀表达式）和逆波兰表达式（后缀表达式）。

前缀表达式：操作符+操作数+操作数

中缀表达式：操作数+操作符+操作数

后缀表达式：操作数+操作数+操作符

1.1 后缀表达式转中缀表达式

1.2 中缀表达式转后缀表达式

二、逆波兰表达式求值

. - 力扣（LeetCode）

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;//栈帮助我们计算for(auto&s:tokens) //遍历字符串{if(s=="+"||s=="-"||s=="*"||s=="/")//如果是操作符的话，取栈顶两个元素计算{//先取右操作数，再取左操作数int right=st.top(); st.pop();int left=st.top();st.pop();//因为可能会有不同的情况，所以要用一个swich去计算switch(s[0]){case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*': st.push(left*right);break;case '/': st.push(left/right);break;}}else st.push(stoi(s));如果不是操作符的话，利用stoi将字符串转化成数字并入栈 }return st.top();}
};

三、基本计算器II

. - 力扣（LeetCode）

class Solution {
public:int calculate(string s) {vector<int> v;char op='+';int i=0,n=s.size();while(i<n){if(s[i]==' ') ++i;else if(isdigit(s[i])){int temp=0;//先取出这个数字while(i<n&&isdigit(s[i]))  temp=temp*10+(s[i++]-'0');//这时候要根据当前op的情况去判断怎么操作switch(op){case '+':v.push_back(temp);break;case '-':v.push_back(-temp);break;case '*':v.back()*=temp;break;case '/':v.back()/=temp;break;}}else op=s[i++];//是操作符就直接改掉op}return accumulate(v.begin(),v.end(),0);}
};

四、基本计算器I

. - 力扣（LeetCode）

class Solution {
public:void calc(stack<int> &numst, stack<char> &ops){int right=numst.top();numst.pop();int left=numst.top();numst.pop();char op=ops.top();ops.pop();numst.push(op=='+'?left+right:left-right);//根据op去计算}void replace(string&s){//去掉空格int pos=s.find(" ");while(pos!=-1) {s.erase(pos,1);pos=s.find(" ");}}int calculate(string s){//利用双栈stack<int> numst;//存放所有数字//防止第一个数为负数numst.push(0);//防止第一个数是负数stack<char> ops;//存放所有运算符replace(s);int n=s.size();int i=0;while(i<n){if(s[i]=='(')  ops.push(s[i++]);  //如果是左括号 直接压栈。else if(s[i]==')')  //如果是右括号，就计算到左括号为止{while(ops.top()!='(')  calc(numst,ops);  //还没遍历到左括号的时候//循环结束说明遇到(了 此时跳过即可ops.pop();//弹出左括号++i;//去下一个位置}else if(isdigit(s[i]))//遇到数字的时候{int temp=0;while(i<n&&isdigit(s[i])) temp=temp*10+(s[i++]-'0');numst.push(temp);}else //此时遇到操作符了{  if(i>0&&s[i]=='-'&&s[i-1]=='(') numst.push(0);//应对括号后面带负数的情况while(!ops.empty()&& ops.top() != '(')//放入之前先把能算的给算了calc(numst, ops);ops.push(s[i++]);//操作符入栈}}//最后要将栈中的所有的都计算一便while(!ops.empty())   calc(numst,ops);return numst.top();//最后剩下的就是最终结果}
};

五、有效的括号

. - 力扣（LeetCode）

class Solution {
public:bool isValid(string s){//用一个栈来模拟 stack<char> st;for(auto&ch:s){if(ch=='('||ch=='{'||ch=='[') st.push(ch);//遇到左括号肯定是无脑入栈的else //此时肯定遇到了右括号 {//有两种情况，一种是右括号比左括号多，此时栈可能为空,就肯定不符合了if(st.empty()) return false;//还有一种情况是前面的对不上else if(ch==')'&&st.top()!='(' ||ch=='}'&&st.top()!='{'||ch==']'&&st.top()!='[') return false;else st.pop();}}return st.empty();//可能左括号比右括号多，导致最后栈里面还有剩下}
};

六、删除字符串中所有相邻重复项

. - 力扣（LeetCode）

class Solution {
public:string removeDuplicates(string s) {string ret;for(auto&ch:s){if(ret.size()&&ret.back()==ch) ret.pop_back();else ret.push_back(ch);}return ret;}
};

七、比较含退格的字符串

. - 力扣（LeetCode）

class Solution {
public:bool backspaceCompare(string s, string t) {//没遇到# 就入栈，遇到#就出栈return stringchange(s)==stringchange(t);}string stringchange(string&s){string ret;for(auto &ch:s){if(ch!='#') ret.push_back(ch);else if(ret.size()) ret.pop_back();}return ret;}
};

八、字符串解码

. - 力扣（LeetCode）

该题也是利用到基本计算器的解题思想

class Solution {
public:string decodeString(string s){stack<int> numst;//数字栈stack<string> strst;//字符串栈strst.push("");//先插入一个空字符串 防止越界访问int i=0,n=s.size();while(i<n){if(isdigit(s[i])) //遇到数字，提取出来放到字符串栈中{int temp=0;while(isdigit(s[i])) temp=temp*10+(s[i++]-'0');numst.push(temp);}else if(s[i]=='[')//遇到[将后面的字符串提取出来放入字符串栈中{++i;//先跳过这个括号string str;while(islower(s[i])) str+=s[i++];strst.push(str);}else if(s[i]==']')//遇到]就提取栈顶元素进行计算{int k=numst.top();numst.pop();string str=strst.top();strst.pop();for(int j=0;j<k;++j) strst.top()+=str;++i;//跳过这个右括号}else //遇到单独的字符，直接加进去strst.top()+=s[i++];}    return strst.top();}
};

九、最小栈

. - 力扣（LeetCode）

策略3解题：

class MinStack {
public:MinStack() {}void push(int val) {st.push(val);//如果当前栈为空，或者是当前的数比栈顶元素小或者相等，就入minstif(minst.empty()||minst.top()>=val) minst.push(val);}void pop() {//如果当前数和minst的栈顶元素相等，就得出if(minst.top()==st.top()) minst.pop();st.pop();}int top() {return st.top();}int getMin() {return minst.top();}private:stack<int> st;stack<int> minst;};

策略4解题：存键值对

class MinStack {
public:MinStack() {}void push(int val) {st.push(val);//如果当前栈为空，或者是当前的数比栈顶元素小或者相等，就入minstif(minst.empty()||minst.top().first>val) minst.push(pair(val,1));else if(minst.top().first==val) ++minst.top().second;}void pop() {if(minst.top().first==st.top()) {if(minst.top().second==1) minst.pop();else --minst.top().second;}st.pop();}int top() {return st.top();}int getMin() {return minst.top().first;}private:stack<int> st;stack<pair<int,int>> minst;//第一个代表最小值，第二个代表其数量};

十、验证栈序列

. - 力扣（LeetCode）

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int popi=0;for(auto&num:pushed){st.push(num);while(!st.empty()&&st.top()==popped[popi])//可能会连续出多个{st.pop();++popi;}}//return popi==popV.size();return st.empty();}
};

十一、1-n所有可能的出栈序列

如果入栈序列是1-n 将所有可能的出栈序列存储起来并返回。

//尝试输出所有出栈序列
vector<vector<int>> ret;//记录所以出栈序列
int n;//记录入栈范围
void dfs(int i, vector<int> push, vector<int> pop) //深搜+回溯
{if (i == n + 1){if (pop.size() == n){ret.push_back(pop);}return;}//入栈push.push_back(i);//可以选择出栈，或者不出栈//选择不出栈dfs(i + 1, push, pop);//选择出栈while (!push.empty()){pop.push_back(push.back());push.pop_back();dfs(i + 1, push, pop);//用形参去记录路径}
}
vector<vector<int>> poporder(int _n)
{n = _n;dfs(1, {}, {});return ret;
}

我们来测试一下：

void test()
{vector<vector<int>> ret = poporder(5);for (int i = 0; i < ret.size(); ++i){for (int j = 0; j < ret[i].size(); ++j)cout << ret[i][j] << " ";cout << endl;}cout << "入栈序列为";for (int i = 1; i <= n; ++i) cout << i;cout << "的出栈序列一共有" << ret.size() << "种" << endl;;
}

十二、利用栈实现基本计算器

目标：实现一个基本计算器，能够满足以下条件的运算：

操作数：支持正数、负数、多位数计算
操作符：支持（） + - * / % ^ 这些操作符

设计思路来源：中缀表达式和后缀表达式

具体的设计思路：

所需要的数据结构——双栈+哈希表（设为全局变量）。其中一个存储整型的栈帮助我们存储操作数，另一个存储字符类型的栈帮助我们存储操作符，然后哈希表帮我们确立操作符的优先级。
+ -的映射关系为1,* / %的映射关系为2，^的映射关系为3，按照上述方式存进哈希表来映射操作符优先级。然后对于左括号和右括号，我们进行特殊处理。
因为我们输入的是字符串，所以有些时候需要用空格分割操作符和操作数，所以我们在计算前的第一步就是封装一个replace函数来帮助我们删除字符串中的所用空格。
封装一个calc函数，帮助我们在满足计算条件的时候，取出数字栈的头两个元素分别作为右操作数和左操作数，再取出字符栈的栈顶操作符进行计算，用一个swtich语句根据不同的操作符类型执行不同的运算逻辑
进行分类讨论：

如果遇到(，无脑进栈
如果遇到 ),不断进行calc直到遇到( ,并将(弹出
如果遇到数字，因为要实现的是多位数的计算，所以可能后面的数字是挨着连在一起的，此时我们要想将该数提取出来，如果下一位也是数字，就将当前的数*10+下一个数字，当不再是数字的时候，将提取出来的数字入数字栈。
如果遇到操作符，首先要处理一个特殊情况就是，如果当前操作符是- 并且前一个操作符时( 说明该-表示的是负数而不是减，所以为了运算的合理性，我们要在数字中压个0进去。然后我们的新操作符要跟栈顶的操作符进行比较，如果运算的优先级较低或相等，就得将栈顶的操作符弹出来进行计算，即进行calc，不断重复该过程，直到新加入的操作符优先级比栈顶元素高，此时再将新操作符入栈
细节处理：第一个数可能是负数，所以我们也要按照（4）中的逻辑一样，再数字栈上先压个0进去。
最后当整个字符串遍历结束之后，我们将栈中剩余的操作数和操作符拿出来运算，最后留在数字栈顶的元素。就是我们的最终结果。
该计算器的小缺陷：（1）不支持浮点数（2）整型除不尽会舍去。

using namespace std;
unordered_map<char, int> map{{'+',1},{'-',1} ,{'*',2} ,{'/',2} ,{'%',2} ,{'^',3}}; //建立哈希映射，建立各操作符的优先级。
stack<int> nums;//创建一个数字栈，存储操作数信息
stack<char> ops;//创建一个字符栈，存储操作数信息
//对于左括号，我们直接入栈，等待右括号的匹配
//一旦遇到右括号，就需要计算()内的结果，直到遇到左括号然后弹出
//计算器
void calc()
{if (nums.size() < 2 || ops.empty()){cout << "表达式有误" << endl;return;//少于两个操作数或没有操作符，说明输入的表达式有误}//先取右操作数，再取左操作数，根据操作符进行运算int right = nums.top(); nums.pop();int left = nums.top(); nums.pop();char op = ops.top(); ops.pop();switch (op){case '+':nums.push(left + right); break;case '-':nums.push(left - right); break;case '*':nums.push(left * right); break;case '/':nums.push(left / right); break;case '%':nums.push(left % right); break;case '^':nums.push((int)pow(left, right)); break;default:cout << "操作符有误" << endl; break;//如果都不符合，就是操作符有误}
}
void replace(string& s) //删除字符串中所有空格
{int index = 0;if (!s.empty()){while ((index = s.find(' ', index)) != string::npos){s.erase(index, 1);}}
}
//可以计算整型(正负数均可,也可以是多位数)    有关()、+、-、*、/、%、^的运算      
//小缺陷：1、不支持小数   2、因为是整型,/除不尽小数会被省去
int calculate(string s)//基本计算器的实现
{replace(s);//先去掉空格 方便我们计算int i = 0, n = s.size();//用来遍历字符串nums.push(0);//先补个0，目的是防止第一个数是负数while (i < n){//如果遇到( 直接压栈即可if (s[i] == '(') ops.push(s[i++]);//如果遇到右括号，将一直到（的结果进行计算else if (s[i] == ')'){while (ops.top() != '(') calc();//此时遇到左括号，弹出左括号并++ops.pop();++i;}//如果遇到数字，将数字提出出来else if (isdigit(s[i])){//将数字提取出来放到nums中int temp = 0;while (i < n && isdigit(s[i])) temp = temp * 10 + (s[i++] - '0');nums.push(temp);}//如果遇到操作符else{//如果是(-的情况，补0，保证运算合理if (i > 0 && s[i] == '-' && s[i - 1] == '(') nums.push(0);//在放入这个操作符之前，把能算的给算了while (!ops.empty() && ops.top() != '(')//放入之前先把能算的给算了{char prev = ops.top();if (map[prev] >= map[s[i]])  calc();//如果我比前面的运算符优先级低或者相等，就将前面运算符弹出来计算。else break;}//然后将新的操作符入栈ops.push(s[i++]);}}//整个过程遍历结束后，将栈中的剩下的进行计算while (!ops.empty()) calc();return nums.top();//此时栈顶留下来的就是最终结果
}

十三、利用栈实现十进制转任意进制

stack<int> st;//帮助我们存储进制数
string basechage(int n, int x) 
{string ret;if (x < 2 && x>36) { cout << "不存在" << x << "进制数" << endl; return ret; }while (n) //当n变成0的时候{st.push(n % x);n/=x;}//此时栈中存储的就是 最终结果 while (!st.empty()){int top = st.top();if ( top>=0 && top <= 9) //如果是0-9,直接插入ret.push_back(top + '0');else //此时不是1-9，要用字母来替代ret.push_back(top + 55);st.pop();}return ret;
}