C++二叉树应用：计算表达式

　　昨天晚上，我花了大把的 工夫探究里面二叉树 利用解 信念算 抒发式的问题，向来就没 了解，重要是感觉是否自己错了，又懒，不情愿自己把代码敲到电脑里看看， 后果 浪费了众多 工夫 。所以还是 揭示大家，代码这种东西，有什么好多看的，感觉他错了就自己敲到电脑里去看看！其实也没错太多，便是少了一些东西，招致原代码里的括号 彻底没有 意思，也便是说，书中的代码 固然考量到了计算 抒发式中的括号，却什么都没有做，而这其实 惟独稍稍改良：加一个flag存储上次读到的char，假如是‘)’的话，就要把左式当成运算数来计算 。

　　好了，把正确的代码贴在下面：

　　#include <iostream>

　　using namespace std;

　　class calc

　　{

　　enum Type {DATA, ADD, SUB, MULTI, DIV, OPAREN, CPAREN, EOL};

　　struct node

　　{

　　Type type;

　　int data;

　　node *lchild, *rchild;

　　node(Type t, int d=0, node *lc=NULL, node *rc=NULL)

　　{

　　type=t; data=d; lchild=lc; rchild=rc;

　　}

　　};

　　node *root;

　　node *create(char * &s);

　　Type getToken (char * &s, int &value);

　　int result (node *t);

　　public:

　　calc (char *s) {root=create(s);}

　　int result() {if (root==NULL) return 0;

　　return result(root);}

　　};

　　calc::node *calc::create(char * &s)

　　{

　　node *p, *root=NULL;

　　Type returnType,flag=DATA;

　　int value;

　　while (*s)

　　{

　　flag=returnType;

　　returnType=getToken(s,value);

　　switch (returnType)

　　{

　　case DATA:

　　case OPAREN:

　　if (returnType == DATA) p=new node(DATA,value);

　　else p=create(s);

　　if (root==NULL) root=p;

　　else if (root->rchild==NULL) root->rchild=p;

　　else root->rchild->rchild=p;

　　break;

　　case CPAREN:

　　case EOL: return root;

　　case ADD:

　　case SUB:

　　root=new node(returnType,0,root);

　　break;

　　case MULTI:

　　case DIV:

　　if (root->type==DATA || root->type==MULTI || root->type==DIV || flag==OPAREN)

　　root=new node(returnType,0,root);

　　else root->rchild=new node(returnType,0,root->rchild);

　　}

　　}

　　return root;

　　}

　　calc::Type calc::getToken(char *&s, int &data)

　　{

　　char type;

　　while (*s==' ') ++s;

　　if (*s>='0' && *s<='9')

　　{

　　data=0;

　　while (*s>='0' && *s<='9') {data=data*10+ *s-'0'; ++s;}

　　return DATA;

　　}

　　if (*s == '\0') return EOL;

　　type =*s; ++s;

　　switch(type)

　　{

　　case '+':return ADD;

　　case '-':return SUB;

　　case '*':return MULTI;

　　case '/':return DIV;

　　case '(':return OPAREN;

　　case ')':return CPAREN;

　　default: return EOL;

　　}

　　}

　　int calc::result(node *t)

　　{

　　int num1,num2;

　　if (t->type == DATA) return t->data;

　　num1=result(t->lchild);

　　num2=result(t->rchild);

　　switch(t->type)

　　{

　　case ADD:t->data=num1+num2;break;

　　case SUB:t->data=num1-num2;break;

　　case MULTI: t->data=num1*num2;break;

　　case DIV:t->data=num1/num2;break;

　　}

　　return t->data;

　　}

　　int main()

　　{

　　char equation[256];

　　cin>>equation;

　　//calc exp("3*(2+(6/2))");

　　calc exp(equation);

　　cout<<exp.result()<<endl;

　　return 0;

　　}