總目錄詳見：https://blog.csdn.net/mrcrack/article/details/86501716
資訊學奧賽一本通（C++版） 第三部分 資料結構 第一章 棧
http://ybt.ssoier.cn:8088/
//1331 【例1-2】字尾表達式的值
//該題 一本通 的線上測評，一送出就說逾時，同樣的題目 在洛谷
//https://www.luogu.org/problem/show?pid=1449 同樣的代碼，一送出就AC
//P1449 字尾表達式
//以下代碼為 洛谷AC 代碼，卻在 一本通 逾時代碼
//2017-10-26 21:30
//将讀取代碼修改，不再逾時，卻報答案錯誤，看來有必要翻翻原書了。
//下述代碼，在洛谷再次通過
//輸入：
//16 9 4 3 +*-@
//輸出：
//-47
//1331 【例1-2】字尾表達式的值
//該題擱置很久，《資訊學奧賽一本通(C++版)》題解已不适合該題了，翻看該題
//發現：添加了提示“提示：輸入字元串長度小于250，參與運算的整數及結果之絕對值均在264範圍内，如有除法保證能整除。”
//将int改成long long 送出，AC 2017-12-25
#include <stdio.h>
#include <string.h>
char a[10000];
long long stack[1000],top=-1;//此處寫成 int stack[1000],top=-1;
int main(){
long long k=0,i,len,b,tag,d,e,f;//此處寫成 int k,i,len,b,tag,d,e,f;
char c;
gets(a);
len=strlen(a);
i=0;
while(i<len){
b=0,tag=0;
while(i<len&&'0'<=a[i]&&a[i]<='9')b*=10,b+=a[i]-'0',i++,tag=1;
if(tag)top++,stack[top]=b;
else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){
d=stack[top],top--;
e=stack[top],top--;
switch(a[i]){
case '+':
f=e+d;
break;
case '-':
f=e-d;
break;
case '*':
f=e*d;
break;
case '/':
f=e/d;
break;
}
top++;
stack[top]=f;
i++;
}else
i++;
}
printf("%lld",stack[top]);
return 0;
}
//1331 【例1-2】字尾表達式的值
//該題 一本通 的線上測評，一送出就說逾時，同樣的題目 在洛谷
//https://www.luogu.org/problem/show?pid=1449 同樣的代碼，一送出就AC
//P1449 字尾表達式
//以下代碼為 洛谷AC 代碼，卻在 一本通 逾時代碼
//2017-10-26 21:30
#include <stdio.h>
#include <string.h>
char a[10000];
int stack[1000],top=-1;
int main(){
int k=0,i,len,b,tag,d,e,f;//此處寫成 int k,i,len,b,tag,d,e,f;
char c;
while((c=getchar())!='@')
a[k++]=c;
a[k]='\0';
len=strlen(a);
i=0;
while(i<len){
b=0,tag=0;
while(i<len&&'0'<=a[i]&&a[i]<='9')b*=10,b+=a[i]-'0',i++,tag=1;
if(tag)top++,stack[top]=b;
else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){
d=stack[top],top--;
e=stack[top],top--;
switch(a[i]){
case '+':
f=e+d;
break;
case '-':
f=e-d;
break;
case '*':
f=e*d;
break;
case '/':
f=e/d;
break;
}
top++;
stack[top]=f;
i++;
}else
i++;
}
printf("%d",stack[top]);
return 0;
}
//1353 表達式括号比對(stack)
#include <stdio.h>
#include <string.h>
int stack[1000],top=-1;
char a[10000];
int main(){
int i,len;
scanf("%s",a);
len=strlen(a);
for(i=0;i<len;i++)
if(a[i]=='(')top++,stack[top]=1;//( 1
else if(a[i]==')'){
if(top>=0)top--;
else top++,stack[top]=2;//) 2
}
if(top==-1)printf("YES");
else printf("NO");
return 0;
}
//1354 括弧比對檢驗
//該題說明如下：
//題目中的字元串根本不能用，夾雜着中文的括号，英文的空格
//要進行測試，讀者隻能自行輸入英文的符号2017-10-26 22:27
#include <stdio.h>
#include <string.h>
char a[1000];
int stack[1000],top=-1;//(1 )2 [3 ]4
int main(){
int i,len;
scanf("%s",a);
len=strlen(a);
for(i=0;i<len;i++)
if(a[i]=='(')top++,stack[top]=1;
else if(a[i]==')'){
if(top==-1)top++,stack[top]=2;
else if(stack[top]==1)top--;
else top++,stack[top]=2;
}else if(a[i]=='[')top++,stack[top]=3;
else if(a[i]==']'){
if(top==-1)top++,stack[top]=4;
else if(stack[top]==3)top--;
else top++,stack[top]=4;
}
if(top==-1)printf("OK");
else printf("Wrong");
return 0;
}
//1355 字元串比對問題(strs)
//一月前編寫此題，一個多小時，送出，未果，擱置
//http://blog.csdn.net/ametake/article/details/43987407此文寫得不錯，吸引本人原因，代碼寫得夠短
//第一步，将字元映射成數字，處理起來友善
//樣例通過，送出,測試點2,3,5答案錯誤
//反複閱讀代碼，覺得所有情況都考慮周全，很需要上述三個測試點資料，無奈，在http://codevs.cn/problem/3543/送出研究
//在上述網站找到一組測試資料：
//輸入：
//6
//{}{}<><>()()[][]
//{{}}{{}}<<>><<>>(())(())[{}][[]]
//{{}}{{}}<<>><<>>(())(())[[]][[]]
//{<>}{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
//><}{{[]}<<<>><<>>>((<>))(())[[(<>)]][[]]
//([])
//輸出：
//YES
//NO
//YES
//YES
//NO
//NO
//對照上述例子，發現，top未在每次讀取新字元串時，初始化為0，難怪這個錯誤怎麼找都找不到，原來是初始化的問題。
//codevs裡送出AC，ybt裡送出AC,2017-12-9 12:33
#include <stdio.h>
#include <string.h>
char a[]={'{','[','(','<','}',']',')','>'},s[300];//{0 }4 [1 ]5 (2 )6 <3 >7
int b[300],stack[300],top;//b[i]與s[i]一一映射
int main(){
int t,len,i,j,k,flag;//flag合法，非法标記
scanf("%d",&t);
while(t--){
flag=1,top=0;//漏了top=0這句，查了好久
scanf("%s",s);//此處寫成 scanf("%d",s); 盡出昏招
len=strlen(s);
for(i=0;i<len;i++)//建立字元與數字的一一映射關系
for(j=0;j<8;j++)
if(s[i]==a[j]){
b[i]=j;
break;
}
i=0;
while(i<len){//是否比對處理
//printf("b[%d]=%d\n",i,b[i]);
if(b[i]<=3)//b[i]元素想要入棧
if(top==0||b[i]>=stack[top]){//b[i]元素可以入棧，top==0棧為空，或棧内符号滿足嵌套關系
top++,stack[top]=b[i];
}else{//b[i]元素無法入棧，該組資料非法，結束該組資料處理
flag=0;
break;
}
else if(b[i]>=4){//b[i]元素希望與棧内元素配對
if(top>0&&stack[top]+4==b[i]){//首先棧内要有元素，同時判斷是否配對
top--;
}else{//無法配對，結束 該組資料處理
flag=0;
break;
}
}
i++;
}
if(top)printf("NO\n");//棧内有元素，比對不成功
else if(flag==1)printf("YES\n");//棧内無元素，比對成功
else printf("NO\n");//棧内無元素，比對不成功
}
return 0;
}
//1356 計算(calc)
//http://www.oier.cc/ssoj2461%e8%ae%a1%e7%ae%97/研究此文代碼,思路摘抄如下：
//一個資料棧，一個運算符棧，遇到資料，資料進資料棧，遇到運算符，運算符進運算符棧。
//最後計算的時候，從棧頂開始計算：取出一個運算符和兩個資料，把計算結果壓回資料棧，
//直到運算符棧為空，資料棧的那個資料即是答案。
//按照上述方法，則靠近棧頂的運算符優先級高，靠近棧底的運算符優先級低。
//如果在進棧過程中，出現棧頂的優先級比前一個運算符優先級低（不高于），怎麼辦？
//那肯定是先計算前面的運算符。是以，在運算符壓棧過程中，讀入後一個資料前（43行代碼），
//如果前面有應該先算的運算符（優先級高或者同級），則先算前面的。
//最後一個問題，就是括号問題了。左括号是在擷取資料時遇到的，這是先把括号當運算符壓棧，
//i+1略過這個左括号後再繼續擷取資料。當遇到右括号時，運算符棧中，前一個左括号後面的運算符都要先算，
//則一直算到左括号（39行代碼）。在判斷優先級時，括号優先級很高，但左括号不能運算，故遇到括号不算，
//至少在遇到右括号時一直退棧。
//抄寫此代碼，送出AC。
//經測試，http://ybt.ssoier.cn:8088 該題背景測試資料有誤，基本可以确定背景測試資料是根據 系統自帶的 pow函數算出，請注意pow函數 傳回值時double，轉成整數，存在誤差
//采用自編的my_pow函數 ，測試點2-4 答案錯誤，基本确認，這三個測試點的輸出資料是錯誤的
//提供一組測試樣例
//輸入:
//(1-2+3-4+5-6+7-8+9-10+(10^2*2+2)/2-1)^3
//輸出：
//857375
//采用 系統自帶 pow 針對上述樣例 算出過程如下：
//a[n-1]=10 a[n]=2
//a[n-1]=99
//a[n-1]=94 a[n]=3
//a[n-1]=830584
//830584
//故 經驗證 測試點2-4 的輸出資料 有誤。2018-1-5
//編寫下來的感覺是，對i的處理還需改進，什麼時候i++,什麼時候還是用i，很依賴程式設計者的思維
//樣例通過，送出AC 2018-1-5 21:39
#include <stdio.h>
#include <math.h>
int a[2000],n=0,i=0,m=0;//資料棧 n标記資料棧中位置 i标記字元串位置 m标記運算符棧中位置 請注意i=0
char s[2000],b[2000],c[300];//s字元串，b運算符棧 ,運算符優先級設定
void compute(){
switch(b[m-1]){//自左往右計算
case '+':a[n-1]+=a[n];break;
case '-':a[n-1]-=a[n];break;
case '*':a[n-1]*=a[n];break;
case '/':a[n-1]/=a[n];break;
case '^':a[n-1]=pow(a[n-1],a[n]);break;//此處不用系統自帶的pow無法通過所有測試點
}
b[m-1]=b[m],m--,n--;//出棧，運算符棧，資料棧
}
int can(){
if(c[b[m-1]]==4||c[b[m]]==4)return 0;//判斷是否有'(' 左括号
if(c[b[m-1]]>=c[b[m]])return 1;//此處寫成if(c[b[m-1]]>c[b[m]])return 1;//左邊運算符優先級高于右邊運算符，可以計算
return 0;//其它情況都是 無法計算
}
int getint(){//獲得整數
int ans=0;
if(s[i+1]=='('){//遇到'('的處理
b[++m]=s[++i];//将'('存入 運算符棧
return getint();//遞歸調用
}
while('0'<=s[++i]&&s[i]<='9')ans=ans*10+s[i]-'0';//注意此處技巧s[++i]//脫出循環時i已經指向非整數位置
return ans;
}
int main(){
c['+']=c['-']=1,c['*']=c['/']=2,c['^']=3,c['(']=c[')']=4;//設定運算符優先級
scanf("%s",s+1);//存儲字元串，從 s[1]開始
a[++n]=getint();
while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='^'||s[i]==')'){//此句寫得很妙，無需判斷字元串長度了//右括号
b[++m]=s[i];
if(s[i]==')'){//右括号要單獨處理
while(b[m-1]!='(')compute();
m-=2,i++;//i++目的，讀取')'，若是其他運算符，在getint()函數裡，會運算下一個i值，即i+1//此句寫成m-=2;//彈出左右括号
continue;
}
while(m>1&&can())compute();
a[++n]=getint();//此處寫到大的while循環之外
}
m++;//必須空算一次
while(m>1)compute();
printf("%d",a[1]);
return 0;
}
//1357 車廂排程(train)
//https://www.cnblogs.com/zxqxwnngztxx/p/6679727.html代碼寫得精煉
//該題思維量比較大，2017-12-11 AC
#include <stdio.h>
int a[1010],b[1010],top=0;
int main(){
int n,i,cur;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);//a[i]為到達B站的車廂
b[0]=0;
for(i=1,cur=1;i<=n;i++){//模拟進棧,到達A站，出棧,到達B站，模拟
while(b[top]<a[i])top++,b[top]=cur,cur++;//比a[i]小的車廂都要在棧中 cur為需要進棧的車廂，這個要求技巧比較高
if(b[top]==a[i])top--;//将a[i]彈出棧
else{
printf("NO");
return 0;
}
}
printf("YES");
return 0;
}
![noip2013day1第三題 貨車運輸LCA+并查集[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)