大神的世界

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct node{
    char value[MAX_SIZE];
    int result;
    struct node *leftChild;
    struct node *rightChild;
}Tree;

void parse(char prefix[], int *pos, char buffer[])
{
    int i = 0;
    while(prefix[*pos] == ' ')
        (*pos)++;

    if(isdigit(prefix[*pos])){
        while(isdigit(prefix[*pos]))
            buffer[i++] = prefix[(*pos)++];
        buffer[i] = '\0';
    }
    else{
        buffer[0] = prefix[(*pos)++];
        buffer[1] = '\0';
    }
}

Tree *createExpressionTree(char expression[])
{
    int len = strlen(expression);

    Tree * stack[MAX_SIZE];
    int top = -1;

    Tree *root, *tmp;
    root = tmp = NULL;

    for(int i = 0; i<len; ){
        Tree * treeNode = (Tree*)malloc(sizeof(treeNode));
        parse(expression, &i, treeNode->value);

        if(!root){
            root = treeNode;
            stack[++top] = root;
            tmp = root;
        }
        else{
            if(isdigit(tmp->value[0])){
                tmp = stack[top--];
                tmp->rightChild = treeNode;
                tmp = tmp->rightChild;
            }
            else{
                tmp->leftChild = treeNode;
                stack[++top] = tmp;
                tmp = tmp->leftChild;
            }
        }
    }

    return root;
}

void Evaluate(Tree *root)
{
    if(isdigit(root->value[0]))
        root->result = atoi(root->value);
    else{
        Evaluate(root->leftChild);
        Evaluate(root->rightChild);

        switch(root->value[0]){
            case '+':
                root->result = root->leftChild->result + root->rightChild->result;
                break;

            case '-':
                root->result = root->leftChild->result - root->rightChild->result;
                break;

            case '*':
                root->result = root->leftChild->result * root->rightChild->result;
                break;

            case '/':
                root->result = root->leftChild->result / root->rightChild->result;
                break;

            default:
                printf("error occured! Unrecognize symbol\n");
                exit(1);
        }
    }
}

int main()
{
    /* To create an expression tree, prefix is a good choice.
       Here, we skip the step of transforming, just focus on 
       how to create. */

    char expression[] = "+ * / 4 2 - + 3 2 1 - 5 2";

    Tree *Tree_A;
    Tree_A = createExpressionTree(expression);

    Evaluate(Tree_A);

    printf("answer = %d\n", Tree_A->result);
    return 0;
}