生成表达式树
栈及中缀表达式转后缀表达式的实现看之前的日志//>>>>>>mocro.h#ifndef _MACRO_H_#define _MACRO_H_#define EmptyTOS (-1)#define MinStackSize (5)#define ElementType int#endif//>>>>>>struct.h#ifndef _STRUCT_H_#define _STRUCT_H_#include "macro.h"/*< stack struct */typedef struct StackRecord{ int Capacity; int TopOfStack; ElementType * Array;}STACK_RECORD;typedef STACK_RECORD * Stack;/*< tree struct*/typedef struct TreeNode{ int value; TreeNode * Left; TreeNode * Right;}TreeNode;typedef TreeNode * Tree;#endif//>>>>>>stack.h#ifndef _STACK_H_#define _STACK_H_#include "macro.h"#include "struct.h"//清空栈void MakeEmpty(Stack S);//生成容量为MaxElements的栈Stack CreateStack(int MaxElements);//判断栈是否为空int IsEmpty(Stack S);//判断栈是否已满int IsFull(Stack S);//释放所有栈空间void DisposeStack(Stack S);//进栈void Push(ElementType X,Stack S);//出栈void Pop(Stack S);//返回栈顶数据ElementType Top(Stack S);//出栈并返回数值ElementType TopAndPop(Stack S);#endif//>>>>>>tree.h#ifndef _TREE_H_#define _TREE_H_#include "macro.h"#include "struct.h"#include "stack.h"//清空树void ClearTree(Tree t);//创建节点Tree CreateNode(int x);//先序遍历void Preorder_TreePrint(Tree t);//中序遍历void Inorder_TreePrint(Tree t);//后续遍历void Postorder_TreePrint(Tree t);#endif//>>>>>infix_suffix_conv.h#ifndef _INFIX_SUFFIX_CONV_#define _INFIX_SUFFIX_CONV_#include "macro.h"#include "struct.h"#include "stack.h"//获得符号优先级int getLevel(char symbol);//判断字符是否为符号int isSymbol(char ch);//中缀表达式转后缀表达式void infix_suffix_convert(char * infixStr,char * suffixStr);#endif//>>>>>>expTree.c#include<stdio.h>#include<string.h>#include<stdlib.h>#include"tree.h"#include "infix_suffix_conv.h"//清空树void ClearTree(Tree t){if(t!=NULL){ClearTree(t->Left);ClearTree(t->Right);free(t);}}//创建节点Tree CreateNode(int x){Tree tree = (Tree)malloc(sizeof(TreeNode));tree->value = x;tree->Left = NULL;tree->Right = NULL;return tree;}//先序遍历void Preorder_TreePrint(Tree root){if(root!=NULL){if(root->Left == NULL && root->Right == NULL)printf("%d ",root->value);elseprintf("%c ",root->value);Preorder_TreePrint(root->Left);Preorder_TreePrint(root->Right);}}//中序遍历void Inorder_TreePrint(Tree root){if(root!=NULL){Inorder_TreePrint(root->Left);if(root->Left == NULL && root->Right == NULL)printf("%d ",root->value);elseprintf("%c ",root->value);Inorder_TreePrint(root->Right);}}//后续遍历void Postorder_TreePrint(Tree root){if(root!=NULL){Postorder_TreePrint(root->Left);Postorder_TreePrint(root->Right);if(root->Left == NULL && root->Right == NULL)printf("%d ",root->value);elseprintf("%c ",root->value);}}//生成表达式树Tree expTree(char * suffixStr){Stack treeStack = CreateStack(20); int iCount = strlen(suffixStr),i,j,k,flag,n; i=j=k=n=flag=0; for(i=0;i<=iCount;i++) { if(isSymbol(suffixStr)) {Tree tree = (Tree)malloc(sizeof(TreeNode)); tree->value = suffixStr;if(!IsEmpty(treeStack))tree->Right = (Tree)TopAndPop(treeStack);elsetree->Right = NULL;if(!IsEmpty(treeStack))tree->Left = (Tree)TopAndPop(treeStack);elsetree->Left = NULL;if(!IsFull(treeStack))Push((int)tree,treeStack);elseprintf("The stack is full!\n");flag=2; } else if(suffixStr>='0' && suffixStr<='9') {if(flag == 2 || flag == 0) {Tree node = CreateNode(atoi(&suffixStr));if(!IsFull(treeStack))Push((int)node,treeStack);elseprintf("The stack is full!\n");flag = 3; } } else { flag = 2; } }if(!IsEmpty(treeStack)) return (Tree)TopAndPop(treeStack); else return NULL;}////mainint main(void){char * infix = "(1+2323)*55/26+83-(77+2)*32";char suffix;memset(suffix,0,sizeof(suffix));infix_suffix_convert(infix, suffix);puts(suffix);///----Tree root = expTree(suffix);Postorder_TreePrint(root);putchar('\n');ClearTree(root); return 0;}
页:
[1]