MT2135调整队伍
马蹄集：链表
小码哥迎来了他大学的第一次军训，军训的第一个项目就是列队，每个同学在队伍中都有属于自己的编号。但在练习过程中，教官怎么看这支队伍怎么不顺眼，于是决定调整一下队伍的顺序。
为了顺便考验同学们的反应力，教官与学生们约定了一个口令，每当他说x y 0，x号同学就要移动到y号同学的前面，每当他说x y 1，x号同学就要移动到y*号同学的后面，但学生们不想一次次慢慢移动这么麻烦，想要知道队伍最后是怎么排的然后直接排好。为了解决同学们的烦恼，小码哥立刻动手原地写了一个程序算出了最终排序。
现在告诉你队伍从前到后的初始排序编号以及教官的口令，要你得出队伍从前往后的最终排序。已知有n个学生，编号不重复且1≤编号≤n1≤编号≤n。
格式
输入格式：
第一行两个正整数n，m，表示学生的数量和教官口令的数量；
第二行n个正整数，表示学生们的初始排序；
接下来m行，每行3个整数，表示教官的口令。
输出格式：
nn个数字，每个数字之间用空格隔开，表示队伍从前往后的最终排序。
样例 1
输入：
10 5
8 4 6 7 9 3 5 10 1 2
4 9 0
10 5 1
3 9 0
1 9 1
3 6 0
输出：
8 3 6 7 4 9 1 5 10 2
AC代码：
#include<iostream>
using namespace std;
//这是一个实现循环链表，操作数字前插尾插的操作代码；
const int ma=3e5+7;
struct add{
int l; //左节点；
int r; //右节点；
}insert[ma];
int n,m,ne,head;
int main(){
cin >> n >> m;
//初始化，实现把输入的各各节点已链表的形式连接起来；
while(n--){
int tt;
cin >> tt;
insert[tt].l=ne;
insert[ne].r=tt;
ne=tt;
}
while(m--){
int x,y,op;
cin >> x >> y >> op;
//记录要操作的左右节点；
int i=insert[x].l,j=insert[x].r;
//不管怎样都是要实现删除；
//在外头就实现删除，让操作的左节点的右指针指向右节点的左指针；
//在里头就只要实现插入操作；
insert[i].r=j,insert[j].l=i;
i=insert[y].l,j=insert[y].r;
if(op){
//循环链表基操；
//操作数后插操作；
insert[x].l=y;
insert[x].r=j;
insert[y].r=x;
insert[j].l=x;
}else{
//操作数前插操作；
insert[x].l=i;
insert[x].r=y;
insert[y].l=x;
insert[i].r=x;
}
}
//这里刚开始会有点迷；
//这里主要实现从头(0节点)的右节点开始；
ne=insert[head].r;
//直到遇到一个非正数的数值(/n)等等停止；
while(ne){
cout << ne << " ";
ne=insert[ne].r;
//一直指向下一个右节点；
}
return 0;
}
MT2114括号家族
马蹄集：栈
小码哥在研究只有左括号和右括号组成的序列。给出一个括号序列，求出最长合法子串和它的数量（合法的定义：这个序列中左右括号匹配）。
例如:(()不合法，)()(也不合法，但()()和(())合法。
格式
输入格式：
输入一行只有左括号和右括号组成的序列（只包含小括号）。
输出格式：
输出两个数字：最长子字符串的长度，以及此类子字符串的数量，如果没有这样的子字符串，则输出0 1。
样例 1
输入：
()()))()()(()
输出：
4 2
备注
其中：字符串长度小于等于 10^6;
AC代码：
#include<iostream>
#include<stack>
#include<map>
using namespace std;
//这算个是栈的最最基础代码(主要是用到的两常用容器，下次在见就是复习了)
const int N=10000010;
//pair<char,int>定义映射两种类型；
stack<pair<char,int>> st;
int arr[N]={0};
int main(){
string s;
cin >> s;
int len=s.size();
for(int i=0;i<len;i++){
//左括号操作；
if(s[i]=='('){
//映射左括号，以及它的下标；
pair<char,int> tmp(s[i],i);
//压入栈中；
st.push(tmp);
}else{
//如果栈中是左括号遇到右括号，标记对应的左右括号为 1；
//first这里代表char类型的操作；
if(!st.empty() && st.top().first=='('){
//st.top(),second:栈头元素的int类型进行操作；
//这里就让int类型的操作赋值为 1；
//arr[i]右括号赋值为 1；
arr[i]=arr[st.top().second]=1;
//栈顶出栈(左括号)；
st.pop();
}else{
//俩都不是就继续压入栈中；
pair<char,int> tmp(s[i],i);
st.push(tmp);
}
}
}
//map老朋友了，这里ans记录长度，mp[ans]计入个数；
map<int,int> mp;
int ans=0,ct=0;
for(int i=0;i<len;i++){
if(arr[i]==1){
ct++;
}else{
if(ct>=ans){
ans=ct;
mp[ans]++;
}
ct=0;
}
}
// 在代码中，ct 用于计算当前有效括号的数量，而 ans 用于记录最大有效括号的长度。
// 当遇到无效括号时，代码会检查当前有效的长度 ct 是否大于等于 ans，如果是，就更新 ans 并重置 ct 为0。
// 但是，在循环结束后，如果最后有一段有效的括号（例如字符串以有效括号结尾），就要再次检查 ct。
// 这就是后面的 if(ct >= ans) 这一段的目的，以确保我们不会遗漏最后的有效长度。
if(ct>=ans){
ans=ct;
mp[ans]++;
}
if(ans==0) cout << "0 1" << endl;
else cout << ans << " " << mp[ans] << endl;
return 0;
}
后缀表达式的值
一本通：栈
从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。
比如，16–9(4+3)转换成后缀表达式为：16□9□4□3□+–，在字符数组A中的形式为：
栈中的变化情况：
运行结果：-47
提示：输入字符串长度小于250，参与运算的整数及结果之绝对值均在264264范围内，如有除法保证能整除。
【输入】
一个后缀表达式。
【输出】
一个后缀表达式的值。
【输入样例】
16 9 4 3 +*-@
【输出样例】
-47
AC代码:
解法一：数组；
(这个仅供参考)
#include<iostream>
#include<cstring>
using namespace std;
const int Ma=100010;
long long a[Ma];
int con=0;
int main(){
string s;
getline(cin,s);
int n=s.size();
int x=0;
for(int i=0;i<n;i++){
if(s[i]=='+'){
a[con-2]+=a[con-1];
con--;
}else if(s[i]=='-'){
a[con-2]-=a[con-1];
con--;
}else if(s[i]=='*'){
a[con-2]*=a[con-1];
con--;
}else if(s[i]=='/'){
a[con-2]/=a[con-1];
con--;
}else{
while(i<n && s[i]>='0' && s[i]<='9'){
x=x*10+s[i]-'0';
i++;
}
a[con++]=x;
x=0;
}
}
cout << a[0] << endl;
return 0;
}
解法2：栈操作；
#include<iostream>
#include<stack>
#include<string>
using namespace std;
stack<long long> st;
string s;
int main(){
getline(cin,s);
int n=s.length();
for(int i=0;i<n-1;i++){
if(s[i]>='0' && s[i]<='9'){
long long x=0;
while(s[i]>='0' && s[i]<='9'){
x=x*10+s[i]-'0';
i++;
}
st.push(x);
}
if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/'){
long long k,l;
k=st.top();
st.pop();
l=st.top();
st.pop();
if(s[i]=='+') st.push(l+k);
if(s[i]=='-') st.push(l-k);
if(s[i]=='*') st.push(l*k);
if(s[i]=='/') st.push(l/k);
}
}
cout << st.top() << endl;
return 0;
}
中缀表达式值(expr)
一本通：栈
输入一个中缀表达式（由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。
注意：必须用栈操作，不能直接输出表达式的值。
【输入】
一行为一个以@结束的字符串。
【输出】
如果表达式不合法，请输出“NO”，要求大写。
如果表达式合法，请输出计算结果。
【输入样例】
1+2*8-9@
【输出样例】
8
AC代码：
#include <iostream>
#include <stack>
#include<string>
using namespace std;
const int Ma=100010;
//创建一个结构体：存储后缀表达式运算符和操作数
struct Node{
int n; //数值
char c; //运算符
}eq[Ma];
string s;
int p; // 后缀表达式的索引
int pri[128]; // pri[i]: ascii码为i的运算符的优先级
//运算符优先级：
void initpri(){
pri['(']= 4;
pri['*']=pri['/']= 3;
pri['+']=pri['-']= 2;
pri[')']= 1;
}
// 计算给定的两个数字和运算符的结果
int calc(int a, int b, char c)
{
switch(c)
{
case '+':
return a + b; // 加法
case '-':
return a - b; // 减法
case '*':
return a * b; // 乘法
case '/':
return a / b; // 除法
}
}
bool Chva(char c){
return c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')';
}
bool legal(){
stack<char> st;
for(int i=0;i<s.length();i++){
//判断匹配问题；
if(s[i]=='('){
st.push(s[i]);
}else if(s[i]==')'){
if(st.empty()){
return false; //在栈为空的情况下，单进右括号？？？
}else{
st.pop(); //栈不空，出栈；
}
}
}
if(!st.empty()) return false; //栈不为空的情况下，还有括号？？？
//判断‘-’当负号处理；
for(int i=0;i<s.length();i++){
//细节：如果第一位是负号，则将其变为‘0’+‘-’,到时候在数字操作中就变成了 0-x, 0-任何正数都得-数；
if(i==0 && s[i]=='-'){
s='0'+s;
}else if(s[i]=='-' && s[i-1]=='('){ //这里就是（-2+3）这种情况，在‘-’前面插入一个‘0’；
s.insert(i,"0"); //为什么不考虑-（2+3）这种情况？出现这种情况是只会出现在头
} //在中途的话是当减号处理的；
//判断算式头尾问题；(要知道正常的算式头和尾都是数字，或者左右括号，唯一的负号开头，已经在上添加了‘0’开头)
if(Chva(s[0]) && s[0]!='('){ //头
return false;
}
int len=s.length()-1; //尾
if(Chva(s[len]) && s[len]!=')'){
return false;
}
}
for(int i=0;i<s.length();i++){
if(Chva(s[i]) && Chva(s[i+1])){
if(s[i]==')' && s[i+1]=='('){
return false;
}else if(!(s[i]==')' || s[i+1]=='(')){ //细节：如果两个字符都能匹配的只有左边是‘)’ ，右边是‘(’ ;
return false; //打个比方：s[i]=='+',就继续判断s[i+1]=='('; 1+(2+2);
} //s[i]==')',s[i+1]=='+'; (1+2)+3;
}
}
return true; //上述都不满足，就输出true;
}
// 递归求解后缀表达式
int Postfix()
{
int i = p--; // 从后缀表达式中取出当前操作数或运算符的索引
if(eq[i].c) // 如果当前是运算符
{
int b = Postfix(); // 递归求解第二个操作数
int a = Postfix(); // 递归求解第一个操作数
return calc(a, b, eq[i].c); // 返回计算结果
}
else{
return eq[i].n; // 如果是数字，直接返回
}
}
int main(){
//初始化优先级表；
initpri();
cin >> s;
//首先判断表达式是否合法；
if(legal()==false){
cout << "NO" << endl;
return 0;
}
//创建栈；
stack<char> cSta;
bool flag=false;
int ans=0;
//直接转后缀表达式，如果不是合理表达式,直接输出no,在转后缀表达式，判断如果是合法，求出结果；这到不如直接合并解决；
//将中缀表达式转换为后缀表达式；
for(int i=0;i<s.size();i++){
if(s[i]>='0' && s[i]<='9'){
flag=true;
ans=ans*10+s[i]-'0';
}else {
if(flag){
eq[++p].n=ans;
flag=false;
ans=0;
}
//这个!() 刚开始一直没理解什么意思;
//现在解释：先判断括号里的条件，从cSta开始判断，以此不满足就 || ；(get这句话)
//括号里判断成功说明，条件true,在到括号外取反跳出循环；(get这句话)
//get到上两句的话：就方便实现，最后一个cSta.top()是'('问题；左右括号其实就是判断条件，并不入栈；
while(!(cSta.empty() || pri[s[i]]>pri[cSta.top()] || cSta.top()=='(')){
eq[++p].c=cSta.top();
cSta.pop();
}
//结合上面:手推算式就知道这个判断括号问题了；
if(!cSta.empty() && cSta.top()=='(' && s[i]==')'){
cSta.pop();
}else{
cSta.push(s[i]);
}
}
}
cout << Postfix() << endl;
return 0;
}