算法1：栈维护(模拟) $O(n)$

//整体是栈模拟，一个栈存储数字，一个栈存储符号；
//左括号入栈，右括号一直算到左括号，然后出栈左括号，数字入栈
//符号，栈顶符号优先级>=当前符号就一直计算
//细节处理, -是负号还是减号，-前面不是数字且不是) 就是负号，在数字栈加入一个0
//有多余的括号，先在左边加入足够多的左括号，
//最后在清空符号栈
#include <bits/stdc++.h>
using namespace std;

stack<int> nums;
stack<char> ops;
string s;
unordered_map<char, int> mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}};

void cal() {
    int b = nums.top(); nums.pop();
    int a = nums.top(); nums.pop();
    char c = ops.top(); ops.pop();
    int res;
    if (c == '+') res = a + b;
    if (c == '-') res = a - b;
    if (c == '*') res = a * b;
    if (c == '/') res = a / b;
    if (c == '^') res = pow(a, b);
    nums.push(res);
}

int main() {
    cin >> s;
    string t(s.size(), '(');
    s = t + s + ')'; //预处理括号，保证左括号一定足够右括号匹配的

    for (int i = 0; i < s.size(); ++ i) 
        if (s[i] == '(') ops.push(s[i]);
        else if (s[i] >= '0' && s[i] <= '9') {
            int j = i, t = 0;
            while (s[j] >= '0' && s[j] <= '9') {
                t = t*10 + s[j] - '0';
                j++;
            }
            i = j-1;
            nums.push(t);
        } else if (s[i] == '-' && !(s[i-1] >= '0' && s[i-1] <= '9' || s[i-1] == ')')) { //特判出是负号
            nums.push(0); //增加一个0  相当于是把x 变为 0-x  形式
            ops.push(s[i]);
        } else if (s[i] == ')') {
            while (ops.top() != '(') cal();
            ops.pop(); //一直算到遇到左括号，最后在弹出左括号
        } else { //+ - * / ^
            while (mp[ops.top()] >= mp[s[i]]) cal();
            ops.push(s[i]); //最后在把si负号加入到栈中
        }
    while (ops.size()) {
        if (ops.top() == '(') ops.pop();
        else cal();
    }
    cout << nums.top();
    return 0;
}

参考题解： https://www.acwing.com/solution/content/120962/
把括号预处理到匹配： https://www.acwing.com/solution/content/64760/

yz总题解； https://www.acwing.com/solution/content/6405/

算法1：队列维护(模拟) $O(45*n)$

//用队列记录所有的优惠卷，每次查询优惠卷时，先出队过期的，然后再查找
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e5+10;
PII yhj[N];
int n, hh = 1, tt = 0, res; //队列从1开始使用，也可从0开始使用，注意好边界就可以

int main() {
    scanf("%d", &n);
    int t, x, op;
    while (n--) {
        scanf("%d%d%d", &op, &x, &t);
        if (op == 0)  yhj[++tt] = {t, x}; //记录优惠卷
        else {
            while (hh <= tt && t - yhj[hh].first > 45) hh++; //过滤掉过期的
            for (int i = hh; i <= tt; ++ i) //在没有过期的里面找最靠前的可用优惠卷
                if (yhj[i].second >= x) {
                    x = 0;
                    yhj[i].second = 0;
                    break;
                }
        }
        res += x;
    }
    printf("%d", res);
    return 0;
}

算法1：stl-queue维护(暴力枚举) $O(n)$

//维护每个小组内的顺序，1000个队列；循环小组间的顺序；1个队列
//用数组标记该编号小朋友属于那个组别；
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 1e6+10;
int tid[M], n; //标记编号属于那个小组

int main() {
    int c = 0;
    while (scanf("%d", &n), n) {
        printf("Scenario #%d\n", ++c);
        for (int i = 0; i < n; ++ i) { //n个小组
            int cnt, x;
            scanf("%d", &cnt); //小组的人数
            while (cnt--) {
                scanf("%d", &x);
                tid[x] = i; //编号x的人属于第i组  怎么知道每个人属于那个小组
            }
        }
        //维护出队列
        queue<int> preson[N]; //组内队列
        queue<int> team; //组间队列
        char op[25], ed[25] = "STOP";
        int x;
        while (scanf("%s", op), strcmp(op, "STOP")) {
            if (strcmp(op, "ENQUEUE") == 0) {
                scanf("%d", &x);
                int id = tid[x]; //获取属于的小组编号
                if (preson[id].empty()) team.push(id); //小组第一个，加入到team队列中
                preson[id].push(x);
            } else {
                int id = team.front(); //拿到team的队头 小组编号
                auto &q = preson[id]; //获取维护该小组的 组内的队列
                printf("%d\n", q.front()); //输出该队列的第一个
                q.pop();  //删除第一个
                if (q.empty()) team.pop(); //出队后，组内队列空了，从team中删除
            }
        }
        printf("\n");
    }
    return 0;
}

算法2：数组模拟队列() $O(n)$

//数组模拟队列
#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 1e6+10;
int tid[M];
int q[N][N], hh[N], tt[N]; //hh[x] tt[x] 表示第x个队列的头指针和尾指针

int main() {
    int c = 0, n;
    while (scanf("%d", &n), n) {
        printf("Scenario #%d\n", ++c);
        for (int i = 0; i < N; ++ i) { //初始化队列的队头和队尾
            hh[i] = 1;
            tt[i] = 0;
        }
        for (int i = 1, x, cnt; i <= n; ++ i) { //小组编号从1开始，0是维护组间队列的
            scanf("%d", &cnt);
            while (cnt--) {
                scanf("%d", &x);
                tid[x] = i; //记录x在第i组
            }
        }
        char op[35];
        int x;
        while (scanf("%s", op), op[0] != 'S') {
            if (op[0] == 'E') {
                scanf("%d", &x);
                int id = tid[x];
                if (hh[id] > tt[id]) q[0][++tt[0]] = id; //小组队列为空，是小组第一人
                q[id][++tt[id]] = x;
            } else {
                int id = q[0][hh[0]]; //获取组间队列的队头组号
                if (hh[id] <= tt[id]) printf("%d\n", q[id][hh[id]++]);
                if (hh[id] > tt[id]) hh[0]++; 
            }
        }
        printf("\n");
    }
    return 0;
}

算法1：数组模拟队列(枚举) $O(n)$

//数组标记是否出现，队列维护当前在内存中的单词
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int q[N], hh = 1, tt, st[N];
int n, m, res, x;

int main() {
    cin >> m >> n;
    while (n--) {
        cin >> x;
        if (st[x]) continue;
        res++; //查询
        st[x] = 1; //标记出现了
        if (tt-hh+1 == m) {
            st[q[hh]] = 0; //队头出队
            hh++;
        } 
        q[++tt] = x;
    }
    cout << res;
    return 0;
}

算法2：stl-queue() $O(n)$

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
int n, m, cnt;
int st[1010]; //哈希表

int main() {
    cin >> m >> n;
    while (n--) {
        int x;
        cin >> x;
        if (!st[x]) {
            cnt++;
            st[x] = 1;
            q.push(x);

            if (q.size() == m+1) {
                st[q.front()] = 0;
                q.pop();
            }
        }
    }
    cout << cnt;
    return 0;
}

算法1：数组模拟单链表存储-遍历单链表需要操作的数据放到数组中操作() $O(nlogn)$

//排序 排的是值，同时要输出地址 pair存储
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1E5+10;
PII a[N]; //值 和 该节点的地址 
int n, h, e[N], ne[N], cnt;

int main() {
    scanf("%d%d", &n, &h);
    for (int i = 0; i < n; ++ i) {
        int addr, data, nex;
        scanf("%d%d%d", &addr, &data, &nex);
        e[addr] = data;
        ne[addr] = nex;
    }
    for (int i = h; i != -1; i = ne[i])
        a[cnt++] = {e[i], i};
    sort(a, a+cnt);

    printf("%d ", cnt);
    if (cnt == 0) {
        printf("-1");
        return 0;
    }
    printf("%05d\n", a[0].second);
    for (int i = 0; i < cnt; ++ i) {
        printf("%05d %d ", a[i].second, a[i].first);
        if (i == cnt-1) printf("-1");
        else printf("%05d\n", a[i+1].second);
    }
    return 0;
}

算法2：结构体存储() $O(nlogn)$

//结构体存储单链表
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1E5+10;
struct node{
    int addr, data, next;
    bool operator< (const node& t) const{
        return data < t.data;
    }
}a[N];//存储地址和节点的映射
vector<node> res;
int h, n; 

int main() {
    scanf("%d%d", &n, &h);
    for (int i = 0; i < n; ++ i) {
        int addr, data, next;
        scanf("%d%d%d", &addr, &data, &next);
        a[addr] = {addr, data, next}; //
    }
    //存储出现在单链表中的节点，a中存下的是所有节点，有些节点并不在单链表上
    for (int i = h; ~i; i = a[i].next) 
        res.push_back(a[i]); 

    if (res.empty()) {
        printf("0 -1");
        return 0;
    }
    sort(res.begin(), res.end());
    printf("%d %05d\n", res.size(), res[0].addr);
    for (int i = 0; i < res.size(); ++ i) {
        printf("%05d %d ", res[i].addr, res[i].data);
        if (i == res.size() - 1) printf("-1\n");
        else printf("%05d\n", res[i+1].addr); //后面那个节点的地址
    }

    return 0;
}

算法1：单链表的遍历() $O(n)$

//用一个数组标记地址是否出现
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5+10;
int e[N], ne[N], h1, h2, n;
bool st[N]; //标记地址是否出现

int main() {
    scanf("%d%d%d", &h1, &h2, &n);
    for (int i = 0; i < n; ++ i) {
        int addr, nex;
        char data;
        scanf("%d %c %d", &addr, &data, &nex); //注意char型变量在scanf的时候会吃空格
        e[addr] = data;
        ne[addr] = nex;
    }
    for (int i = h1; ~i; i = ne[i]) st[i] = 1; //遍历第一个单链表，标记出现的节点
    int res = -1;
    for (int i = h2; ~i; i = ne[i]) //遍历第二个单链表
        if (st[i]) {
            printf("%05d", res);
            return 0;
        }
    printf("-1");
    return 0;
}

算法2：扫描两个单链表，扫完后到扫另一个() $O(n)$

//将两条链表长度划分为X + Z， Y + Z （Z为公共部分）
// 到达链尾就从另一个链表头结点继续走
// 1. 如果共享一个子链 X + Z + Y = Y + Z + X 一定在相交的子链入口处结束
// 2. 如果不同共享子链 X + Y = Y + X 到达链尾结束
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5+10;
int e[N], ne[N], h1, h2, idx, n;

int main() {
    scanf("%d%d%d", &h1, &h2, &n);
    for (int i = 0; i < n; ++ i) {
        int addr, nex;
        char data;
        scanf("%d %c %d", &addr, &data, &nex); //注意输入字符 中间加入空格
        e[addr] = data;
        ne[addr] = nex;
    }
    int i = h1, j = h2;
    while (i != j) {
        i = (i==-1 ? h2 : ne[i]);
        j = (j==-1 ? h1 : ne[j]);
    }
    if (i == -1 || j == -1) printf("-1");
    else printf("%05d", i);
    return 0;
}

• 同66. 两个链表的第一个公共结点

算法1：结构体标记(暴力枚举) $O(n^2)$

//初始每条线段都是一个单链表，结构体维护线段，标记是否被合并了，记录合并的个数
//n-合并个数就是总共出现的单链表个数，合并的时候标记 双重循环
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
struct node{
    string st, ed;
    bool f = 1;
}d[N];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> d[i].st >> d[i].ed;
    int cnt = 0; //记录合并了几个
    for (int i = 0; i < n; ++ i) 
        for (int j = i+1; j < n; ++ j) //遍历后面的即可
            if (d[i].ed == d[j].st && d[j].f) { //dj可以合并到di后面 且没有被合并过
                d[i].ed = d[j].ed;
                d[j].f = 0; //标记被合并
                cnt++;
            }
    cout << n - cnt << endl;
    for (int i = 0; i < n; ++ i)
        if (d[i].f) 
            cout << d[i].st << ' ' << d[i].ed << endl;
    return 0;
}

算法2：map维护() $O(n)$

//对每个单链表维护出头和尾的对应，map维护
//每条边必然属于某一个单链表，怎么找属于那个单链表，
//判断a->b a是否是某一个单链表的尾，还需要存储一下尾到头的映射
//通过尾找到头，改变他对应的尾，  尾对应的头也要作修改
#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_map<string, string> head, tail;
    string a, b;
    int n;

    cin >> n;
    while (n--) {
        cin >> a >> b;
        if (!tail.count(a)) head[a] = b, tail[b] = a;
        else head[tail[a]] = b, tail[b] = tail[a], tail.erase(a);
    }
    cout << head.size() << endl;
    for (auto &[k, v] : head)
        cout << k << ' ' << v << endl;
    return 0;
}

算法3：() $O(n^2)$

//直接用map维护出头尾映射，新边进来，直接遍历一遍map 判断是否是某一个的结尾，不是就加入
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, string> mp;
int n;
string a, b;

int main() {
    cin >> n;
    while (n--) {
        cin >> a >> b;
        bool f = 1;//默认a->b是一个新的链表
        for (auto& it : mp) //引用类型，要修改尾巴
            if (a == it.second) {//a是否个链表的尾巴，能接上，更新该链表的尾巴
                it.second = b;
                f = 0;
                break;
            }
        if (f) mp[a] = b;
    }
    cout << mp.size() << endl;
    for (auto it : mp)
        cout << it.first << ' ' << it.second << endl;
    return 0;
}

算法1：两个栈分别维护数字和符号-模拟() $O(n)$

//先算和后算的问题
#include <bits/stdc++.h>
using namespace std;

string s;
stack<int> num; //遇到乘法就拿出两个数相乘，数字全部加到栈中，最后栈全部加起来
stack<char> op;
unordered_map<char, int> prio = {{'+', 1}, {'*', 2}};

void cal() {//拿出数字栈中的两个数字，以及栈顶的符号出来计算，结果再放会数字栈
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();
    char c = op.top(); op.pop();
    if (c == '*') num.push(a * b % 10000);
    else num.push(a + b % 10000);
}

int main() {
    cin >> s;
    for (int i = 0; i < s.size(); ++ i) {
        if (s[i] >= '0' && s[i] <= '9') { //数字就加入栈中
            int x = 0, j = i;
            while (j < s.size() && s[j] >= '0' && s[j] <= '9') 
                x = x*10 + (s[j++] - '0');
            num.push(x);
            i = j-1;
        } else { //栈顶元素的优先级高就可以进行计算了
            while (op.size() && prio[op.top()] >= prio[s[i]]) cal();
            op.push(s[i]);
        }
    }
    while (op.size()) cal();
    cout << num.top() % 10000;
    return 0;
}

算法2：栈维护要计算的数字() $O(n)$

#include <bits/stdc++.h>
using namespace std;

const int N = 1E5+10;
int stk[N], tt = 1;
int x;
char op;
int main() {
    cin >> stk[1];
    while (cin >> op >> x) {
        //读入的时候就是分离的，边读入边判断是否可以计算
        if (op == '*') stk[tt] = x * stk[tt] % 10000;
        else stk[++tt] = x;
    }
    int res = 0;
    for (int i = 1; i <= tt; ++ i) 
        res = (res + stk[i]) % 10000;
    cout << res;
    return 0;
}

算法3：栈维护要计算的数字，变量记录上一个符号() $O(n)$

//如果是加减乘除都有的情况
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    stack<int> stk;
    cin >> s;
    int n = 0;
    char op = '+';
    for (int i = 0; i < s.size(); ++ i) {
        if (s[i] >= '0' && s[i] <= '9') 
            n = n*10 + s[i] - '0';
        if (s[i] == '+' || s[i] == '*' || i == s.size()-1) {
            if (op == '*') stk.top() = stk.top() * n % 10000;
            if (op == '+') stk.push(n);
            n = 0;
            op = s[i]; //记录上一个符号
        }
    }
    int res = 0;
    while (stk.size()) {
        res = (res + stk.top()) % 10000;
        stk.pop();
    }
    cout << res;
    return 0;
}

算法1：手写栈-模拟() $O(k*n)$

//出栈合法性判断，多了一个限制，栈的容量是限定了
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int stk[N], n, m, k, a[N];

int main() {
    scanf("%d%d%d", &m, &n, &k);
    while (k--) {
        for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
        int tt = 0, f = 1;
        for (int i = 1, j = 0; i <= n; ++ i) {
            stk[++tt] = i; //先进栈，按顺序进栈
            if (tt > m) { //容量超过，非法
                f = 0;
                break;
            }
            while (tt && stk[tt] == a[j]) { //只要当前栈顶元素和出栈序列匹配就一直出
                tt--;
                j++;
            }
        }
        if (tt) f = 0;
        if (f) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

算法2：stl容器-模拟() $O(k*n)$

//出栈合法性判断，多了一个限制，栈的容量是限定了
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, m, k, a[N];
bool check() {
    stack<int> stk;
    for (int i = 1, j = 0; i <= n; ++ i) {
        stk.push(i);
        if (stk.size() > m) return false;
        while (stk.size() && stk.top() == a[j]) {
            stk.pop();
            j++;
        }
    }
    return stk.empty();
}

int main() {
    scanf("%d%d%d", &m, &n, &k);
    while (k--) {
        for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
        if (check()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

算法3：模拟3() $O(k*n)$

//从出栈元素分析，x要出栈，则小于它的数必然都需要入栈
#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, m, k, a[N];
int stk[N], x;

int main() {
    scanf("%d%d%d", &m, &n, &k);
    while (k--) {
        int tt = 0, j = 1, f = 1; //j用来表示当前要入栈的值
        for (int i = 0; i < n; ++ i) {
            scanf("%d", &x); //x要出栈，此时栈顶元素小于x，就需要入栈，x才能入栈后再出栈
            while (!tt || stk[tt] < x && tt < m) stk[++tt] = j++;
            if (stk[tt] == x) tt--;
            else f = 0;
        }
        if (f) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

//区间的个数是确定的，n的阶加，每个区间的核心数是确定的，找到后在对应数组下标记录
#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
int cnt[N], res[N], bk[N];
int n, a[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> a[i];

    for (int i = 0; i < n; ++ i) {
        int cnt[N] = {};
        for (int j = i, h = 0; j < n; ++ j) {
            cnt[a[j]]++;
            if (cnt[a[j]] > cnt[h] || cnt[a[j]] == cnt[h] && a[j] < h) h = a[j];
            res[h]++;
        }
    }

    for (int i = 1; i <= n; ++ i)
        cout <<res[i] << ' ';
    return 0;
}