栈的应用有数制转换，括号匹配检测，迷宫求解，表达式求值等
本文涉及
1. 中缀表达式求值
2. 中缀表达式转换为后缀表达式
3. 后缀表达式求值

1.中缀表达式求值

题目链接

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
// 表达式求值 要用到两个栈 一个数字栈 一个符号栈
// 同时 在扫描前定义好运算符的优先级
// +- =1 */=2 (=0
// 对于每一个元素 若是数字存入数字栈
// 若是(入符号栈 
// 若是)进行运算 直到符号栈栈顶为(
// 运算的过程为弹出数字栈的两个元素 符号栈的栈顶
// 根据弹出的运算符进行运算 要注意运算的先后顺序
// 再将运算结果存入数字栈
// 若是其他运算符 只要符号栈不为空 就持续运算 
// 直到符号栈空 或 当前运算符 优先级高于栈顶
stack <int> num;
stack <char> op;
map <char,int> mp;//{{'+',1},{'-',1},{'*',2},{'/',2}};

void eval(){
    int a=num.top();num.pop();
    int b=num.top();num.pop();
    char c=op.top();op.pop();
    int x=0;
    if (c=='+') x=a+b;
    else if (c=='-') x=b-a;
    else if (c=='*') x=a*b;
    else if (c=='/') x=b/a;
    num.push(x);
}
int main(){
    string s;
    cin>>s;
    mp['+']=1;mp['-']=1;
    mp['*']=2;mp['/']=2;
    mp['(']=0;
    for (int i=0;i<s.size();i++){
        char x=s[i];
        if (s[i]>='0'&&s[i]<='9'){
            int j=i,t=0;
            while (j<s.size()&&s[j]>='0'&&s[j]<='9'){
                t=t*10+s[j]-'0';
                j++;
            }
            i=j-1;
            num.push(t);
        }
        else if (x=='(') op.push(x);
        else if (x==')') {
            while (op.top()!='(') eval();
            op.pop();
        }
        else {
            while (op.size()&&mp[op.top()]>=mp[x]) eval();
    //运算至 当前运算符 优先级高于栈顶
            op.push(x);
        }
    }
    while (op.size()) eval();
    cout<<num.top();
}

作者：蓬蒿人
链接：https://www.acwing.com/activity/content/code/content/1053483/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.中缀表达式转化为后缀表达式

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
// 与表达式求值无本质区别
//如果看不懂可以先去看上面的表达式求值
// 一个string数组res存结果 以便对字母表达式也能读 如 c+bl*o
// 再开一个栈存放运算符
// mp确定运算符优先级顺序
// 对于数字 直接存入res 运算符则视情况而定
// 若当前的运算符优先级高于 栈顶的运算符 则入栈
// 否则 栈顶元素弹出 存入res 
// 直至栈顶元素优先级小于当前运算符优先级 或栈为空
stack <int> num;
stack <char> op;
map <char,int> mp;
int main(){
    string s;
    cin>>s;
    mp['+']=1;mp['-']=1;
    mp['*']=2;mp['/']=2;
    mp['(']=-1;mp[')']=-1;
    string res[100010];
    int u=0;
    for (int i=0;i<s.size();i++){
        char x=s[i];
        //if (s[i]>='0'&&s[i]<='9'){
        if(!mp[s[i]]){
            int j=i;
            string t;
            //while (j<s.size()&&s[j]>='0'&&s[j]<='9'){
            while (j<s.size()&&!mp[s[j]]){
                t+=s[j++];
            }
            res[u++]=t;
            i=j-1;
        }
        else if (x=='(') {
            //res[u++]='(';
            op.push(x);
        }
        else if (x==')') {
            while (op.top()!='(') {
                res[u++]=op.top();
                op.pop();
            }
            op.pop();
            //res[u++]=')';
        }
        else {
            while (op.size()&&mp[op.top()]>=mp[x]) {
                res[u++]=op.top();
                op.pop();
            }
            op.push(x);
        }
    }
    while (op.size()) {
        res[u++]=op.top();
        op.pop();
    }
    for (int i=0;i<u;i++){
        cout<<res[i]<<' ';
    }
}

后缀表达式(逆波兰表达式)求值

题目链接

// 基本思路就是一个栈存运算的值 
// 对于输入 是数字就读入 
// 若是是运算符op 就弹出栈顶a 在弹出栈顶b 进行b op a的运算
// 运算完把结果再存回数值栈
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack <int> sta;
        for (auto &t:tokens){
            if (t=="+"||t=="-"||t=="*"||t=="/"){
                int a=sta.top();sta.pop();
                int b=sta.top();sta.pop();
                if (t=="+") sta.push(a+b);
                else if (t=="-") sta.push(b-a);
                else if (t=="*") sta.push(a*b);
                else sta.push(b/a);
            }
            else sta.push(stoi(t));
        }
        return sta.top();
    }
};