将中缀表达式转换为后缀表达式

midToPost.c

#include <stdio.h>
#include <stdlib.h>
#include <cstring>


typedef char ElementType;
struct StackRecord;
typedef struct StackRecord *Stack;
int isEmpty(Stack s);
int isFull(Stack s);
Stack createStack(int amount);
void disposeStack(Stack s);
void makeEmtpy(Stack s);
void push(ElementType x,Stack s);
ElementType  top(Stack s);
void pop(Stack s);
ElementType  topAndPop(Stack s);

#define  EmptyTos -1
#define  minStackSize 2
struct StackRecord {
    int capacity;
    int topOfStack;
    ElementType  *array;
};

Stack createStack(int amount)
{
    Stack s;
    if (minStackSize > amount) {
        printf("amount is too small...\n");
        exit(-1);
    }

    s = (Stack)malloc(sizeof(struct StackRecord));
    if (s == NULL) {
        printf("failed to malloc...\n");
    }
    s->array = (ElementType *)malloc(sizeof(ElementType)*amount);
    if (s->array == NULL) {
        printf("failed to malloc...\n");
    }
    s->capacity = amount;
    makeEmtpy(s);
    return  s;
}

void disposeStack(Stack s)
{
    if (s != NULL) {
        free(s->array);
        free(s);
    }
}


int isEmpty(Stack s)
{
    return  s->topOfStack == EmptyTos;
}

void makeEmtpy(Stack s)
{
    s->topOfStack = EmptyTos;
}

void push(ElementType x,Stack s)
{
    if (isFull(s)) {
        printf("stack is full...\n");
        exit(-1);
    } else {
        s->topOfStack++;
        s->array[s->topOfStack] = x;
    }
}

int isFull(Stack s)
{
    return  s->topOfStack == s->capacity-1;
}

void pop(Stack s)
{
    if (isEmpty(s)) {
        printf("stack is empty...\n");
        exit(-1);
    } else {
        s->topOfStack--;
    }
}

ElementType  top(Stack s)
{
    if (isEmpty(s)) {
        printf("stack is empty...\n");
        exit(-1);
    }
    return s->array[s->topOfStack];
}

ElementType  topAndPop(Stack s)
{
    if (isEmpty(s)) {
        printf("stack is empty...\n");
        exit(-1);
    } else {
        return  s->array[s->topOfStack--];
    }
}

int isOperator(char ch)
{
    char operators[4] = {'+','-','*','/'};
    for(int i = 0;i < 4;i++) {
        if (ch == operators[i]) {
            return  1;
        }
    }
    return 0;
}

int precedence(char ch)
{
    if (ch == '(') {
        return  -1;
    } else if (ch == '+' || ch == '-') {
        return 0;
    } else if (ch == '*' || ch == '/') {
        return 1;
    }
}

void midToPost(char *mid, char *post)
{
    int lenOfMid = strlen(mid);
    Stack expressions = createStack(lenOfMid);
    makeEmtpy(expressions);
    int j = 0;
    for(int i = 0;i < lenOfMid;i++) {
        if (mid[i] == '(') {
            push(mid[i],expressions);
        } else if (mid[i] == ')') {
            while (top(expressions) != '(') {
                post[j++] = topAndPop(expressions);
            }
            pop(expressions);
        }
        else {
            if (!isOperator(mid[i])) {
                post[j++] = mid[i];
            } else {
                while (isEmpty(expressions) == 0 && precedence(top(expressions)) >= precedence(mid[i])) {
                    post[j++] = topAndPop(expressions);
                }
                push(mid[i],expressions);
            }
        }
    }

    while (isEmpty(expressions) == 0) {
        post[j++] = topAndPop(expressions);
    }

    post[j] = 0;
}


int main()
{
    char mid[100],post[100];
    printf("input the mid expression: ");
    gets(mid);
    printf("mid expression is %s\n",mid);
    midToPost(mid,post);
    printf("post expression is %s\n",post);
    return 0;
}