目录
7-1 括号匹配
7-2 后缀式求值
7-3 表达式转换
7-4 【模板】KMP字符串匹配
比较详细注释和图解请看KMP——字符串匹配-CSDN博客，（点击链接可跳转）一看就会
7-5 约瑟夫环（押题，重要）
7-6 单调栈（新题，有注释详解）
7-1 括号匹配
给定一串字符，不超过100个字符，可能包括括号、数字、字母、标点符号、空格，编程检查这一串字符中的( ) ,[ ],{ }是否匹配。
输入格式:
输入在一行中给出一行字符串，不超过100个字符，可能包括括号、数字、字母、标点符号、空格。
输出格式:
如果括号配对，输出yes，否则输出no。
输入样例1:
sin(10+20)
输出样例1:
yes
输入样例2:
{[}]
输出样例2:
no#include<stdio.h>
char stack[10086];
int top=-1;
void push(char x)
{stack[++top]=x;
}
int pop()
{if(top==-1)return 0;elsereturn stack[top--];
}
int peidui(char str[])
{int i;int len=strlen(str);while(str[i]!='\0'){if(str[i]=='('||str[i]=='['||str[i]=='{')push(str[i]);else if(str[i]==')'||str[i]==']'||str[i]=='}'){if(top==-1||str[i]-pop()>2)return 0;}i=i+1;}return(top==-1);
}
int main()
{char str[10086];fgets(str,sizeof(str),stdin);if(peidui(str))printf("yes");elseprintf("no");return 0;
}7-2 后缀式求值
我们人类习惯于书写“中缀式”，如 3 + 5 * 2 ，其值为13。 (p.s. 为什么人类习惯中缀式呢？是因为中缀式比后缀式好用么？）
而计算机更加习惯“后缀式”（也叫“逆波兰式”，Reverse Polish Notation）。上述中缀式对应的后缀式是： 3 5 2 * +
现在，请对输入的后缀式进行求值。
输入格式:
在一行中输入一个后缀式，运算数和运算符之间用空格分隔，运算数长度不超过6位，运算符仅有+ - * / 四种。
输出格式:
在一行中输出后缀式的值，保留一位小数。
输入样例:
3 5.4 2.2 * +
输出样例:
14.9#include<stdio.h>
int main()
{char str[10086];double st[10086];int i=0;while(scanf("%s",str)!=EOF){if(str[1]=='\0'&&(str[0]=='+'||str[0]=='-'||str[0]=='*'||str[0]=='/')){double num1,num2,current;num1=st[--i];num2=st[--i];switch(str[0]){case'+':current=num2+num1;st[i++]=current;break;case'-':current=num2-num1;st[i++]=current;break;case'*':current=num2*num1;st[i++]=current;break;case'/':current=num2/num1;st[i++]=current;break;}}else{double num;sscanf(str,"%lf",&num);st[i++]=num;}}printf("%.1f",st[0]);return 0;
}7-3 表达式转换
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/以及左右括号()，表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。
输入样例:
2+3*(7-4)+8/4
输出样例:
2 3 7 4 - * + 8 4 / +#include<stdio.h>
#include<string.h>
void print()
{static int flag=0;if(flag!=0)putchar(' ');flag++;
}
int main()
{char stack[10086];char str[10086];int top=-1,i;gets(str);int len=strlen(str);for(i=0;i<len;i++){if((str[i]=='+'||str[i]=='-')&&(i==0||str[i-1]=='(')||isdigit(str[i])){print();if(str[i]!='+')putchar(str[i]);while(str[i+1]=='.'||isdigit(str[i+1]))putchar(str[++i]);}else{if(str[i]==')'){while(top!=-1&&stack[top]!='('){print();putchar(stack[top--]);}if(top!=-1){top--;}}else{if(top==-1){stack[++top]=str[i];}else{while(top>-1&&stack[top]!='('){if(str[i]=='('||((str[i]=='*'||str[i]=='/')&&(stack[top]=='+'||stack[top]=='-'))){break;}print();putchar(stack[top--]);}stack[++top]=str[i];}}}}while(top>-1){if(stack[top]=='(')top--;elseprint();putchar(stack[top--]);}return 0;
}7-4 【模板】KMP字符串匹配
比较详细注释和图解请看KMP——字符串匹配-CSDN博客，（点击链接可跳转）一看就会
给出两个字符串text和pattern，其中pattern为text的子串，求出pattern在text中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next。
输入格式:
第一行为一个字符串，即为text。
第二行为一个字符串，即为pattern。
输出格式:
若干行，每行包含一个整数，表示pattern在text中出现的位置。
接下来1行，包括length(pattern)个整数，表示前缀数组next[i]的值，数据间以一个空格分隔，行尾无多余空格。
输入样例:
ABABABC
ABA
输出样例:
1
3
0 0 1
样例说明:
#include<stdio.h>
#include<string.h>
int main()
{char a[1000010],b[1000010];int next[1000010];scanf("%s %s",a+1,b+1);int m=strlen(a+1),n=strlen(b+1);int i,j=0;for(i=2;i<=n;i++){while(j&&b[i]!=b[j+1]){j=next[j];}if(b[i]==b[j+1]){j++;}next[i]=j;}j=0;for(i=1;i<=m;i++){while(j&&a[i]!=b[j+1]){j=next[j];}if(a[i]==b[j+1])j++;if(j==n){printf("%d\n",i-n+1);j=next[j];}}for(i=1;i<=n;i++){if(i==n) printf("%d",next[i]);elseprintf("%d ",next[i]);}return 0;
}7-5 约瑟夫环（押题，重要）
N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
请按退出顺序输出每个退出人的原序号。
输入格式:
输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。
输出格式:
按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。
输入样例:
在这里给出一组输入。例如：
7 3
输出样例:
3 6 2 7 5 1 4#include<stdio.h>
#include<string.h>
void print()
{static int flag=0;if(flag!=0)putchar(' ');flag++;
}
int main()
{char stack[10086];char str[10086];int top=-1,i;gets(str);int len=strlen(str);for(i=0;i<len;i++){if((str[i]=='+'||str[i]=='-')&&(i==0||str[i-1]=='(')||isdigit(str[i])){print();if(str[i]!='+')putchar(str[i]);while(str[i+1]=='.'||isdigit(str[i+1]))putchar(str[++i]);}else{if(str[i]==')'){while(top!=-1&&stack[top]!='('){print();putchar(stack[top--]);}if(top!=-1){top--;}}else{if(top==-1){stack[++top]=str[i];}else{while(top>-1&&stack[top]!='('){if(str[i]=='('||((str[i]=='*'||str[i]=='/')&&(stack[top]=='+'||stack[top]=='-'))){break;}print();putchar(stack[top--]);}stack[++top]=str[i];}}}}while(top>-1){if(stack[top]=='(')top--;elseprint();putchar(stack[top--]);}return 0;
}7-6 单调栈（新题，有注释详解）
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入格式:
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式:
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
数据范围:
1≤N≤105
1≤数列中元素≤109
输入样例:
在这里给出一组输入。例如：
5
3 4 2 7 5
输出样例:
在这里给出相应的输出。例如：
-1 3 -1 2 2 //此题要求解出每个数左边第一个比它小的数
//我们把左边已经输入的数存放到一个栈中，因为栈的特性是后进先出
#include<iostream>
using namespace std;
const int N=100010;
int n;
int stk[N],tt;
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++){int x;scanf("%d",&x);while(tt&&stk[tt]>=x){tt--;//tt不为0，且stk[tt]>=x，也就是stk里面这个数大于目标值，他不应该在里面，弹出即可}if(tt) printf("%d ",stk[tt]);//如果上述条件都满足了，那说明stk里面的值就是第一个小于x的值，输出else printf("-1 ");//如果都弹出去完了，tt为0了，也就说明stk里面为空，空的话就不用就一定没有，输出-1stk[++tt]=x;//然后将x放进栈中}return 0;
}
