将表达式转化为表达式树

expressionTree.c

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

struct TreeNode;
typedef struct TreeNode * ptrToTreeNode;
typedef struct ptrToTreeNode Tree;
struct TreeNode {
    char element;
    Tree left;
    Tree right;
};

typedef ptrToTreeNode ElementType;
struct StackRecord;
typedef struct StackRecord *Stack;
int isEmpty(Stack s);
int isFull(Stack s);
void disposeStack(Stack s);
Stack createStack(int amount);
void makeEmpty(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 (amount < minStackSize)
    {
        printf("amount is too small...\n");
        exit(-1);
    }
    s = (Stack)malloc(sizeof(struct StackRecord));
    if (s == NULL) {
        printf("malloc failed...\n");
    }
    s->array = (ElementType *)malloc(sizeof(ElementType)*amount);
    if (s->array == NULL) {
        printf("malloc failed...\n");
    }

    s->capacity = amount;
    makeEmpty(s);
    return s;
}

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

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

void makeEmpty(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;
    }
}

void 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);
    }
    else {
        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 = "+-*/";
    for(int i = 0;i<4;i++) {
        if (ch == operators[i]) {
            return 1;
        }
   }
   return 0;
}

Tree buildExpressionTree(char * expressions)
{
    int length = strlen(expressions);
    int j = 0;
    Stack s = (Stack)malloc(sizeof(struct StackRecord));
    makeEmpty(s);
    for (int i = 0;i < length;i++) {
        if (!isOperator(expressions[i])) {
            Tree atree = (Tree)malloc(sizeof(struct TreeNode));
            atree->element = expressions[i];
            atree->left = NULL;atree->right = NULL;
            push(atree, s);
        }
        else {
            Tree tree1 = topAndPop(s);
            Tree tree2 = topAndPop(s);
            Tree newTree = (Tree)malloc(sizeof(struct TreeNode));
            newTree->element = expressions[i];
            newTree->left = tree1;
            newTree->right = tree2;
            push(newTree,s);
        }
    }

    Tree node = top(s);
    disposeStack(s);
    return node;
}

int main(void)
{
    printf("Hello World!\n");
    return 0;
}