ĐỀ THI MÔN Cấu Trúc Dữ Liệu và Giải Thuật học viện công nghệ bưu chính viễn thông (7)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (19.15 KB, 4 trang )
M¹nh D¬ng Biªn So¹n
Bé M«n CÊu Tróc D÷ LiÖu
Gi¶i ThuËt 2012
§ª Sè 7
Trong Bé §Ò ¤n TËp
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
#include<string.h>
#include<stdio.h>
#include <math.h>
ifstream tepvao("C:/cau truc du lieu/dethi/hauto.in.txt");
ofstream tepra("C:/cau truc du lieu/dethi/ketqua7.out.txt");
/*
Tinh ket qua hau to
*/
struct node
{
int conyeu;
struct node *next;
};
typedef struct node *stacknode;
typedef struct
{
stacknode top;
}Stack;
Stack dau;
void KhoiTaoStack(Stack *S)
{
S->top=NULL;
return ;
}
int StackRong(Stack S)
{
return (S.top==NULL);
}
void PUSHStack(Stack *S,int x)
{
stacknode p;
p=(stacknode)malloc(sizeof(struct node));
p->conyeu=x;
p->next=S->top;
S->top=p;
return ;
}
int POPStack(Stack *S)
{
stacknode p;
if(StackRong(*S))
{
return -1;
}else
{
p=S->top;
S->top=S->top->next;
return p->conyeu;
}
}
int xemdinh(Stack *S)
{ stacknode p;
if(StackRong(*S)){return -1;}
p=S->top;
return p->conyeu;
}
int ket(char S)
{
int k=int (S);
int h=k-int ('0');
return h;
}
int chuyen(char S[])
{int j=0,k=0;
for(int i=strlen(S)-1;i>=0;i )
{k+=ket(S[i])*pow(10,j);j++;}
return k;
}
void NhapDL(char S[][600],int &n)
{
tepvao>>n;
for(int i=0;i<=n;i++)
tepvao.getline(S[i],600,'\n');
}
void ketqua(char S[])
{
int i=0;
KhoiTaoStack(&dau);
while(S[i]!='\0')
{
if(S[i]>='0'&&S[i]<='9')
{
char SS[600];
int k=0;
while(S[i]>='0'&&S[i]<='9')
{
SS[k]=S[i];
k++;
i++;
}
SS[k]='\0';
PUSHStack(&dau,chuyen(SS));
}
else if(S[i]=='+')
{
int a=POPStack(&dau);
int b=POPStack(&dau);
PUSHStack(&dau,a+b);
}
else if(S[i]=='-')
{
int a=POPStack(&dau);
int b=POPStack(&dau);
PUSHStack(&dau,b-a);
}
else if(S[i]=='*')
{
PUSHStack(&dau,POPStack(&dau)*POPStack(&dau));
}
else if(S[i]=='/')
{
int a=POPStack(&dau);
int b=POPStack(&dau);
PUSHStack(&dau,b/a);
}
i++;if(S[i]==' ')i++;
}
int k=POPStack(&dau);
if(StackRong(dau))tepra<<k<<endl;else
{while(StackRong(dau)!=1)
{
k=POPStack(&dau);
}
tepra<<k<<endl;}
}
main()
{
char S[1000][600];
int n;
NhapDL(S,n);
tepra<<n<<endl;
for(int i=1;i<=n;i++)
ketqua(S[i]);
}
