/*the filename: main
*the filename extension: .c
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"list.h"
int isOperator(char the_char) //判斷是否為運算子
{
if(the_char=='+'||the_char=='-'||the_char=='*'||the_char=='/') //是運算子，回傳1，並跳出subfunction
{
return 1;
}
return 0; //若不是運算子，回傳0
}
int lower_priority(char data,char the_char) //在convert_infix_to_posfix函式內，已經有判斷myList內是否有東西個機制，所以在此不用考慮mylist為空的情況
{
if(the_char == '+'||the_char=='-') //輸入進來的運算子只要是'+'或'-'，就屬於最低優先的運算子，不管mylist內存放哪一種運算子，在pop_all_higher函式內，必須把該原本存放在mylist內最上層的運算子印出來，並從mylist中刪除
{
return 1;
}
else if(data == '*' || data == '/') //經過上一個if的判斷，可以確定輸入進來的運算子是'*'或'/'，如果mylist內存放在最上面的運算子是最高優先權的運算子(即：'*'或'/')，代表輸入進來的運算子權限並沒有比mylist內最上層的運算子高，所以在pop_all_higher函式內，必須把原本存放在mylist內最上層的運算子印出來，並從mylist中刪除
{
return 1;
}
return 0;
}
//pop_all_higher函式用來印出並清空所有在mylist中的運算子，這些在mylist中的運算子之優先權高於或等於所輸入進來的運算子
void pop_all_higher(List *mylist,char the_char) //這裡的the_char就是指在convert_infix_to_posfix函式內用來記錄當前運算式字元的the_char
{
Node *x; //所宣告的NODE內，包含一個用來'記錄當前運算子的char data'和'紀錄下一個NODE位置的struct node *link'
while(!empty_list(mylist)) //判斷存放運算子的stack(即myList)內是否有東西
{
x = get_first_list(mylist); //取出stack(即mylist)內最上面的資料，並回傳給x
if(!lower_priority(x->data,the_char)) //判斷當前輸入進來的運算子權限是否有高過原本在mylist內最上層的運算子，如果有，就跳出subfunction，並且在convert_infix_to_postfix函式內，將其存入mylist中
{
return;
}
printf("%c",x->data); //如果當前輸入的運算子是最低優先的運算子，就印出原本在mylist中最上層的運算子
delete_first_list(mylist); ////並且把該最上層的運算子從mylist中刪除
}
return;
}
void pop_all(char *mylist) //印出剩下還存放在mylist內的運算子，並清空mylist
{
Node *x;
while(!empty_list(mylist))
{
x=get_first_list(mylist);
printf("%c",x->data);
delete_first_list(mylist);
}
return;
}
void convert_infix_to_postfix()
{
char input[24];
char the_char; //用the_char來紀錄下面for迴圈中所檢視到的當前運算式字元
List *mylist;
int lg;
int i;
mylist = (List *) malloc(sizeof(List));
creat_list(mylist); //剛創好的mylist內，count為0，代表裡面尚未有資料，所以head接地(NULL)
printf("the test sequence : ");
scanf("%s",input); //輸入一個數學運算式，例如：a+b*k-c
lg = strlen(input); //計算輸入的運算式長度，以此例子為例，其長度為7
for(i=0; i<lg; i++) //一個個細細地去檢視所輸入的數學運算式的每一個字元內容為何
{
the_char = input[i]; //把當前數學運算式的字元傳給the_char
if(isOperator(the_char)) //判斷當前的運算式字元是否為運算子(即:'+'、'-'、'*'、'/')
{
if(!empty_list(mylist)) //判斷mylist內是否有資料，如果沒有，跳過此if判斷式
{
pop_all_higher(mylist,the_char); //如果輸入的運算子優先權低，就把原本在mylist內的運算子都印出來並且清空
}
insert_first_list(mylist,the_char); //如果數學運算式當前的字元為運算子且優先權限不是最低(在pop_all_higher函式中會去判斷)，就把他存入mylist中
}
else
{
printf("%c",the_char); //如果當前的數學運算式字元不是運算子，就把他直接印出來即可
}
}
pop_all(mylist); //當檢視完所輸入的數學運算式之每個字元時，只要mylist內還有存放運算子，均無條件把他印出
return;
}
void prase()
{
char input[24];
char the_char; //用the_char來紀錄下面for迴圈中所檢視到的當前運算式字元
List *mylist;
mylist = (List*) malloc(sizeof(List));
creat_list(mylist); //剛創好的mylist內，count為0，代表裡面尚未有資料，所以head接地(NULL)
int i;
int lg;
printf("Please enter the test sequence :");
scanf("%s",input); //輸入一個數學運算式，例如：(a+b*k-c
lg = strlen(input); //計算輸入的運算式長度，以此例子為例，其長度為8
for(i=0; i<lg; i++)
{
the_char = input[i]; //把當前數學運算式的字元傳給the_char
if(the_char=='(') //如果為左括號，將其存入myList
{
insert_first_list(mylist,the_char);
}
else if(the_char==')') //如果為右括號，判斷mylist是否為空(即：有沒有一個左括號與之對應)
{
if(empty_list(mylist)) //如果mylist為空，代表沒有左括號與')'對應
{
printf("the closing parenthesis not matched\n"); //故印出"右括號不匹配"
return; //並且跳出parse函式
}
delete_first_list(mylist); //如果mylist為非空(即：mylist裡面存有一個左括號與當前所輸入的右括號對應)，故清掉mylist中的一個'('
}
}
if(!empty_list(mylist)) //如果到最後(此時，已經檢查完所有輸入的運算式字元)，發現mylist竟然沒有被清空，就表示一定有至少一個'('
{
printf("the opening parenthesis not matched\n"); //故印出"左括號不匹配"
return; //並且跳出parse函式
}
else //如果mylist皆已清空，代表'('與')'完全配對
{
printf("the perfect match\n"); //故印出"完美配對"
return; //並且跳出parse函式
}
}
void student_app()
{
s_List *mylist = (s_List *)malloc(sizeof(s_List));
s_creat_list(mylist);
FILE *f=fopen("d:/cs/score.dat","r");
int sid;
char sname[24];
int score;
while(fscanf(f,"%d %s %d",&sid,sname,&score)!=EOF)
{
s_insert_first_list(mylist,sid,sname,score);
}
fclose(f);
s_Node *get_hscore_student(s_List *list)
{
s_Node *hstudent;
s_Node *c;
if(list->count == 0)
{
return NULL;
}
else
{
hstudent = list->head;
for(c=hstudent->link; c!=NULL; c=c->link)
{
if(c->score > hstudent->score)
{
hstudent = c;
}
}
return hstudent;
}
}
s_print_list(mylist);
printf("*************\n");
s_Node *x;
x=get_hscore_student(mylist);
printf("the high score student is:\n");
s_dump_node(x);
}
int main()
{
convert_infix_to_postfix(); //postponement
printf("\n\n");
prase(); //parsing
printf("\n\n");
student_app();
return 0;
}
/*the filename: list
*the filename extension: .h
*/
typedef struct node{
char data;
struct node *link;
}Node;
typedef struct s_node{
int sid;
char sname[24];
int score;
struct s_node *link;
}s_Node;
typedef struct list{
int count;
Node *head;
}List;
typedef struct s_list{
int count;
s_Node *head;
}s_List;
void creat_list(List *list);
void s_creat_list(s_List *list);
void insert_first_list(List *list,char data);
void s_insert_first_list(s_List *list,int sid,char *sname,int score);
void print_list(List *list);
void s_print_list(s_List *list);
void dump_node(Node *input);
void s_dump_node(s_Node *input);
void delete_first_list(List *list); //student_app不會用到
Node *get_first_list(List *list); //student_app不會用到
int empty_list(List *list); //student_app不會用到
/*the filename: list_implement
*the filename extension: .c
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"list.h"
void creat_list(List *list)
{
list->count = 0;
list ->head =NULL;
return;
}
void s_creat_list(s_List *list)
{
list->count = 0;
list ->head =NULL;
return;
}
void insert_first_list(List *list,char data)
{
Node *p;
p = (Node *) malloc(sizeof(Node));
p->data = data;
p->link = list->head;
list->head = p;
list->count++;
return;
}
void s_insert_first_list(s_List *list,int sid,char *sname,int score)
{
s_Node *p;
p = (s_Node *) malloc(sizeof(s_Node));
p->sid = sid;
strcpy(p->sname,sname);
p->score = score;
p->link = list->head;
list->head = p;
list->count++;
return;
}
void print_list(List *list)
{
Node *c;
if(list->count == 0)
{
printf("the list is empty\n");
}
else
{
printf("the total count = %d",list->count);
for(c = list->head; c!=NULL; c=c->link)
{
dump_node(c);
}
}
return;
}
void s_print_list(s_List *list)
{
s_Node *c;
if(list->count == 0)
{
printf("the list is empty\n");
}
else
{
printf("the total count = %d\n",list->count);
for(c = list->head; c!=NULL; c=c->link)
{
s_dump_node(c);
}
}
return;
}
void dump_node(Node *input)
{
if(input!=NULL)
{
printf("the record: %c",input->data);
}
return;
}
void s_dump_node(s_Node *input)
{
if(input!=NULL)
{
printf("the record: %d \t %s \t %d\n",input->sid,input->sname,input->score);
}
return;
}
void delete_first_list(List *list)
{
Node *p;
if(list->head==NULL)
{
//do nothing
}
else
{
p=list->head;
list->head=p->link;
list->count--;
free(p);
}
return;
}
Node *get_first_list(List *list)
{
Node *p;
if(list->head==NULL)
{
// do nothing
return NULL;
}
else
{
p=list->head;
return p;
}
}
int empty_list(List *list) //判斷list內有無資料
{
if(list->head==NULL) //如果list內沒有資料，回傳1
{
return 1;
}
else //如果list內有資料，回傳0
{
return 0;
}
}
圖解說明
1.convert_Infix_to_Postfix
沒有留言:
張貼留言