• 博客访问： 299448
• 博文数量： 83
• 博客积分： 3193
• 博客等级： 中校
• 技术积分： 1679
• 用 户 组： 普通用户
• 注册时间： 2006-04-03 12:04

2013年（2）

2012年（6）

2011年（72）

2010年（2）

2009年（1）

2011-07-05 12:55:13

1.填图游戏：

#include
#include

#define M    20
#define N    20

static int graph[M][N]={
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{1,1,1,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,0,1},
{1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1},
{1,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,0,0,1},
{1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1},
{1,1,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,0,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
void showgraph(int graph[][N])
{
int i,j;
for(i=0;i    {
for(j=0;j        {
if(graph[i][j]==1 || graph[i][j] == 2)
printf("*");
else
printf(" ");
}
printf("\n");
}
}
int NotFilling(int m, int n)
{
if(graph[m][n] == 0)
return 0;
else
return -1;
}

int PointOnEdge(int m, int n)
{
if(graph[m][n] == 1)
return 0;
else
return -1;
}

void pre_draw(int m,int n)
{
if((n-1 > 0) && (PointOnEdge(m,n-1)==-1) && (NotFilling(m,n-1) == 0))
{
//    printf("m=%d,n-1=%d\n",m,n-1);
graph[m][n-1]=2;
pre_draw(m,n-1);
}
if((m+1)<19 && (PointOnEdge(m+1,n) == -1) && (NotFilling(m+1,n) == 0))
{
//    printf("m+1=%d,n=%d\n",m+1,n);
graph[m+1][n] =2;
pre_draw(m+1,n);
}
if((n+1)< 19 && (PointOnEdge(m,n+1) == -1) && (NotFilling(m,n+1) == 0))
{
//    printf("m=%d,n+1=%d\n",m,n+1);
graph[m][n+1] =2;
pre_draw(m,n+1);
}
if((m-1) > 0 && (PointOnEdge(m-1,n) == -1) && (NotFilling(m-1,n) == 0))
{
//    printf("m-1=%d,n=%d\n",m-1,n);
graph[m-1][n] =2;
pre_draw(m-1,n);
}
}
void main(void)
{
showgraph(graph);
int m,n;
do{
scanf("%d %d", &m, &n);
if(PointOnEdge(m,n) == 0)
printf("The point is on the edge, please try again!\n");

else
break;
}while(1);
graph[m][n]=1;
pre_draw(m,n);
showgraph(graph);
}

2.球钟算法：

::::::::::::::
queue.h
::::::::::::::
#include

#define QUEUE_TYPE    int

void create_queue(size_t size);
void destroy_queue(void );
void insert(QUEUE_TYPE    value);
void delete(void);

QUEUE_TYPE first(void);
int is_empty(void);
int is_full(void);
void show_queue(void);
void show_myqueue(void);
void record_queue(int [], int);

::::::::::::::
g_stack.h
::::::::::::::
#include

#define GENERIC_STACK( STACK_TYPE, SUFFIX, STACK_SIZE)    \
static STACK_TYPE    stack##SUFFIX[STACK_SIZE];\
static int        top_element##SUFFIX = -1;\
\
int                        \
is_empty##SUFFIX(void)                \
{                        \
}                        \
\
int                        \
is_full##SUFFIX(void)                \
{                        \
}                        \
\
void                        \
push##SUFFIX(STACK_TYPE value)            \
{                        \
assert(!is_full##SUFFIX());            \
top_element##SUFFIX += 1;            \
stack##SUFFIX[top_element##SUFFIX] = value;     \
}                        \
\
void                        \
pop##SUFFIX(void)                \
{                        \
assert(!is_empty##SUFFIX());            \
top_element##SUFFIX -= 1;            \
}                        \
\
STACK_TYPE top##SUFFIX(void)            \
{                        \
assert(!is_empty##SUFFIX());            \
return stack##SUFFIX[top_element##SUFFIX];    \
}

::::::::::::::
main.c
::::::::::::::
#include "g_stack.h"
#include "queue.h"
#include

GENERIC_STACK(int,_int_a,4)
GENERIC_STACK(int,_int_b,11)
GENERIC_STACK(int,_int_c,11)

#define QUEUE_SIZE    27

void one_cycle(void)
{
int queue_pop;
int queue_push;
int i;
queue_pop = first();
delete();

if(!is_full_int_a())
{

push_int_a(queue_pop);
}
else
{
for(i=0;i<4;i++)
{
insert(top_int_a());
pop_int_a();
}

if(!is_full_int_b())
push_int_b(queue_pop);
else
{
for(i=0;i<11;i++)
{
insert(top_int_b());
pop_int_b();
}
if(!is_full_int_c())
push_int_c(queue_pop);
else
{
for(i=0;i<11;i++)
{
insert(top_int_c());
pop_int_c();
}
insert(queue_pop);
}
}

}

}

void list_array(int queue[])
{
int i = 0;
while(queue[i]!=-1 && i < QUEUE_SIZE)
{
printf("%d ",queue[i]);
i++;
}
printf("\n");
}

int compare_queue(int a[], int b[])
{
int i;
for(i=0;i    {
if(a[i] != b[i])
return 0;
}
return 1;
}

void time_counting(int *min, int *hour, int *day)
{
if( *min != 59)    // min
{
*min += 1;

}
else        //hour
{
*min = 0;
if( *hour != 23 )
*hour += 1;
else        //day
{
*hour = 0;
*day += 1;
}
}
}

main(void)
{
int count = 0;
int start_queue[QUEUE_SIZE];
int queue[QUEUE_SIZE];
int i;

int min = 0 ;
int hour = 0;
int day = 0;

create_queue(QUEUE_SIZE);
for(i=0;i        insert(i+1);
record_queue(start_queue, QUEUE_SIZE);
record_queue(queue, QUEUE_SIZE);
list_array(queue);
printf("Compare result : %d\n",compare_queue(start_queue,queue));
while(1)
{
i = 0;
one_cycle();
record_queue(queue, QUEUE_SIZE);
count++;
time_counting(&min, &hour, &day);

/*
if(count > 33110)
{
printf("Count = %d\n",count);
list_array(queue);
}
*/

if(compare_queue(start_queue,queue)==1)
break;
//printf("Compare result : %d\n",compare_queue(start_queue,queue));
//getchar();
}
printf("Count = %d mintinues\n",count);
printf("%d days:%d hours:%d mins\n", day, hour, min);
}
::::::::::::::
queue.c
::::::::::::::
#include "queue.h"
#include

struct node_st{
int id;
int value;
struct node_st *next;
};

static struct node_st *root = NULL;

void show_myqueue(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
printf("%d ",current->value);
current = current->next;
if(current->id == start)
break;
}
printf("\n");
}

void record_queue(int queue[],int queue_size)
{
int i=0;
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
queue[i] = current->value;
i++;
current = current->next;
if(current->id == start)
break;
}
if(i        queue[i]=-1;
}

void show_queue(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
printf("queue id:%d value:%d\n",current->id,current->value);
current = current->next;
if(current->id == start)
break;
}
}
void create_queue(size_t size)
{
int i;
struct node_st *current= NULL;
struct node_st *new;
for(i=0;i    {
new = malloc(sizeof(struct node_st));
new->id = i;
new->value = -1;
new->next = NULL;
if(root == NULL)
current = root = new;
else
{
current->next = new;
current = current->next;
new = NULL;
}
}
if(current->next == NULL)
current->next = root;
}

void insert(QUEUE_TYPE    value)
{
struct node_st *current = root;
int ret=0;
while(current->value != -1)
{
if((ret=is_full()) == 1)
break;
current = current->next;
}
if(ret == 0)
current->value = value;
}
/* check if the queue is empty:
if return 0, it shows that the queue is not empty;
if return 1, it shows that the queue is empty
*/
int is_empty(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value == -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}
/* check if the queue  is full:
if return 0, it shows that the queue is not full;
else if return 1, it shows that the queue is full
*/

int is_full(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}

void delete(void)
{
if(!is_empty())
{
root->value = -1;
root= root->next;
}
}

QUEUE_TYPE first(void)
{
return root->value;
}

void destroy_queue(void)
{
int start, end;
struct node_st *current = root;
struct node_st *previous = root;
start = current->id;
do{
end =current->id;
current = current->next;
}while(current->id != start);

while(current->id != end)
{
previous = current;
current = current->next;
free(previous);
previous = NULL;
}
free(current);
current = NULL;
}

3.Dijkstra算法：

::::::::::::::
dijkstra.c
::::::::::::::
#include
#include

#define SIZE 7

typedef struct NODE_ST{
int dv;
int pv;
int known;
}node_data;

void sort_route(int temp[],node_data V[])
{
int i=0;
int j,k;
int tmp;
while(temp[i] != -1)
{
//        printf("temp[%d]=%d\n",i,temp[i]);
i++;
}
for(j=0;j    {
for(k=0;k        {
if(V[temp[j]].dv < V[temp[k]].dv)
{
tmp = temp[j];
temp[j]=temp[k];
temp[k] = tmp;
}

}
}

}

void display_route(node_data V[], int n)
{
int i;
printf("v     Known     dv      pv\n");
for(i=1;i<=n;i++)
printf("V%d:      %d     %d    V%d\n", i, V[i].known, V[i].dv, V[i].pv);
}

void clear_route(int route[])
{
route[0]=-1;
}
void update_route(int node[][SIZE], node_data V[], int volume, int route[])
{
int i,j;
i = 0;
while(route[i] != -1)
i++;
//    printf("\tstart updating on V%d:\n",volume);
V[volume].known = 1;
for(j=1;j<8;j++)
{
if(node[volume-1][j-1]>0)
{
if(V[j].known == 1)
continue;
if((V[j].dv != 0) && (V[j].dv < (V[volume].dv + node[volume-1][j-1])))
continue;

// update the shorter route
V[j].pv = volume;
V[j].dv = V[volume].dv + node[volume-1][j-1];
route[i]=j;
//            printf("\tUpdate V%d in route \n",j);
i++;
}
}
route[i]=-1;
//    display_route(V, 7);
}

int check_known(node_data V[], int size)
{
int i;
for(i=1;i<=size;i++)
{
if(V[i].known == 0)
return 0;
}
return 1;
}
void dijkcheck(int node[][SIZE],node_data V[], int volume)
{
int i;
int route[SIZE];
int new_route[SIZE];
route[0]=-1;
new_route[0]=-1;
//    printf("Enter V%d node:\n",volume);
update_route(node, V, volume, route);
while(check_known(V, SIZE) == 0)
{
//getchar();
sort_route(route,V);
for(i=0;route[i] != -1;i++)
update_route(node, V, route[i], new_route);
for(i=0;new_route[i] != -1;i++)
route[i]=new_route[i];
route[i]=-1;
new_route[0]=-1;
}
}

::::::::::::::
main.c
::::::::::::::
#include "dijkstra.c"

int main(void)
{
int i,j;
int start = 3;
int node[SIZE][SIZE]={ // V1 V2 V3 V4 V5  V6  V7
/*V1*/        { 0, 2, -1, 1,-1, -1, -1},
/*V2*/        {-1, 0, -1, 3,10, -1, -1},
/*V3*/        { 4,-1,  0,-1,-1,  5, -1},
/*V4*/        {-1,-1,  2, 0, 2,  8,  4},
/*V5*/        {-1,-1, -1,-1, 0, -1,  6},
/*V6*/        {-1,-1, -1,-1,-1,  0, -1},
/*V7*/        {-1,-1, -1,-1,-1,  1,  0}};

node_data V[8];
for(i=1;i<8;i++)
{
V[i].dv=0;
V[i].pv=999;
V[i].known=0;
}
dijkcheck(node, V, start);
printf("Final route starting from V%d:\n",start);
display_route(V,7);

}

4.拓扑排序：
::::::::::::::
topologic.h
::::::::::::::
#ifndef _TOPOLOG_HS_
#define _TOPOLOG_HS_

#endif

::::::::::::::
topologic.c
::::::::::::::
#include "topologic.h"
#include
#include

static int count = 1;

{
int i;
lkqnode *current = NULL;
for(i=0;i    {
current = L[i]->rear->next;
continue;
while(current != NULL)
{
if(current->data == volume)
return -1;
current = current->next;
}
}
return 0;
}

void sort(linkqueue *L[], int arr[], int n)
{
int i;
int loop = 1;
for(i=0;i    {
if(L[i]->id != -1)
continue;
{
L[i]->id = count;
arr[count-1] = i;
count++;
loop = 0;
break;
}
}
if(count <= n && loop == 0 )
sort(L,arr,n);
}

::::::::::::::
::::::::::::::
#include
#include

{
lkqnode *new;
L=malloc(sizeof(*L));
if(L == NULL)
return NULL;
L->id = -1;
L->front = L->rear = malloc(sizeof(struct linkqueue));;
L->rear->next = NULL;
return L;

}

{
lkqnode *new;
lkqnode *current ;
new = malloc(sizeof(*new));
if(new == NULL)
return -1;
new->data = x;
new->next = NULL;
L->front = new;
if(L->rear->next == NULL)
{
L->rear->next = new;
return 0;
}
current = L->rear->next;
while(current->next != NULL)
current = current->next;
current->next = new;
//    printf("%d \n",L->rear->data);
}

{
if(L->front == NULL)
return -1;
lkqnode *p = L->rear;
lkqnode *q = p->next;

*x = q->data;
p->next = q->next;
free(q);
return 0;
}

{
return L->rear->next == NULL;

}

{
//    printf("display\n");
lkqnode *current = L->rear->next;
while(current != NULL)
{
printf("%d ",current->data);
current = current->next;
}
}

{
return;
lkqnode *q = L->rear->next;
lkqnode *p;
while(q != NULL)
{
p = q;
q = q->next;
free(p);
}
L->rear->next = NULL;
}
::::::::::::::
::::::::::::::

typedef int datatype;
{
datatype data;
}lkqnode;
typedef struct
{
int id;
lkqnode *front;
lkqnode *rear;

#endif
::::::::::::::
main.c
::::::::::::::
#include "topologic.h"
#include

#define C1 0
#define C2 1
#define C3 2
#define C4 3
#define C5 4
#define C6 5
#define C7 6
#define C8 7
#define C9 8
#define C10 9
#define C11 10
#define C12 11
#define C13 12

main(void)
{
int i;
int arr[12]={0};

sort(L,arr,12);
for(i=0;i<12;i++)
printf("C%d ", arr[i]+1 );
printf("\n");
}

5.计算器

::::::::::::::
main.c
::::::::::::::
#include
#include
#include "g_stack.h"

GENERIC_STACK(int,_int,30)
GENERIC_STACK(char,_char,30)

#define MAXSIZE    100

void getstring(char *str)
{
int i;
fgets(str, MAXSIZE, stdin);
}

int converse(char *str)
{
int i;
int count=0;
int num=0;
int mul=1;
while(str[count]!='\0')
count++;
for(i=count-1;i>=0;i--)
{
num += mul*(str[i]-'0');
mul *= 10;
}
return num;
}

int compare_op(char a,char b)
{
int flag_a;
int flag_b;

if(a == '+' || a == '-')
flag_a = 1;
else if(a == '*' || a == '/')
flag_a = 2;
else if(a == '^')
flag_a =3;
else if(a == '#' || a =='(')
flag_a = 0;

if(b == '+' || b == '-')
flag_b = 1;
else if(b == '*' || b == '/')
flag_b = 2;
else if(b == '^')
flag_b =3;
else if(b == '#' || b =='(')
flag_b = 0;

return flag_a - flag_b;
}
int power(int a, int n)
{
int i;
int value = 1;
for(i=0;i        value *= a;
return value;
}

int result(int a, int b, char op)
{
switch(op){
case '+':
return a+b;
break;
case '-':
return a-b;
break;
case '*':
return a*b;
break;
case '/':
return a/b;
break;
case '^':
return power(a,b);
break;
default:
break;
}
}
int native_oper(void)
{
int a,b,c;
char current_op;
while(top_char() != '#' && top_char() != '(')
{
current_op = top_char();
pop_char();

b = top_int();
pop_int();
a = top_int();
pop_int();

c = result(a,b,current_op);
push_int(c);

}
if(top_char() == '(')
pop_char();
return 0;
}
/*
void parentheses_oper(void)
{
int a,b,c;
char current_op;
while(top_char() != '(')
{
current_op = top_char();
pop_char();

b = top_int();
pop_int();
a = top_int();
pop_int();

c = result(a,b,current_op);
push_int(c);
}
}
*/
int operation(char *str)
{
int i;
char buffer[MAXSIZE];
int b_count;
int num=0;
char top_op;
char current_op;
int a;
int b;
int c;
push_char('#');
for(i=0; str[i] != '\n'; i++)
{
if(str[i]=='(')
{
push_char(str[i]);
continue;
}
if(isdigit(str[i]))
{
b_count=0;
while(isdigit(str[i]))
{
buffer[b_count]=str[i];
b_count++;
i++;
}
buffer[b_count] = '\0';
num = converse(buffer);
push_int(num);
//        printf("%d ",num);
i--;
continue;
}

if(str[i]==')')
{
if(native_oper()==0)
continue;
else
return -1;
}

top_op = top_char();
current_op = str[i];
if(compare_op(current_op,top_op) > 0)
{
push_char(current_op);
}
else if((compare_op(current_op, top_op) < 0)||(compare_op(current_op, top_op) == 0))
{
i--;
pop_char();
b = top_int();
pop_int();
a = top_int();
pop_int();

c = result(a,b,top_op);
push_int(c);

}
//        printf("%c ",top_char());

}
if(native_oper()==0)
else
return -1;
}

int main(void)
{
char str[MAXSIZE];
int i;
int result;

getstring(str);
result = operation(str);
if(result != -1)
printf("Th final result is %d\n",result);

//    printf("%d\n",converse("1234"));

}

::::::::::::::
queue.c
::::::::::::::
#include "queue.h"
#include

struct node_st{
int id;
int value;
struct node_st *next;
};

static struct node_st *root = NULL;

void show_queue(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
printf("queue id:%d value:%d\n",current->id,current->value);
current = current->next;
if(current->id == start)
break;
}
}
void create_queue(size_t size)
{
int i;
struct node_st *current= NULL;
struct node_st *new;
for(i=0;i    {
new = malloc(sizeof(struct node_st));
new->id = i;
new->value = -1;
new->next = NULL;
if(root == NULL)
current = root = new;
else
{
current->next = new;
current = current->next;
new = NULL;
}
}
if(current->next == NULL)
current->next = root;
}

void insert(QUEUE_TYPE    value)
{
struct node_st *current = root;
int ret=0;
while(current->value != -1)
{
if((ret=is_full()) == 1)
break;
current = current->next;
}
if(ret == 0)
current->value = value;
}
/* check if the queue is empty:
if return 0, it shows that the queue is not empty;
if return 1, it shows that the queue is empty
*/
int is_empty(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value == -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}
/* check if the queue  is full:
if return 0, it shows that the queue is not full;
else if return 1, it shows that the queue is full
*/

int is_full(void)
{
struct node_st *current = root;
int start = current->id;
while(current->value != -1)
{
current = current->next;
if(current->id == start)
return 1;
}
return 0;
}

void delete(void)
{
if(!is_empty())
{
root->value = -1;
root= root->next;
}
}

QUEUE_TYPE first(void)
{
return root->value;
}

void destroy_queue(void)
{
int start, end;
struct node_st *current = root;
struct node_st *previous = root;
start = current->id;
do{
end =current->id;
current = current->next;
}while(current->id != start);

while(current->id != end)
{
previous = current;
current = current->next;
free(previous);
previous = NULL;
}
free(current);
current = NULL;
}
::::::::::::::
queue.h
::::::::::::::
#include

#define QUEUE_TYPE    int

void create_queue(size_t size);
void destroy_queue(void );
void insert(QUEUE_TYPE    value);
void delete(void);

QUEUE_TYPE first(void);
int is_empty(void);
int is_full(void);
void show_queue(void);

::::::::::::::
g_stack.h
::::::::::::::
#include

#define GENERIC_STACK( STACK_TYPE, SUFFIX, STACK_SIZE)    \
static STACK_TYPE    stack##SUFFIX[STACK_SIZE];\
static int        top_element##SUFFIX = -1;\
\
int                        \
is_empty##SUFFIX(void)                \
{                        \
}                        \
\
int                        \
is_full##SUFFIX(void)                \
{                        \
}                        \
\
void                        \
push##SUFFIX(STACK_TYPE value)            \
{                        \
assert(!is_full##SUFFIX());            \
top_element##SUFFIX += 1;            \
stack##SUFFIX[top_element##SUFFIX] = value;     \
}                        \
\
void                        \
pop##SUFFIX(void)                \
{                        \
assert(!is_empty##SUFFIX());            \
top_element##SUFFIX -= 1;            \
}                        \
\
STACK_TYPE top##SUFFIX(void)            \
{                        \
assert(!is_empty##SUFFIX());            \
return stack##SUFFIX[top_element##SUFFIX];    \
}

::::::::::::::
main.c
::::::::::::::
#include
#include

#include "tree.h"
#include "g_stack.h"
#include "point_stack.h"

#define MAXSIZE    50
#define MAXOPSIZE    100000
GENERIC_STACK(char,_char,30)
GENERIC_STACK(char,_char_2,30)

void getstring(char *str)
{
int i;
fgets(str, MAXSIZE, stdin);
}

int converse(char *str)
{
int i;
int count=0;
int num=0;
int mul=1;
while(str[count]!='\0' && str[count]!='\n')
count++;
for(i=count-1;i>=0;i--)
{
num += mul*(str[i]-'0');
mul *= 10;
}
return num;
}
int compare_op(char a,char b)
{
int flag_a;
int flag_b;

if(a == '+' || a == '-')
flag_a = 1;
else if(a == '*' || a == '/')
flag_a = 2;
else if(a == '^')
flag_a =3;
else if(a == '#' || a == '(')
flag_a = 0;

if(b == '+' || b == '-')
flag_b = 1;
else if(b == '*' || b == '/')
flag_b = 2;
else if(b == '^')
flag_b =3;
else if(b == '#' || b == '(')
flag_b = 0;

return flag_a - flag_b;
}
void print_op(char end_op)
{
while(top_char() != end_op)
{
push_char_2(top_char());
pop_char();
}
}
void reverse_char(char *des, char *src)
{
int i;
int j;
for(i=0;src[i] != '\0';i++);
for(j=0;j        des[j]=src[i-j-1];
des[j]='\0';
}

void MiddleToEnd(char *buffer)
{
int i;
char des[MAXSIZE];
char current_op;
push_char('#');
push_char_2('#');
for(i=0;buffer[i]!='\n';i++)
{
if(buffer[i] == ')')
{
print_op('(');
pop_char();
continue;
}

else if(buffer[i]  == '(')
{
push_char(buffer[i]);
continue;
}

if(isalnum(buffer[i]))
push_char_2(buffer[i]);
else
{
if(isalnum(buffer[i-1]))
push_char_2(' ');
current_op = buffer[i];
if(buf
fer[i]=='(' || compare_op(top_char(),current_op)<0)
push_char(buffer[i]);

else
{
while((compare_op(top_char(),current_op) > 0) || (compare_op(top_char(),current_op)== 0 ))
{
push_char_2(top_char());
pop_char();
}
push_char(buffer[i]);
}
}
}
print_op('#');
for(i=0;!is_empty_char_2();i++)
{
des[i]=top_char_2();
pop_char_2();
}
des[--i]='\0';
reverse_char(buffer,des);
}

SearchTree CreateExprTree(char *buffer)
{
int i;
int num;
char digit_str[20];
int str_count;
SearchTree p_l;
SearchTree p_r;
SearchTree op;

SearchTree T[100]={NULL};
int t_count = 0;
Stack S = NULL;

S = CreateStack();

for(i=0; buffer[i] != '\0'; i++)
{
//        printf("buffer[i]=%c\n",buffer[i]);
if(isdigit(buffer[i]))
{
str_count = 0;
while(isdigit(buffer[i]))
{
digit_str[str_count] = buffer[i];
i++;
str_count++;
}
if(!isspace(buffer[i]))
i--;
digit_str[str_count] = '\0';
num = converse(digit_str);

p_l = Insert(num, T[t_count]);
//    p_l = Find(num, T[t_count]);
//    printf("Push p_l for %d\n",num);
Push(p_l, S);
t_count++;
}
else
{
p_r = top(S);
Pop(S);

p_l = top(S);
Pop(S);

op = Insert(buffer[i]-MAXOPSIZE, T[t_count]);
op->Left = p_l;
op->Right = p_r;
Push(op, S);
t_count++;
}
}
return op;
}
int result(int a, int b, char op)
{
int i;
int mul_sum=1;
switch(op){
case '+':
return a+b;
break;
case '-':
return a-b;
break;
case '*':
return a*b;
break;
case '/':
return a/b;
break;
case '^':
for(i=b;i>0;i--)
mul_sum *= a;
return mul_sum;
break;
default:
break;
}
}

SearchTree CutTree(SearchTree T)
{
ElementType sum;
char op;
SearchTree t_l;
SearchTree t_r;
while(1)
{
if(T->Left->Element > 128 - MAXOPSIZE && T->Right->Element > 128 - MAXOPSIZE)
{
t_l = T->Left;
t_r = T->Right;
op = (char)(T->Element+MAXOPSIZE);
printf("\n%c ",op);
T->Element = result(T->Left->Element, T->Right->Element, op);
T->Left = T->Right = NULL;
printf("result is %d\n",T->Element);
free(t_l);
free(t_r);
return T;
}
else
{
if(T->Left->Element < 128 - MAXOPSIZE)
{
T->Left = CutTree(T->Left);
}
if(T->Right->Element < 128 - MAXOPSIZE)
{
T->Right = CutTree(T->Right);
}
}
}
return T;
}

int main(void)
{
char buffer[MAXSIZE];
int num;
int i;
char current_op;
char top_op;
SearchTree root = NULL;
Position res = NULL;

getstring(buffer);
MiddleToEnd(buffer);
printf("%s\n",buffer);

root = CreateExprTree(buffer);
//    ListTree(root, printf_s);
res = CutTree(root);
printf("The final result is %d\n",res->Element);

#ifdef DEBUG

push_char('#');
for(i=0;buffer[i]!='\n';i++)
{
if(buffer[i] == ')')
{
print_op('(');
pop_char();
continue;
}
if(isalnum(buffer[i]))
printf("%c",buffer[i]);
else
{
if(isalnum(buffer[i-1]))
printf(" ");
current_op = buffer[i];
//    if(buffer[i]=='(');
//        printf("%c\n",buffer[i]);
if(buffer[i]=='(' || compare_op(top_char(),current_op)<0)
push_char(buffer[i]);
else
{
while((compare_op(top_char(),current_op) > 0) || (compare_op(top_char(),current_op)==
0 ))
{
printf("%c",top_char());
pop_char();
}
push_char(buffer[i]);

}
}
}
print_op('#');
//    num = converse(buffer);
//    printf("%d\n",num);
#endif
}

::::::::::::::
point_stack.c
::::::::::::::
#include "point_stack.h"
#include
#include
#include

Stack CreateStack(void)
{
Stack S = NULL;
S = malloc(sizeof(struct Node *));
if(S == NULL)
{
printf("Fail to malloc\n");
return NULL;
}
S->Next = NULL;
return S;
}

void Push(ElementStackType X, Stack S)
{
Stack new;
new = malloc(sizeof(struct Node *));
if(new == NULL)
{
printf("Fail to malloc\n");
exit(1);
}
new->Element = X;
new->Next = S->Next;
S->Next = new;
}

ElementStackType top(Stack S)
{
if(!IsEmpty(S))
return S->Next->Element;
else
{
perror("Empty Stack!!!\n");
exit(1);
}
}
void Pop(Stack S)
{
Stack FirstCell = NULL;
if(IsEmpty(S))
{
perror("Empty Stack!!!\n");
exit(1);
}
else
{
FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);
}
}

int IsEmpty(Stack S)
{
return S->Next == NULL;
}

void MakeStackEmpty(Stack S)
{
Stack FirstCell = NULL;
if(S == NULL)
perror("Must use CreateStack first!\n");
else
while(S->Next != NULL)
{
FirstCell = S->Next;
Pop(S);
free(FirstCell);
}
}

::::::::::::::
point_stack.h
::::::::::::::
#ifndef __POINT_STACK_H_
#define __POINT_STACK_H_

#define ElementStackType void*

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void Push(ElementStackType X, Stack S);
ElementStackType top(Stack S);
void Pop(Stack S);

#endif

struct Node
{
ElementStackType Element;
PtrToNode Next;
};

::::::::::::::
tree.h
::::::::::::::
#ifndef __TREE_SH_
#define __TREE_SH_

#define ElementType int

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

SearchTree MakeEmpty(SearchTree T);
SearchTree CreateTree(void); //Don need it
Position Find(ElementType X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);
void ListTree(Position P, void (*callback)(ElementType X));
void printf_s(ElementType X);
int Count_Node(SearchTree T);

#endif

struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
};

::::::::::::::
tree.c
::::::::::::::
#include "tree.h"
#include
#include

#define MAXOP    100000
static int count = 0;

SearchTree CreateTree(void)
{
SearchTree new;
new = malloc(sizeof(SearchTree));
new->Left = new->Right = NULL;
return new;
}

SearchTree MakeEmpty(SearchTree T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
ElementType Retrieve(Position P)
{
return P->Element;
}

void printf_s(ElementType X)
{
if(X < -1)
printf("%c\n",X+MAXOP);
else
printf("%d\n",X);
}

void ListTree(Position P, void (*callback)(ElementType X))
{

if(P != NULL)
{
(*callback)(P->Element);
ListTree(P->Left,callback);
ListTree(P->Right,callback);
}

}
int Count_Node(SearchTree T)
{
if( T != NULL)
{
count++;
Count_Node(T->Left);
Count_Node(T->Right);
}
return count;
}

SearchTree Delete(ElementType X, SearchTree T)
{
Position P = T;
Position SmallRC = NULL;
if(P == NULL)
return NULL;
else if(X < P->Element)
P->Left = Delete(X, P->Left);
else if(X > P->Element)
P->Right = Delete(X, P->Right);
else if(X == P->Element)
{
if((P->Left != NULL) && (P->Right != NULL))
{
SmallRC = FindMin(P->Right);
P->Element = SmallRC->Element;
P->Right = Delete(P->Element,P->Right);

}
else if((P->Left == NULL)||(P->Right == NULL))
{
SmallRC = P;
if(P->Left == NULL)
P = P->Right;
else if(P->Right == NULL)
P = P->Left;

free(SmallRC);
}

}
return P;

}

int My_Delete(ElementType X, SearchTree T)
{
}

SearchTree Insert(ElementType X, SearchTree T)
{
if(T == NULL)
{
//    printf("insert %d\n",X);
T = malloc(sizeof(struct TreeNode *));
if(T == NULL)
{
perror("Fail to malloc memory for a new tree!!!\n");
return NULL;
}
T->Element = X;
T->Left = T->Right = NULL;
return T;
}
else
{
if(X < T->Element)
T->Left = Insert(X,T->Left);
else
T->Right = Insert(X,T->Right);
}
return T;

}

Position Find(ElementType X, SearchTree T)
{
Position P = T;
if(T == NULL)
return NULL;
while(P != NULL)
{
if(X < P->Element)
P = P->Left;
else if(X > P->Element)
P = P->Right;
else
return P;
}
return NULL;
}

Position FindMin(SearchTree T)
{
Position P = T;
while(P->Left !=NULL)
P = P->Left;
return P;
}

Position FindMax(SearchTree T)
{
Position P = T;
while(P->Right != NULL)
P = P->Right;
return P;

}

jiayanfu2011-08-11 23:05:04