二、栈

0x00 最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。

    stack<int> s,mins;//mins栈同步存储当前栈内元素的最小值
    MinStack() {

    }

    void push(int x) {
        s.push(x);
        if(mins.empty()) mins.push(x);
        else mins.push(min(mins.top(),x));
    }

    void pop() {
        s.pop();
        mins.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return mins.top();
    }
0x01 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

    bool isValid(string s) {
        stack<char> stk;
        for(auto v : s){
            if(v=='('||v=='{'||v=='[') stk.push(v);//是左括号则直接入栈
            else if(stk.empty()) return false;//只有右括号没有左括号时显然不匹配
            else{
                int x = stk.top();
                stk.pop();
                if(v==')'&&x!='('||v=='}'&&x!='{'||v==']'&&x!='[') return false;//不匹配情况
            }
        }
        return stk.empty();//完整的匹配最后栈应该为空
    }
0x02 栈序列合法性

给定 pushed-进栈顺序 和 popped-给定的出栈顺序 两个序列，每个序列中的值都不重复，判断给出的出栈序列是否合法。

  示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输出：true 解释：我们可以按以下顺序执行：

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

输出：false

解释：1 不能在 2 之前弹出。

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int n = pushed.size();
        for(int i = 0,j=0; i < n; i++){//模拟进栈
            s.push(pushed[i]);//先直接进栈
            //然后根据出栈序列决定是否出栈
            while(!s.empty()&&j<n&&s.top()==popped[j]) s.pop(),j++;//出栈条件
        }
        return s.empty() ? true:false;//若合法，则此时栈一定是空的
    }
0x03 单调栈

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入样例： 5 3 4 2 7 5

输出样例： -1 3 -1 2 2

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N],tt,n,x;
int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d",&x);
        while(tt&&x<=stk[tt])tt--;
        //如果发现新来的x比栈顶元素更小 那么对于之后的数来说 栈内大于x的数便没有价值了
        //因为如果之后的数存在左侧更小值,那么会首先选择x,所以栈内大于x的没有价值了
        //
        if(tt==0) printf("-1 ");
        else printf("%d ",stk[tt]);
        stk[++tt] = x;
    }
    return 0;
}
0x04 逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

输入: ["10", "6", "9", "3", "+", "-11", "", "/", "", "17", "+", "5", "+"]

输出: 22

解释:

((10 (6 / ((9 + 3) -11))) + 17) + 5

= ((10 (6 / (12 -11))) + 17) + 5

= ((10 * (6 / -132)) + 17) + 5

= ((10 * 0) + 17) + 5

= (0 + 17) + 5

= 17 + 5

= 22

    int getv(string &s){
        int ans = 0;
        if(s[0]=='-'){
            for(int i = 1; i < s.size(); i++) ans = ans*10+s[i]-'0';
            return -ans;
        }
        else{
            for(auto v:s) ans = ans*10+v-'0';
            return ans;
        }
    }
    int calc(int a, int b, char op){
        if(op=='+') return a+b;
        else if(op=='-') return a-b;
        else if(op=='*') return a*b;
        else return a/b;
    }
    int evalRPN(vector<string>& t) {
        stack<int> stk;
        for(auto s : t){
            if(s[0]>='0'&&s[0]<='9'||s[0]=='-'&&s.size()>1) stk.push(getv(s));//读入数字 负数和减号需要特判
            else {//是运算符，则从栈顶弹出两个操作数 进行运算
                int b = stk.top();
                stk.pop();
                int a = stk.top();
                stk.pop();
                stk.push(calc(a,b,s[0]));
            }
        }
        return stk.top();
    }
0x05 表达式计算

给出一个表达式,其中运算符仅包含+,-,*,/,^（加 减 乘 整除 乘方）要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现大于或等于2^31的答案。

数据可能会出现负数情况。

输入格式 输入仅一行，即为表达式。

输出格式 输出仅一行，既为表达式算出的结果。

输入样例： (2+2)^(1+1)

输出样例： 16

#include<bits/stdc++.h>
using namespace std;
stack<char> ops;//运算符栈
stack<int> nums;//运算数栈
int quick_mi(int a, int b){//快速幂
    int t = a,ans = 1;
    while(b){
        if(b&1) ans*=t;
        t = t*t;
        b>>=1;
    }
    return ans;
}
void calc(){//执行一次计算
    int b = nums.top();
    nums.pop();
    int a = nums.top();
    nums.pop();
    char c = ops.top();
    ops.pop();
    int d;//结果
    if(c=='+') d = a + b;
    else if(c=='-') d = a - b;
    else if(c=='*') d = a * b;
    else if(c=='/') d = a / b;
    else d = quick_mi(a,b);
    nums.push(d);
}
int main(){
    string str,left;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>str;
    for(int i = 0; i < str.size(); i++) left += '(';
    str  = left+str+')';//在最左侧添加左括号，防止右括号过多
    for(int i = 0; i < str.size(); i++){
        if(str[i]>='0'&&str[i]<='9'){//读取正数
            int j = i,ta = 0;
            while(str[j]>='0'&&str[j]<='9') ta = ta*10+str[j]-'0',j++;//获得该数的值
            i = j-1;
            nums.push(ta);
        }
        else if(str[i]=='-'&&i&&!(str[i-1]>='0'&&str[i-1]<='9')&&str[i-1]!=')'){//读取负数 负号的判定，负号前如果是数字，则是减号,反之即可
            int j = i+1,ta = 0;
            while(str[j]>='0'&&str[j]<='9') ta = ta*10+str[j]-'0',j++;//获得该数的值
            i = j-1;
            nums.push(-ta);
        }
        else if(str[i]=='-'||str[i]=='+'){//+,-优先级最低 前面的可以先算了
            while(ops.top()!='(') calc();
            ops.push(str[i]);
        }
        else if((str[i]=='*'||str[i]=='/')){// * /时
            while(ops.top()=='*'||ops.top()=='/'||ops.top()=='^') calc();//前方可以算的条件
            ops.push(str[i]);
        }
        else if(str[i]=='^'){
            while(ops.top()=='^') calc();
            ops.push(str[i]);
        }
        else if(str[i]=='(') ops.push(str[i]);//左括号直接进
        else if(str[i]==')'){//括号内的此时一定是优先级递增 可以把括号里的都算了
            while(ops.top()!='(') calc();
            ops.pop();
        }
    }
    cout<<nums.top();
    return 0;
}
0x06 a进制数转为b进制数

编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。

这里有62个不同数位{0-9,A-Z,a-z}

输入

62 2 abcdefghiz

输出

62 abcdefghiz

2 11011100000100010111110010010110011111001001100011010010001

解释: 即把62进制的数 转为 2进制 并输出原数和转化后的数

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a,b;
    cin>>n;
    while(n--){
        string a_line,b_line;//a进制的a_line转为b进制的b_line
        vector<int> nums,res;//存储a_line代表的十进制数字,存储b_line代表的十进制数字
        cin >> a >> b >> a_line;
        for(auto v : a_line){//获得每一位的十进制真值
            if(v>='0'&&v<='9') nums.push_back(v-'0');
            else if(v>='A'&&v<='Z') nums.push_back(v-'A'+10);
            else nums.push_back(v-'a'+36);
        }
        reverse(nums.begin(),nums.end());//反转，从低位开始,易于处理高位的进位和删除
        while(nums.size()){//商不为零时,模拟短除法 直接将a进制转化为b进制
            int r = 0;//余数
            for(int i = nums.size()-1; i >=0 ; i--){
                nums[i] += r*a;//计算当前位的真值(相当于该位的十进制真值)
                r = nums[i] % b;//当前位除b后的余数
                nums[i]/=b;//当前位的商
            }
            res.push_back(r);//余数
            while(nums.size()&&nums.back()==0) nums.pop_back();//去除除法后高位的前导零
        }
        reverse(res.begin(),res.end());
        for(v:res){//十进制数组转化为字符表达
            if(v<10) b_line.push_back(v+'0');
            else if(v>=10&&v<36) b_line.push_back(v-10+'A');
            else b_line.push_back(v-36+'a');
        }
        cout<<a<<" "<<a_line<<endl;
        cout<<b<<" "<<b_line<<endl;
        cout<<endl;
    }
}