1 #ifndef _btree_h_ 2 #define _btree_h_ 3  4 #include "iostream" 5 #include "stdlib.h" 6  7 typedef struct _btree_ 8 { 9     char data;10     struct _btree_ *leftTree;11     struct _btree_ *rightTree;12 }BTree;13 14 /*初始化根节点，返回的是根节点地址*/15 BTree*16 initRoot(const char &data)17 {18     BTree *root = (BTree *)malloc(sizeof(BTree));19     root->data =http://www.mamicode.com/ data;20     root->leftTree = nullptr;21     root->rightTree = nullptr;22     return root;23 }24 25 /*打印出所有节点的数据*/26 void27 printOut(BTree *root)28 {29     if (root->leftTree)30     {31         printOut(root->leftTree);32     }33 34     if (root)35         std::cout << root->data << std::endl;36     else37         return;38 39     if (root->rightTree)40     {41         printOut(root->rightTree);42     }43 }44 45 #endif //btree_h

 1 #ifndef _stack_h_ 2 #define _stack_h_ 3  4 #include "iostream" 5 #include "stdlib.h" 6 #include "btree.h" 7  8 #define  minSize 5 9 #define  emptyStack -110 11 #define log(s); std::cout<<s<<std::endl;12 13 typedef struct _stack_14 {15     int capacity;16     int topOfStack;17     BTree* *Array;//注意数组保存的是指向BTree的指针，Array是指向数组的指针18 }stack;19 20 stack *createStack(int maxSize)21 {22     stack *s;23     if (maxSize < minSize)24     {25         log("Stack size is too small");26     }27     s = (stack *)malloc(sizeof(stack));28     s->Array = (BTree **)malloc(sizeof(BTree *) * maxSize);29     s->capacity = maxSize;30     s->topOfStack = emptyStack;/*初始化为空栈*/31     return s;32 }33 34 int isFull(stack *s)/*检测是否为满栈*/35 {36     if (s == nullptr)37     {38         log("the stack has not inital");39         return 1;40     }41     return s->topOfStack == s->capacity;42 }43 44 int isEmpty(stack *s)/*是否为空栈*/45 {46     if (s == nullptr)47     {48         log("the stack has not inital");49         return 1;50     }51     return s->topOfStack == emptyStack;52 }53 54 void push(stack *s, BTree *&data)/*压栈*/ /*此处data是对BTree类型的引用*/55 {56     if (isFull(s))57     {58         log("Full of Stack");59         return;60     }61     ++s->topOfStack;62     s->Array[s->topOfStack] = data;63 }64 65 void pop(stack *s)/*弹出栈*/66 {67     if (isEmpty(s))68     {69         log("Out of Stack");70         return;71     }72     --s->topOfStack;73 }74 75 BTree* top(stack *s)/*访问栈顶元素*/76 {77     if (isEmpty(s))78     {79         std::cout << "Out of Stack,Code is ";80         return nullptr;81     }82     return s->Array[s->topOfStack];83 }84 85 void makeEmpty(stack *&s)/*置空栈*/86 {87     free(s->Array);88     free(s);89     s = nullptr;90 }91 92 #endif /*stack_h*/

 1 #include "btree.h" 2 #include "stack.h" 3 #include "iostream" 4 #include "stdlib.h" 5  6 int isSymbal(const char &c) 7 { 8     if (c == ‘+‘ || c == ‘-‘ || c == ‘/‘ || c == ‘*‘) 9         return 1;10     else11         return 0;12 }13 14 int main(void)15 {16     stack *s = createStack(20);17     BTree *new_b = nullptr;18     char c;19     while (std::cin >> c)20     {21         if (c == ‘=‘)22             break;23         new_b = initRoot(c);24         if (!isSymbal(c))//如果读入的不是符号，将枝叶的地址入栈25             push(s, new_b);26         else//如果读入的是符号27         {28             new_b->rightTree = top(s);//将栈顶的地址赋给右子树，后弹栈，将新栈顶赋给左子树，再弹栈，将新生成的根节点入栈29             pop(s);30             new_b->leftTree = top(s);31             pop(s);32             push(s, new_b);33         }34     }35     printOut(top(s));36     free(new_b);37     makeEmpty(s);38     system("pause");39     return 0;40 }