example for parsing(解析)、postponement(Infix to Postfix)

 /*the filename: main
 *the filename extension: .c
 */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int isOperator(char x) {
    if (x == '+' || x == '-' ||
        x == '*' || x == '/'){
            return 1;
        }
    return 0;
}

int lowerPriority(char a, char b){
    if (a == '+' || a == '-'){
        return 1;
    }
    else{
        if (b == '*' || b == '/'){
            return 1;
        }
    }
    return 0;
}

void popAllHigher(LIST *inList, char op){
    NODE *x;
    while (!emptyList(inList)){
        x = getFirstList(inList);
        if (!lowerPriority(op, x->data)){
            return;
        }
        printf("%c",  x->data);
        deleteFirstList(inList);
    }
}

void popAll(LIST *inList){
    NODE *x;
    while (!emptyList(inList)){
        x = getFirstList(inList);
        printf("%c",  x->data);
        deleteFirstList(inList);
    }
}

void convertInfix_to_Postfix() {
    char input[20];
    char theChar, topChar;
    int i;
    int length;
    LIST *myList;
    NODE *x;
    myList = (LIST *) malloc(sizeof(LIST));
    creatList(myList);
    printf("input the test sequence: ");
    scanf ("%s", input);
    length = strlen(input);
    for (i=0; i<length; i++){
        theChar = input[i];
        if (isOperator(theChar)){
             if (!emptyList(myList)) {
                 popAllHigher(myList, theChar);
             }
             insertFirstList(myList, theChar);
        }
        else {
            printf("%c", theChar);
        }
    }
    popAll(myList);
}

void parse(){
    char input[20];
    char theChar;
    int i;
    int length;
    LIST *myList;
    NODE *x;
    myList = (LIST *) malloc(sizeof(LIST));
    creatList(myList);
    printf("input the test sequence: ");
    scanf ("%s", input);
    length = strlen(input);
    for (i=0; i<length; i++){
        theChar = input[i];
        if (theChar == '('){
            insertFirstList(myList, theChar);
        }
        else if (theChar == ')'){
            if (emptyList(myList)){
                printf("the closing parenthesis not matched \n");
                return;
            }
            deleteFirstList(myList);
        }
        else {
            // do nothing
        }
    }
    if (!emptyList(myList)){
        printf("the opening parenthesis not matched \n");
        return;
    }
    else {
        printf("It is a perfect MTACH\n");
        return;
    }

 }

int main()
{
   parse();   //parsing
   convertInfix_to_Postfix();  //postponement
}

 /*the filename: list
 *the filename extension: .h
 */

typedef struct node {
    char data;
    struct node *link;
} NODE;

typedef struct list {
    int count;
    struct node *head;
} LIST;


void creatList(LIST *listHead);
void insertFirstList(LIST *listHead, char data);
void printList(LIST *listHead);
void dumpNode(NODE *input);
void deleteFirstList(LIST *listHead);
NODE *getFirstList(LIST *listHead);
int emptyList(LIST *listHead);

 /*the filename: list_implement
 *the filename extension: .c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

void creatList(LIST *listHead) {

    listHead->count = 0;
    listHead->head = NULL;
}

void insertFirstList(LIST *listHead, char data){
    NODE *pNew;
    pNew = (NODE *) malloc(sizeof(struct node));
    pNew->data = data;

    if (listHead->head == NULL){ // case 1: empty list
        pNew->link = NULL;
        listHead->head = pNew;
    }
    else { // case 2: begining list
        pNew->link = listHead->head;
        listHead->head = pNew;
    }
    listHead->count++;
}

void deleteFirstList(LIST *listHead){
    NODE *pLoc;
    if (listHead->count == 0){
        printf("Do nothing \n");
    }else if (listHead->count == 1){
        pLoc = listHead->head;
        listHead->head = NULL;
        listHead->count--;
        free(pLoc);
    } else {
        pLoc = listHead->head;
        listHead->head = pLoc->link;
        listHead->count--;
        free(pLoc);
    }
}

int emptyList(LIST *listHead){
    if (listHead->count == 0){
        return 1;
    }
    else {
        return 0;
    }

}

NODE *getFirstList(LIST *listHead){
    NODE *pLoc;
    if (listHead->count == 0){
        // do nothing
    }else {
        pLoc = listHead->head;
        return pLoc;
    }
}

void dumpNode(NODE *input){
    if (input != NULL){
        printf("the record: %c \n", input->data);
    }
}


void printList(LIST *listHead){

    NODE *curr;
    if (listHead->head != NULL){
        printf("the total count = %d\n", listHead->count);
        for (curr = listHead->head; curr != NULL; curr = curr->link){
            dumpNode(curr);
        }
    }
    else{
        printf("the list is empty\n");
    }
}