Embedded Files
Đề bài: Chuyển trung tố sang hậu tố
input.txt
1-2^3^3-(4+5*6)*7
main.c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node_data
{
char a;
struct node_data *next;
} node;
typedef struct queue_element
{
struct node_data *front;
struct node_data *back;
} queue;
node* khoitao_stack()
{
return(NULL);
}
int rong_stack(node*top)
{
return(top==NULL);
}
int push(node**top,node**tmp)
{
(*tmp)->next=NULL;
if(*top==NULL)
{
*top=*tmp;
}
else
{
(*tmp)->next=*top;
*top=*tmp;
}
return(0);
}
char pop(node **top)
{
char tmp=0;
node*x;
if(rong_stack(*top))
{
printf("Stack rong.\n");
return(0);
}
else
{
tmp=(*top)->a;
x=*top;
*top=(*top)->next;
free(x);
}
return(tmp);
}
char stacktop(node *top)
{
return(top->a);
}
int khoitao_queue(queue *q)
{
q->back=q->front=NULL;
return(0);
}
int rong_queue(queue q)
{
return(q.front==NULL&&q.back==NULL);
}
int enqueue(queue *q,node *a)
{
if(q->front==NULL)
{
q->front=q->back=a;
}
else
{
q->back->next=a;
q->back=a;
}
return(0);
}
int dequeue(queue *q)
{
if(q->front==NULL)
return 4;
node*tmp;
tmp=q->front;
q->front=q->front->next;
if(q->front==NULL)
q->back=NULL;
free(tmp);
return 0;
}
int show(queue q)
{
node *tmp;
int x=1;
tmp=q.front;
while(tmp!=NULL)
{
printf("%d: %c--\n",x,tmp->a);
tmp=tmp->next;
x++;
}
return(0);
}
int toan_tu(char c)
{
if(c>='0'&&c<='9') return 0;
if(c=='(') return 1;
if(c=='+') return 2;
if(c=='-') return 2;
if(c=='*') return 2;
if(c=='/') return 2;
if(c=='^') return 2;
if(c=='%') return 2;
if(c==')') return 3;
return -1;
}
int kiem_tra(node *top,char c)
{
int x1,x2;
if(c=='^') x2= 3;
if(c=='%') x2= 2;
if(c=='/') x2= 2;
if(c=='*') x2= 2;
if(c=='-') x2= 1;
if(c=='+') x2= 1;
if(top==NULL)x1=0;
else
{
if(c=='^'&&top->a=='^') return 1;
if(top->a=='^') x1= 3;
if(top->a=='%') x1= 2;
if(top->a=='/') x1= 2;
if(top->a=='*') x1= 2;
if(top->a=='+') x1= 1;
if(top->a=='-') x1= 1;
}
switch(x1-x2)
{
case 0: return 0;
case 1: case 2: return -1;
case -1: case -2: return 1;
}
return 0;
}
FILE *in,*out;
int main()
{
int dk=0;
char c;
node* tmp,*tmp2;
node* stack1;
queue queue1;
khoitao_queue(&queue1);
stack1= khoitao_stack();
if((in=fopen("input.txt","r+"))==NULL)
{
printf("Mo file loi.\n");
}
out=fopen("output.txt","w+");
/* if((tmp=(node*)malloc(sizeof(node)))==NULL)
{
printf("Khoi tao malloc that bai.\n");
exit ;
}
tmp->next=NULL;
tmp->a='(';
push(&stack1,&tmp); */
while((c=getc(in))!=EOF)
{
if((tmp=(node*)malloc(sizeof(node)))==NULL)
{
printf("Khoi tao malloc that bai.\n");
}
tmp->next=NULL;
tmp->a=c;
switch(toan_tu(c))
{
case 0: enqueue(&queue1,tmp); break;
case 1: push(&stack1,&tmp); break;
case 2:
{
while(kiem_tra(stack1,c)!=1)
{
if(stacktop(stack1)=='(') break; // pop(&stack1);
if((tmp2=(node*)malloc(sizeof(node)))==NULL)
{
printf("Khoi tao malloc that bai.\n");
}
tmp2->next=NULL;
tmp2->a=pop(&stack1);
enqueue(&queue1,tmp2);
if(rong_stack(stack1)) break;
}
push(&stack1,&tmp);
break;
}
case 3:
{
while(stacktop(stack1)!='(')
{
if((tmp2=(node*)malloc(sizeof(node)))==NULL)
{
printf("Khoi tao malloc that bai.\n");
}
tmp2->next=NULL;
tmp2->a=pop(&stack1);
enqueue(&queue1,tmp2);
if(rong_stack(stack1)) break;
}
pop(&stack1);
break;
}
default: dk=1;
}
if(dk) break;
}
while(rong_stack(stack1)!=1)
{
if((tmp2=(node*)malloc(sizeof(node)))==NULL)
{
printf("Khoi tao malloc that bai.\n");
}
tmp2->next=NULL;
tmp2->a=pop(&stack1);
enqueue(&queue1,tmp2);
}
while(!rong_queue(queue1))
{
fprintf(out,"%c ",queue1.front->a);
dequeue(&queue1);
}
return 0;
}
Page updated
Google Sites
Report abuse