C语言实现算术表达式语法树生成

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

typedef struct node{ char data; struct node *left,*right; }node;

void E(); void T(); void F(); char exp[50]; //算术表达式区 int i=0;
char w; //当前单词

node* create_node(char data){ node new_node = (node)malloc(sizeof(node)); new_node->data = data; new_node->left = NULL; new_node->right = NULL; return new_node; }

node* create_tree(char *exp){ node *root = create_node(exp[0]); node cur = root; int i = 1; while(exp[i] != '\0'){ if(exp[i] == '+'){ cur->right = create_node(exp[i+1]); cur = cur->right; i += 2; } else if(exp[i] == '-'){ cur->right = create_node(exp[i+1]); cur = cur->right; i += 2; } else if(exp[i] == ''){ node *new_node = create_node(exp[i+1]); new_node->left = cur->right; cur->right = new_node; cur = new_node; i += 2; } else if(exp[i] == '/'){ node new_node = create_node(exp[i+1]); new_node->left = cur->right; cur->right = new_node; cur = new_node; i += 2; } else if(exp[i] == '('){ int j = i+1; int num = 1; while(num != 0){ if(exp[j] == '(') num++; if(exp[j] == ')') num--; j++; } char sub_exp = (char)malloc(sizeof(char)(j-i-1)); strncpy(sub_exp, exp+i+1, j-i-2); sub_exp[j-i-2] = '\0'; node *sub_tree = create_tree(sub_exp); cur->right = sub_tree; cur = sub_tree; i = j; } else{ i++; } } return root; }

void print_tree(node *root, int depth){ if(root != NULL){ for(int i=0; i<depth; i++){ printf(" "); } printf("%c\n", root->data); print_tree(root->left, depth+1); print_tree(root->right, depth+1); } }

int main(int argc, char* argv[]){ printf("please input your expression:"); scanf("%s",exp); //输入表达式 w=exp[i++]; //read(w) E();
if (w=='#'){ printf("OK!\n"); node *root = create_tree(exp); printf("Syntax Tree:\n"); print_tree(root, 0); } else{ printf("err\n"); } return 0; }

void E(){ T(); while ( w=='+' || w=='-') { w=exp[i++]; //read(w) T(); } } void T(){ F(); while ( w=='*' || w=='/') { w=exp[i++]; //read(w) F(); } } void F(){ if ( w=='(') { w=exp[i++]; //read(w) E(); if ( w!=')') { printf("err\n"); } else w=exp[i++]; //read(w) } else if ((w>='a' && w<='p')||(w>='0' && w<='9')) { w=exp[i++]; //read(w) } else { printf("err\n"); }