后缀表达式转表达式树

思路:

1. 遇到普通字符,创建叶节点, 压栈;
2. 遇到运算符, 创建运算符节点, 弹出栈顶两个节点作为,运算符节点的左右子节点, 压栈;
3. 后缀表达式完整的话, 最后栈中留一元素,指向的表达式树的根节点.

#include "stdlib.h"
#include "stdio.h"
#include "string.h"

typedef char bool;

#ifndef true
#define true 1
#endif
#ifndef false
#define false 0
#endif

typedef char element_type;

typedef struct tree_node {
    element_type element;
    struct tree_node *left_child, *right_child;
    //struct tree_node *parent;
} tree_node_t;

char operator_tbl[4] =
{
    '+', '-', '*', '/',
};

bool is_operator(char c)
{
    for (int i = 0; i < 4; i++) {
        if (c == operator_tbl[i])
            return true;
    }
    return false;
}

tree_node_t *create_node(element_type element)
{
    tree_node_t *node;
    node = (tree_node_t *)malloc(sizeof(tree_node_t));
    node->element = element;
    node->left_child = NULL;
    node->right_child = NULL;
    return node;
}

typedef struct {
   tree_node_t *node[128];
   int top;
} tree_node_stack_t;

tree_node_stack_t tree_node_stack;

void push_tree_node_stack(tree_node_t* node)
{
    if (tree_node_stack.top < 127 && node != NULL)
    {
        tree_node_stack.node[tree_node_stack.top++] = node;
        printf("push stack elemnt %c\n", node->element);
    }
}

tree_node_t* pop_tree_node_stack(void)
{
    if (tree_node_stack.top > 0)
    {
       tree_node_stack.top--;
       tree_node_t* node = tree_node_stack.node[tree_node_stack.top];
       printf("pop stack elemnt %c\n", node->element);
       return node;
    }
    else
    {
        return NULL;
    }
}

bool suffix_trans_tree(char* suffix)
{
    element_type element;
    tree_node_t *node;
    tree_node_t *left_child, *right_child;
    while((element = *suffix++) != '\0') 
    {
        node = create_node(element);
        if (true == is_operator(element)) {
            /* merge */
            right_child = pop_tree_node_stack();
            if (right_child == NULL) {
                printf("pop stack failed\n");
                return false;
            }
            left_child = pop_tree_node_stack();
            if (left_child == NULL) {
                printf("pop stack failed\n");
                return false;
            }
            node->right_child = right_child;
            node->left_child = left_child;
            push_tree_node_stack(node);
        }
        else {
            push_tree_node_stack(node);
        }
    }
    return true;
}

#define MAX(a, b) ((a) > (b)? (a): (b))
int get_tree_depth(tree_node_t *root)
{
    if (root == NULL) return 0;
    int left_depth = get_tree_depth(root->left_child);
    int right_depth = get_tree_depth(root->right_child);
    return MAX(left_depth,right_depth) + 1;//child depth + cur depth 1
}

static int print_pos_x;
static int print_tree_high;

#define ELMENT_PRINT_SPACE  (5)
#define ELMENT_PRINT_OFFSET(m,l)  (((m) - (l)) / 2)
#define ELMENT_PRINT_MAX_DEPTH  (6)
#define CALC_PRINT_ELMENT_TAKE_PLACE(l,x) ((1 << (l - 1)) * x + x)
#define ELMENT_PRINT_MAX_DEPTH_SPACE  CALC_PRINT_ELMENT_TAKE_PLACE(ELMENT_PRINT_MAX_DEPTH, ELMENT_PRINT_SPACE)
char print_buffer[ELMENT_PRINT_MAX_DEPTH][ELMENT_PRINT_MAX_DEPTH_SPACE];

void print_core_tree(tree_node_t* node, int level)
{
    if (node == NULL) {
        print_pos_x += ELMENT_PRINT_SPACE * (print_tree_high - level);
        return;
    }

    print_core_tree(node->left_child, level + 1);
    char str_element[10];
    sprintf(str_element, "%c", node->element);
    int len = strlen(str_element);
    memcpy(&print_buffer[level][print_pos_x + ELMENT_PRINT_OFFSET(ELMENT_PRINT_SPACE, len)], str_element, len);
    print_pos_x += ELMENT_PRINT_SPACE;
    print_core_tree(node->right_child, level + 1);
}

void print_tree(tree_node_t* root)
{
    if (root == NULL) return;

    int i,j;
    print_pos_x = ELMENT_PRINT_SPACE / 2;
    print_tree_high = get_tree_depth(root);
    if (print_tree_high > ELMENT_PRINT_MAX_DEPTH) {
        printf("warning: only support %d depth\n", ELMENT_PRINT_MAX_DEPTH);
    }

    for (i = 0; i < ELMENT_PRINT_MAX_DEPTH; i++)
    {
        for (j = 0; j < ELMENT_PRINT_MAX_DEPTH_SPACE; j++)
        {
            print_buffer[i][j] = 0x7f;    
        }
    }
    print_core_tree(root, 0);

    for (i = 0; i < print_pos_x; i++) printf("=");
    printf("\n");
    for (i = 0; i < print_tree_high; i++)
    {
        for (j = 0; j < print_pos_x; j++)
        {
            if (print_buffer[i][j] == 0x7f) printf(" ");
            else printf("%c", print_buffer[i][j]);            
        }
        printf("\n\n");
    }
    for (i = 0; i < print_pos_x; i++) printf("=");
    printf("\n");
}

int get_line(char* buf, int max_size)
{
    int cnt = 0;
    *buf = '\0';
    while(1) {
        char c = getchar();
        if (c == '\n') {
            *buf++ = '\0';
            break;
        }
        if (c == ' ') {
            continue;
        }
        //printf("%c", c);
        *buf++ = c;
        cnt++;
        if(cnt == 1023) {
            break;
        }
    }
    return cnt;
}

char recv_buffer[1024];

int main(int argc, char* argv[])
{
    memset(recv_buffer, 0, 1024);

    if (get_line(recv_buffer, 1024) > 0) 
    {
        printf("suffix: %s\n", recv_buffer);
        if (true == suffix_trans_tree(recv_buffer)) {
            tree_node_t* root = pop_tree_node_stack();
            if (root) {
                print_tree(root); 
            }
            else {
                printf("pop root failed\n"); 
            }
        }
        else {
            printf("trans failed\n");
        }
    }

    getchar();

    return 0;
}

运算结果:

prefix2suffix.jpg