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

来源:网络时间:2012-04-05

  昨天晚上,我花了大把的时间研究里面二叉树应用解决计算表达式的问题,一直就没理解,主要是觉得是不是自己错了,又懒,不愿意自己把代码敲到电脑里看看,结果浪费了很多时间。所以还是提醒大家,代码这种东西,有什么好多看的,觉得他错了就自己敲到电脑里去看看!其实也没错太多,就是少了一些东西,导致原代码里的括号完全没有意义,也就是说,书中的代码虽然考虑到了计算表达式中的括号,却什么都没有做,而这其实只要稍稍改进:加一个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;

  }

发表评论

最新评论(共3条)

2345市网友

都设么玩意啊

2013-07-09 0

回复@2345网友:

  • 取消

2345市网友

这个是计算器的程序!

2013-04-29 0

回复@2345网友:

  • 取消

2345市网友

顶,我写到现在还没有成功……

2012-05-02 0

回复@2345网友:

  • 取消