表达式建树

//用数组实现树
#include<iostream>
#include<ctype.h>
#include<cstring>
#define N 10000
#define optd 1
#define optr 2
using namespace std;
int treeL[N], treeR[N];
class node
{
public:
   int flag;//区分当前节点是操作符还是操作数
   double k;
   char ch;
};

node opt[N];
int nodeN;
char formula[1000];

int buildTree(int ld, int rd)
{
   int i;
   for(i=ld; i<rd; ++i)
     if(!isdigit(formula[i]))
       break;
   if(i>=rd)//最后全部为数字的时候
   {
       ++nodeN;
       opt[nodeN].flag=optd;
       sscanf(formula+ld, "%lf", &opt[nodeN].k);
       treeL[nodeN]=treeR[nodeN]=0;//末端节点没有左右孩子
       return nodeN;//返回当前所建节点编号
   }
   int pAS=-1, pMD=-1;//分别表示加减号， 乘除号所在的位置
   int paren=0;//记录左括弧相对于右括弧出现的数目
   for(i=ld; i<rd; ++i)
   {
      switch(formula[i])
      {
         case '(': ++paren;  break;
         case ')': --paren;  break;

         //最后计算的运算符一定是在括弧的外边，不会包含在括弧里边
         case '+':
         case '-':
                   if(paren==0)   pAS=i;
                   break;
         case '*':
         case '/':
               if(paren==0) pMD=i;
                   break;
      }
   }
   if(pAS<0)  pAS=pMD;
   if(pAS<0) //说明没有找到括弧外边的运算符，则脱掉一对括弧重新寻找
     return buildTree(ld+1, rd-1);
   int u=++nodeN;
   opt[u].flag=optr;//表示存储操作符
   opt[u].ch=formula[pAS];
   treeL[u]=buildTree(ld, pAS);
   treeR[u]=buildTree(pAS+1, rd);
   return u;
}

void printTree(int cur)//中序输出表达式树
{
   if(cur)//非末端节点
   {
      printTree(treeL[cur]);
      if(opt[cur].flag==optd)
        cout<<opt[cur].k<<" ";
      else
        cout<<opt[cur].ch<<" ";
      printTree(treeR[cur]);
   }
} 

int main()
{
   while(cin>>formula)
   {
      buildTree(0, strlen(formula));
      printTree(1);
   }
   return 0;
} 

 //用链表实现树
#include<iostream>
#include<ctype.h>
#include<cstring>
#define N 10000
#define optd 1
#define optr 2
using namespace std;

class node
{
public:
   node *lchild, *rchild;
   int flag;//区分当前节点是操作符还是操作数
   double k;
   char ch;
};

char formula[1000];

void buildTree(node* &T, int ld, int rd)
{
   int i;
   for(i=ld; i<rd; ++i)
     if(!isdigit(formula[i]))
       break;
   if(i>=rd)//最后全部为数字的时候
   {
       T=new node();
       T->flag=optd;
       sscanf(formula+ld, "%lf", &T->k);
       return ;
   }
   int pAS=-1, pMD=-1;//分别表示加减号， 乘除号所在的位置
   int paren=0;//记录左括弧相对于右括弧出现的数目
   for(i=ld; i<rd; ++i)
   {
      switch(formula[i])
      {
         case '(': ++paren;  break;
         case ')': --paren;  break;

         //最后计算的运算符一定是在括弧的外边，不会包含在括弧里边
         case '+':
         case '-':
                   if(paren==0)   pAS=i;
                   break;
         case '*':
         case '/':
               if(paren==0) pMD=i;
                   break;
      }
   }
   if(pAS<0)  pAS=pMD;
   if(pAS<0) //说明没有找到括弧外边的运算符，则脱掉一对括弧重新寻找
     return buildTree(T, ld+1, rd-1);
   T=new node();
   T->flag=optr;//表示存储操作符
   T->ch=formula[pAS];
   buildTree(T->lchild, ld, pAS);
   buildTree(T->rchild, pAS+1, rd);
}

void printTree(node *T)//中序输出表达式树
{
   if(T)//非末端节点
   {
      printTree(T->lchild);
      if(T->flag==optd)
        cout<<T->k<<" ";
      else
        cout<<T->ch<<" ";
      printTree(T->rchild);
   }
} 

int main()
{
   while(cin>>formula)
   {
      node *T=NULL;
      buildTree(T, 0, strlen(formula));
      printTree(T);
   }
   return 0;
}