先序表达式恢复成二叉树并计算--For初学者

思路是这样的：首先，将先序表达式转化成二叉树，其次，用后序来遍历二叉树，最后，通过后序遍历二叉树的结果来计算最终结果。
那么问题来了，为什么我们要通过后序表达式来计算最终结果。这是因为后序表达式我们计算过，点击这里，所以，我们先把后序表达式的代码放进.h的文件里。
编辑环境：Code::Blocks，本人能力有限，难免有bug，大致思想是这样的，其他功能读者可以自行增加

//stcck.h
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#define MAX 100
typedef int ElemType;

typedef struct node {
  ElemType date;
 struct node *next;
} StackNode;
void InitStack(StackNode **p) {//栈的声明
    (*p)=NULL;
}

int StackEmpty(StackNode *p) {//如果栈是空的返回0；不空返回1
    if(p==NULL)
        return 0;
    return 1;
}

void Push(StackNode **top, ElemType x) {//入栈操作
   StackNode *p;
   p=(StackNode *)malloc(sizeof(StackNode));
   p->date=x;
   p->next=*top;
   *top=p;
}

void Pop(StackNode **top, ElemType *x) {//出栈操作
    StackNode *p;
    if(*top==NULL)
        printf("Stack is empty!\n");
    else{
        *x=(*top)->date;
        p=*top;
        *top=(*top)->next;
        free(p);
    }

}
int Calc(char *s) {
    StackNode *p;
    InitStack(&p);
     ElemType x1,x2;
    int i=0,x;
    while(s[i])//进行四则运算
    {
        if(s[i]>='0'&&s[i]<='9')
            Push(&p,s[i]-48);
        else{
            Pop(&p,&x1);
            Pop(&p,&x2);
            if(s[i]=='+')
                Push(&p,x1+x2);
            if(s[i]=='-')
                Push(&p,x1-x2);
            if(s[i]=='*')
                Push(&p,x1*x2);
            if(s[i]=='/')
                Push(&p,x1/x2);
        }
        i++;
    }
    return p->date;
}

#endif // STACK_H_INCLUDED

这个代码跟https://blog.****.net/a_52hz/article/details/82858645的代码基本一样，只不过今天主要的目的是回复二叉树，因此，把这个stack打包比较好。
好了，后序表达式的计算问题解决了，其实就是复制粘贴上次的代码，先序表达式恢复成二叉树，用的是递归的方法。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include"stack.h"
char str[MAX] ;
int i = 0;
typedef int DataType;
typedef struct treenode {
  DataType data;
  struct treenode * leftChild;
  struct treenode * rightChild;
}TreeNode;
void PrintBiTree(TreeNode *bt, int n) {
  int i;
  if (bt == NULL) return;
  PrintBiTree(bt->rightChild, n+1);
  for (i = 0; i < n-1; i++) printf("   ");
  if (n > 0) {
    printf("---");
    printf("%c\n", bt->data);
  }
  PrintBiTree(bt->leftChild, n+1);
}
void PrintF(TreeNode *p)//前序遍历
{
    if(p!=NULL)
    {
        printf("%c",p->data);
        PrintF(p->leftChild);
        PrintF(p->rightChild);
    }
}
void PrintM(TreeNode *p)//中序遍历
{
    if(p!=NULL)
    {
        PrintM(p->leftChild);
        printf("%c",p->data);
        PrintM(p->rightChild);
    }
}
void PrintP(TreeNode *p)//后序遍历
{
    if(p!=NULL)
    {
        PrintP(p->leftChild);
        PrintP(p->rightChild);
        printf("%c",p->data);
        str[i++] = p->data;//为后序计算准备
    }
}
void RecoveryTree(TreeNode **p)//回复成二叉树
{
    char ch;
    scanf("%c",&ch);
    if(ch!='$')
    {
        *p = (TreeNode *)malloc(sizeof(TreeNode));//申请新的结点
        (*p)->data = ch;
        RecoveryTree(&(*p)->leftChild);//一直左插，直到遇到$
        RecoveryTree(&(*p)->rightChild);//一直右插，直到遇到$
    }
    else *p = NULL;//$的位置置成NULL
}
int main() {
    TreeNode *p;
    RecoveryTree(&p);
    printf("The tree is:\n");
    PrintBiTree(p,1);
    printf("\n\nThe forward expression is:    ");
    PrintF(p);
    printf("\n\nThe middle expression is:    ");
    PrintM(p);
    printf("\n\nThe following expression is:    ");
    PrintP(p);
    printf("\n\nThe result is:  %d", Calc(str));
    return 0;
}

其实核心代码就那么几行（主要靠递归）。
运行结果：