棧 手算到機算 入門 字尾表達式 逆波蘭式 進制轉換

棧 手算到機算 入門   字尾表達式  逆波蘭式

總目錄：從手算到機算 算法競賽入門篇

棧：先進後出

1.入門：洛谷 P1427 小魚的數字遊戲

AC代碼如下：

#include <bits/stdc++.h>
int st[110],top;//棧
int main(){
	int x;
	while(scanf("%d",&x)){
		if(!x)break;
		st[++top]=x;//入棧
	}
	while(top)printf("%d ",st[top--]);//出棧
	return 0;
}           

2.字尾表達式  逆波蘭式

洛谷 P1449 字尾表達式

該題題意不全，還需補充一些條件如下：

隻包含+-*/四則運算。

給出的資料，全是正整數。

所有運算，都在int範疇。

AC代碼如下：

#include <bits/stdc++.h>
#define maxn 1010
char s[maxn];
int st[maxn],top;
void cmd(char c){
	int a,b,d;
	b=st[top--],a=st[top--];
	if(c=='+')d=a+b,st[++top]=d;
	else if(c=='-')d=a-b,st[++top]=d;
	else if(c=='*')d=a*b,st[++top]=d;
	else if(c=='/')d=a/b,st[++top]=d;
}
int main(){
	int i,len,x=0;
	scanf("%s",s);
	len=strlen(s);
	for(i=0;i<len;i++)
		if(s[i]=='.'||s[i]=='@'){
			if('0'<=s[i-1]&&s[i-1]<='9'){
				st[++top]=x;
				x=0;
			}
		}else if('0'<=s[i]&&s[i]<='9'){
			x*=10;
			x+=s[i]-'0';
		}else{//字元
			x=0;
			cmd(s[i]);
		}
	printf("%d\n",st[top]);
	return 0;
}           

3.進制轉換

洛谷 P1143 進制轉換

AC代碼如下：

#include <bits/stdc++.h>
int n,m,st[40],top;
char s[40];
int c2i(char c){
	if('0'<=c&&c<='9')return c-'0';
	if(c=='A')return 10;
	if(c=='B')return 11;
	if(c=='C')return 12;
	if(c=='D')return 13;
	if(c=='E')return 14;
	if(c=='F')return 15;
}
int main(){
	int i,len,x=0;
	scanf("%d%s%d",&n,s,&m);
	len=strlen(s);
	for(i=0;i<len;i++){
		x*=n;
		x+=c2i(s[i]);
	}
	while(x){
		st[++top]=x%m;
		x/=m;
	}
	while(top){
		x=st[top--];
		if(x<=9)printf("%d",x);
		else printf("%c",x-10+'A');
	}
	return 0;
}