//用数组实现树
 1 #include<iostream>  2 #include<ctype.h> 3 #include<cstring> 4 #define N 10000 5 #define optd 1 6 #define optr 2 7 using namespace std; 8 int treeL[N], treeR[N]; 9 class node10 {11 public:12    int flag;//区分当前节点是操作符还是操作数 13    double k;14    char ch;15 };16 17 node opt[N];18 int nodeN; 19 char formula[1000];20 21 int buildTree(int ld, int rd)22 {23    int i;24    for(i=ld; i<rd; ++i)25      if(!isdigit(formula[i])) 26        break;27    if(i>=rd)//最后全部为数字的时候 28    {29        ++nodeN;30        opt[nodeN].flag=optd;31        sscanf(formula+ld, "%lf", &opt[nodeN].k);32        treeL[nodeN]=treeR[nodeN]=0;//末端节点没有左右孩子 33        return nodeN;//返回当前所建节点编号 34    }35    int pAS=-1, pMD=-1;//分别表示加减号， 乘除号所在的位置 36    int paren=0;//记录左括弧相对于右括弧出现的数目 37    for(i=ld; i<rd; ++i)38    {39       switch(formula[i])40       {41          case ‘(‘: ++paren;  break;42          case ‘)‘: --paren;  break;43 44          //最后计算的运算符一定是在括弧的外边，不会包含在括弧里边 45          case ‘+‘:46          case ‘-‘: 47                    if(paren==0)   pAS=i;48                    break;49          case ‘*‘:50          case ‘/‘: 51                if(paren==0) pMD=i;52                    break;53       }54    }55    if(pAS<0)  pAS=pMD;56    if(pAS<0) //说明没有找到括弧外边的运算符，则脱掉一对括弧重新寻找 57      return buildTree(ld+1, rd-1);58    int u=++nodeN;59    opt[u].flag=optr;//表示存储操作符60    opt[u].ch=formula[pAS];61    treeL[u]=buildTree(ld, pAS);62    treeR[u]=buildTree(pAS+1, rd);63    return u;64 }65 66 void printTree(int cur)//中序输出表达式树 67 {68    if(cur)//非末端节点 69    {70       printTree(treeL[cur]);71       if(opt[cur].flag==optd)72         cout<<opt[cur].k<<" ";73       else 74         cout<<opt[cur].ch<<" ";75       printTree(treeR[cur]);76    }77 } 78 79 int main()80 {81    while(cin>>formula)82    {83       buildTree(0, strlen(formula));84       printTree(1);85    }86    return 0;87 } 

 //用链表实现树
 1 #include<iostream>  2 #include<ctype.h> 3 #include<cstring> 4 #define N 10000 5 #define optd 1 6 #define optr 2 7 using namespace std; 8  9 class node10 {11 public:12    node *lchild, *rchild;13    int flag;//区分当前节点是操作符还是操作数 14    double k;15    char ch;16 };17 18 char formula[1000];19 20 void buildTree(node* &T, int ld, int rd)21 {22    int i;23    for(i=ld; i<rd; ++i)24      if(!isdigit(formula[i])) 25        break;26    if(i>=rd)//最后全部为数字的时候 27    {28        T=new node();29        T->flag=optd;30        sscanf(formula+ld, "%lf", &T->k);31        return ; 32    }33    int pAS=-1, pMD=-1;//分别表示加减号， 乘除号所在的位置 34    int paren=0;//记录左括弧相对于右括弧出现的数目 35    for(i=ld; i<rd; ++i)36    {37       switch(formula[i])38       {39          case ‘(‘: ++paren;  break;40          case ‘)‘: --paren;  break;41 42          //最后计算的运算符一定是在括弧的外边，不会包含在括弧里边 43          case ‘+‘:44          case ‘-‘: 45                    if(paren==0)   pAS=i;46                    break;47          case ‘*‘:48          case ‘/‘: 49                if(paren==0) pMD=i;50                    break;51       }52    }53    if(pAS<0)  pAS=pMD;54    if(pAS<0) //说明没有找到括弧外边的运算符，则脱掉一对括弧重新寻找 55      return buildTree(T, ld+1, rd-1);56    T=new node();57    T->flag=optr;//表示存储操作符58    T->ch=formula[pAS];59    buildTree(T->lchild, ld, pAS);60    buildTree(T->rchild, pAS+1, rd);61 }62 63 void printTree(node *T)//中序输出表达式树 64 {65    if(T)//非末端节点 66    {67       printTree(T->lchild);68       if(T->flag==optd)69         cout<<T->k<<" ";70       else 71         cout<<T->ch<<" ";72       printTree(T->rchild);73    }74 } 75 76 int main()77 {78    while(cin>>formula)79    {80       node *T=NULL; 81       buildTree(T, 0, strlen(formula));82       printTree(T);83    }84    return 0;85 }