栈

学到栈了..先放一下模板吧！这个使用数组来模拟栈，STL不得不说真心好用啊,hhh！

#include
using namespace std;
const int N=10010;
int stk[N],tt;//tt表示栈顶下标
//插入 
stk[++tt]=x;
//删除
tt--;
//判断是否为空
if(tt>0) not empty;
else empty;
//栈顶
stk[tt]; 

下面再放一下c++STL里面的栈的用法：

//定义栈

function Stack () {
    this.dataStore = [];    //初始化为空
    this.top = 0;           //记录栈顶位置
    this.pop = pop;         //出栈
    this.push = push;       //入栈
    this.peek = peek;       //查看栈顶元素
    this.length = length;   //查看栈内元素总数
    this.clear = clear;     //清空栈
}

模拟栈：

实现一个栈，栈初始为空，支持四种操作：

1. push x – 向栈顶插入一个数 x">xx；
2. pop – 从栈顶弹出一个数；
3. empty – 判断栈是否为空；
4. query – 查询栈顶元素。

现在要对栈进行 M">MM 个操作，其中的每个操作 3">33 和操作 4">44 都要输出相应的结果。

输入格式

第一行包含整数 M">MM，表示操作次数。

接下来 M">MM 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1≤M≤100000">1≤M≤1000001≤M≤100000,
1≤x≤109">1≤x≤1091≤x≤109
所有操作保证合法。

输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

#include
using namespace std;
const int N=100010;
int stk[N],tt;
int main(){
    int n;
    cin>>n;
    while(n--)
    {
        string ch;
        cin>>ch;
        if(ch=="push")
        {
            int x;
            cin>>x;
            stk[++tt]=x;
        }
        else if(ch=="pop") tt--;
        else if(ch=="query") cout<endl;
        else if(ch=="empty") cout<<(tt?"NO":"YES")<<endl;
    }
    return 0;
}

 表达式求值：

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1">231?1231?1。
• 题目中的整除是指向 0">00 取整，也就是说对于大于 0">00 的结果向下取整，例如 5/3=1">5/3=15/3=1，对于小于 0">00 的结果向上取整，例如 5/(1−4)=−1">5/(1?4)=?15/(1?4)=?1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105">105105。

输入样例：

(2+2)*(1+1)

输出样例：

8
这题建议直接上acwing上看最高赞题解，写的很好很详细，tqltql！！
这题只要思路是什么呢/
正常的运算规律先乘除后加减，有括号先算括号。优先级高的直接先算，最后化为统一的优先级再一起计算（用哈希来实现）
但具体怎么实现呢：
在进行计算的时候，符号入栈时要先看看栈顶符号的优先级，如果栈顶优先级高于等于现在的，就先计算再入栈。
如果栈顶优先级小于现在的，可以直接入栈，等待后续操作。
如此操作下来，在括号里面从左往右的优先级是递增的！！！（看上面两行的解释！！）
在括号优先的情况下，根据就从右往左开始计算（高的优先级开始），最后全部都化为统一的符号，再从左往右进行操作就完事了，吼吼吼，自己可以出个操作来模拟一下：

#include
#include
#include<string>
#include
using namespace std;
stack<int> num;
stack<char> ch;
void eval(){
    auto b=num.top();num.pop();//第二个操作数 
    auto a=num.top();num.pop();//第一个操作数 
    auto c=ch.top();ch.pop();
    int x;
    if(c=='+') x=a+b;
    if(c=='-') x=a-b;
    if(c=='*') x=a*b;
    if(c=='/') x=a/b;
    num.push(x);
}
int main(){
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};//用哈希来定位优先级 
    string str;
    cin>>str;
    for(int i=0;i)
    {
        auto c=str[i];
        if(isdigit(c))
        {
            int x=0,j=i;
            while(j//把字符转化为整数 
                x=x*10+str[j++]-'0';
            i=j-1;//在上一步结束之后j++了，这里需要减一 
            num.push(x);
        }
        else if(c=='(')
            ch.push(c);//左括号直接入栈 
        else if(c==')')
        {
            while(ch.top()!='(') eval();//从右往左依次计算 
            ch.pop();//删去左括号，因为最后的计算是以有没有符号作为基准 
        }
        else{
            while(ch.size()&&pr[ch.top()]>=pr[c])
                eval();//在入栈之前检查一下 
            ch.push(c);//栈里的优先级都低于现在的，现在的入栈 
        }
    }
    while(ch.size())
        eval();//都统一了，没有括号，按照优先级开始计算（不过根据上面步骤，优先级越来越高） 
    cout<endl;
    return 0;
}