|
|
在處理表達(dá)式過程中需要對括號匹配進(jìn)行檢驗，括號匹配包括三種：“(”和“)”，“[”和“]”，“{”和“}”。例如表達(dá)式中包含括號如下：
( ) [ ( ) ( [ ] ) ] { } 1 2 3 4 5 6 7 8 9 10 11 12 從上例可以看出第1和第2個括號匹配，第3和第10個括號匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。從中可以看到括號嵌套的的情況是比較復(fù)雜的，使用堆棧可以很方便的處理這種括號匹配檢驗，可以遵循以下規(guī)則：
1、 當(dāng)接收第1個左括號，表示新的一組匹配檢查開始；隨后如果連續(xù)接收到左括號，則不斷進(jìn)堆棧。
2、 當(dāng)接受第1個右括號，則和最新進(jìn)棧的左括號進(jìn)行匹配，表示嵌套中1組括號已經(jīng)匹配消除
3、 若到最后，括號不能完全匹配，則說明輸入的表達(dá)式有錯
Input
第一行輸入一個t，表示下面將有t組測試數(shù)據(jù)。接下來的t行的每行輸入一個表達(dá)式，表達(dá)式只考慮英文半角狀態(tài)輸入，無需考慮中文全角輸入
Output
對于每一行的表達(dá)式，檢查括號是否匹配，匹配則輸入ok，不匹配則輸出error
Sample Input
2 (a+b)[4*5+(-6)] [5*8]/{(a+b)-6 Sample Output
ok error
代碼：
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int main()
{
int t,len;
stack<char> mystack;
cin>>t;
while(t--)
{
int ok=0;
char str[100];
cin>>str;
len=strlen(str);
for(int i=0;i<len;i++)
{
switch(str[i])
{
case '(':
case '[':
case '{':
mystack.push(str[i]);
break;
case ')':
if(mystack.top() == '(')
{
mystack.pop();
ok=1;
}
break;
case ']':
if(mystack.top() == '[')
{
mystack.pop();
ok=1;
}
break;
case '}':
if(mystack.top() == '{')
{
mystack.pop();
ok=1;
}
break;
default: break;
}
}
if(ok && mystack.empty())
cout<<"ok"<<endl;
else
cout<<"error"<<endl;
}
return 0;
}
Description
對于任意十進(jìn)制數(shù)轉(zhuǎn)換為k進(jìn)制，包括整數(shù)部分和小數(shù)部分轉(zhuǎn)換。整數(shù)部分采用除k求余法，小數(shù)部分采用乘k取整法例如x=19.125，求2進(jìn)制轉(zhuǎn)換
整數(shù)部分19， 小數(shù)部分0.125 19 / 2 = 9 … 1 0.125 * 2 = 0.25 … 0 9 / 2 = 4 … 1 0.25 * 2 = 0.5 … 0 4 / 2 = 2 … 0 0.5 * 2 = 1 … 1 2 / 2 = 1 … 0 1 / 2 = 0 … 1 所以整數(shù)部分轉(zhuǎn)為 10011，小數(shù)部分轉(zhuǎn)為0.001，合起來為10011.001 請用堆棧實現(xiàn)上述數(shù)制轉(zhuǎn)換
Input
第一行輸入一個t，表示下面將有t組測試數(shù)據(jù)。
接下來的t行的每行包含兩個參數(shù)n（0<n<10000，且最多有8位小數(shù)）和k（1<k<=16），n表示要轉(zhuǎn)換的數(shù)值，n可以帶小數(shù)（也可以不帶！），k表示要轉(zhuǎn)換的數(shù)制，k必須是正整數(shù)。大于10的進(jìn)制數(shù)據(jù)用A\B\C\D\E\F表示
Output
對于每一組測試數(shù)據(jù)，每行輸出轉(zhuǎn)換后的結(jié)果，小數(shù)部分大于8位的，只輸出前8位小數(shù)
Sample Input
2 19.125 2 15.125 16 Sample Output
10011.001 F.2
代碼
#include<iostream> #include<stack>
using namespace std;
int main()
{
stack<int> mystack;
int t,m,k;
double b,a;
cin>>t;
while(t--)
{
int c,x[100],d=0,i=0,count=0;
cin>>b>>k;
m=b;
a=b-m;
while(m)
{
c=m%k;
m=m/k;
mystack.push(c);
}
while(1)
{
d=a*k;
if(d>=k)
break;
a=a*k;
x[i++]=d;
count++;
}
while(!mystack.empty())
{
if(mystack.top()<10)
{
cout<<mystack.top();
mystack.pop();
}
else
{
switch(mystack.top())
{
case 10: cout<<"A"; mystack.pop(); break;
case 11: cout<<"B"; mystack.pop(); break;
case 12: cout<<"C"; mystack.pop(); break;
case 13: cout<<"D"; mystack.pop(); break;
case 14: cout<<"E"; mystack.pop(); break;
case 15: cout<<"F"; mystack.pop(); break;
}
}
}
cout<<".";
for(i=0;i<count;i++)
cout<<x[i];
cout<<endl;
}
return 0;
}
如下： #include<stdio.h>int main()
{
int M,b;
int N[100],c=0;
scanf("%d%d",&b,&M);//輸入進(jìn)制b(2~10),要轉(zhuǎn)化為b進(jìn)制的正整數(shù)M(十進(jìn)制)
while(M)
{
N[c++]=M%b;
M=M/b;
}
for(int i=c-1;i>=0;i--)
printf("%d",N[i]);
printf("\n");
return 0;
}
如下： #include<stdio.h>#include<string.h>
#include<math.h>
int main()
{
char M[100]={0};
int N=0;
gets(M);
int len=strlen(M);
for(int i=0;i<len;i++)
{
N+=(M[i]-'0') * pow(2.0,len-i-1);
}
printf("%d\n",N);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
ElemType *elem; //存儲空間基址
int length; //當(dāng)前的線性表長度
int listsize; //當(dāng)前分配的存儲容量
}SqList;
//初始化線性表
Status InitList_Sq(SqList *L) //用線性表的指針操作
{
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW);
(*L).length=0;
(*L).listsize=LIST_INIT_SIZE;
return OK;
}
int ListLength(SqList L)
{
return L.length;
}
Status GetElem(SqList L,int i,ElemType *e)
{
if(i<1 || i>L.length)
exit(ERROR);
*e=*(L.elem+i-1);
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase,*p,*q;
if(i<1 || i>(*L).length+1)
return ERROR;
if((*L).length >= (*L).listsize)
{
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*L).elem=newbase;
(*L).listsize +=LISTINCREMENT;
}
q=(*L).elem+i-1; //插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++(*L).length;
return OK;
}
int LocateElem(SqList L,ElemType e)
{
int i;
for(i=0;i<L.length;i++)
{
if(*(L.elem+i) == e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
Status Visit(ElemType *c)
{
printf("%d ",*c);
return OK;
}
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
Visit(L.elem+i);
printf("\n");
return OK;
}
void Union(SqList *La,SqList Lb) //求La和Lb中元素的集合La，即把Lb中與La不相同的元素取出來插入La中
{
ElemType La_len,Lb_len;
int i,e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}//Union
int main()
{
SqList La,Lb;
int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
InitList_Sq(&La);
for(j=1;j<=4;j++)
ListInsert(&La,j,a[j-1]);
printf("print La: \n");
ListTraverse(La);
InitList_Sq(&Lb);
for(j=1;j<=7;j++)
ListInsert(&Lb,j,b[j-1]);
printf("print Lb: \n");
ListTraverse(Lb);
Union(&La,Lb);
printf("print La: \n");
ListTraverse(La);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
ElemType *elem; //存儲空間基址
int length; //當(dāng)前的線性表長度
int listsize; //當(dāng)前分配的存儲容量
}SqList;
//初始化線性表
Status InitList_Sq(SqList *L) //用線性表的指針操作
{
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW);
(*L).length=0;
(*L).listsize=LIST_INIT_SIZE;
return OK;
}
int ListLength(SqList L)
{
return L.length;
}
Status GetElem(SqList L,int i,ElemType *e)
{
if(i<1 || i>L.length)
exit(ERROR);
*e=*(L.elem+i-1);
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase,*p,*q;
if(i<1 || i>(*L).length+1)
return ERROR;
if((*L).length >= (*L).listsize)
{
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*L).elem=newbase;
(*L).listsize +=LISTINCREMENT;
}
q=(*L).elem+i-1; //插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++(*L).length;
return OK;
}
Status Visit(ElemType *c)
{
printf("%d ",*c);
return OK;
}
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
Visit(L.elem+i);
printf("\n");
return OK;
}
void MergeList(SqList La,SqList Lb,SqList *Lc) //歸并線性表La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素安置遞減排列
{
int i=1,j=1,k=0;
int La_len,Lb_len;
ElemType ai,bj;
InitList_Sq(Lc);
La_len=ListLength(La);
Lb_len=ListLength(Lb);
while((i<=La_len) && (j<=Lb_len)) //如果表La和表Lb都非空
{
GetElem(La,i,&ai);
GetElem(Lb,j,&bj);
if(ai<=bj)
{
ListInsert(Lc,++k,ai); ++i;
}
else
{
ListInsert(Lc,++k,bj); ++j;
}
}
while(i<=La_len) //如果只有La非空
{
GetElem(La,i++,&ai);
ListInsert(Lc,++k,ai);
}
while(j<=Lb_len)
{
GetElem(Lb,j++,&bj);
ListInsert(Lc,++k,bj);
}
}
int main()
{
SqList La,Lb,Lc;
int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
InitList_Sq(&La);
for(j=1;j<=4;j++)
ListInsert(&La,j,a[j-1]);
printf("print La: \n");
ListTraverse(La);
InitList_Sq(&Lb);
for(j=1;j<=7;j++)
ListInsert(&Lb,j,b[j-1]);
printf("print Lb: \n");
ListTraverse(Lb);
MergeList(La,Lb,&Lc);
printf("print Lc: \n");
ListTraverse(Lc);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
ElemType *elem; //存儲空間基址
int length; //當(dāng)前的線性表長度
int listsize; //當(dāng)前分配的存儲容量
}SqList;
//初始化線性表
Status InitList_Sq(SqList *L) //用線性表的指針操作
{
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW);
(*L).length=0;
(*L).listsize=LIST_INIT_SIZE;
return OK;
}
int ListLength(SqList L)
{
return L.length;
}
Status ListEmpty(SqList L)
{
if(L.length == 0)
return OK;
else
return ERROR;
}
Status ClearList(SqList *L)
{
(*L).length=0;
return OK;
}
Status DestroyList(SqList *L)
{
free((*L).elem);
(*L).elem=NULL;
(*L).length=0;
(*L).listsize=0;
return OK;
}
Status GetElem(SqList L,int i,ElemType *e)
{
if(i<1 || i>L.length)
exit(ERROR);
*e=*(L.elem+i-1);
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase,*p,*q;
if(i<1 || i>(*L).length+1)
return ERROR;
if((*L).length >= (*L).listsize)
{
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*L).elem=newbase;
(*L).listsize +=LISTINCREMENT;
}
q=(*L).elem+i-1; //插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++(*L).length;
return OK;
}
Status Visit(ElemType *c)
{
printf("%d ",*c);
return OK;
}
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
Visit(L.elem+i);
printf("\n");
return OK;
}
int LocateElem(SqList L,ElemType e)
{
int i;
for(i=0;i<L.length;i++)
{
if(*(L.elem+i) == e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if(L->length == 0)
return ERROR;
if(i<1 || i>=L->length)
return ERROR;
*e=*(L->elem+i-1);
if(i<L->length)
{
for(k=i;k<L->length;k++)
*(L->elem+k-1)=*(L->elem+k);
}
L->length--;
return OK;
}
int main()
{
int i,e;
SqList mylist;
int m = InitList_Sq(&mylist);
if(m)
{
printf("線性表創(chuàng)建成功!\n");
printf("當(dāng)前表長: %d \n",ListLength(mylist));
}
else
printf("線性表創(chuàng)建失敗.");
for(i=1;i<=10;i++)
ListInsert(&mylist,i,i);
ListTraverse(mylist);
printf("當(dāng)前表長：%d \n",ListLength(mylist));
GetElem(mylist,5,&e);
printf("第5個元素為：%d\n",e);
ListDelete(&mylist,4,&e);
printf("刪除第4個元素后：");
ListTraverse(mylist);
printf("當(dāng)前表長：%d \n",ListLength(mylist));
i=ClearList(&mylist);
printf("清空線性表后：表長為 %d\n",mylist.length);
i=ListEmpty(mylist);
printf("表是否為空：%d (1:空 0：否)\n",i);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
typedef struct node *link;
struct node
{ int v; link next; };
link NEW(int v, link next)
{
link x = (link)malloc(sizeof(node));
x->v = v; x->next = next;
return x;
}
int main()
{
int i,j;
link adj[7];
for(i=0;i<7;i++)
adj[i] = NULL;
while (scanf("%d%d",&i,&j) == 2)
{
adj[j] = NEW(i,adj[j]);
adj[i] = NEW(j,adj[i]);
}
return 0;
}
代碼如下： #include<stdio.h> #include<stdlib.h> int main() { int i,j,adj[7][7]; for(i=0;i<7;i++) for(j=0;j<7;j++) adj[i][j] = 0; for(i=0;i<7;i++) adj[i][i] = 1; while(scanf("%d%d",&i,&j) == 2) { adj[i][j] = 1; adj[j][i] = 1; } for(i=0;i<7;i++) { for(j=0;j<7;j++) { printf("%d ",adj[i][j]); } printf("\n"); } return 0; } 結(jié)果截圖： 
編寫一程序，用0或1填充一個二維數(shù)組，如果i 和j 的最大公因子為1，則設(shè)a[i][j]為1；否則設(shè)為0。 代碼如下： #include<stdio.h>
#define N 10
int Maxcom(int a, int b)
{
while(a!=b)
{
if(a>b)
a=a-b;
else if(b>a)
b=b-a;
}
return a;
}
int main()
{
int a[N][N];
int i,j,max;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
if(i==1 && j==1)
a[i][j]=1;
else if( i>0 && j>0)
{
max = Maxcom(i,j);
if(max == 1)
a[i][j]=1;
else
a[i][j]=0;
}
else
a[i][j]=0;
}
}
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
printf("%d ",a[i][j]);
printf("\n");
}
printf("\n");
return 0;
}
|