rpn.zip_rpn_表达式树c++

#include<stdlib.h> #include<stdio.h> #include<conio.h> #include <windows.h> #include <math.h> #include <string> using namespace std; #define MAX 100 char RPN[MAX]; void TransToRPN( ); void CalculateRPN(); void painttree(); void towards(char *tmpa,int pos,int a); char str[MAX]; char stack[MAX]; float stackre[MAX]; char tmp[MAX]; int rpnc=0; int ti=0; int ni=5; int nia=5; typedef struct sstack { char str[MAX]; int top; }mystack; typedef struct BiTNode { string data; int numflag; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void myfree(BiTree ); BiTree creatbt(string a,BiTree le,BiTree ri,int flag); void DispTree(BiTree ,int ,int ,int ) ; BiTree root=NULL; int main() { while (1) { printf("\n***************************************************************\n"); printf( "**** 中缀表达式转后缀表达式 、求值、画表达式树 ****\n"); printf( "**** 输入中缀表达式后以';'结束，如1+2; ****\n"); printf( "**** 08007234 戈润栋 ****\n"); printf("\n***************************************************************\n"); int i=0; printf("中缀表达式:"); do { scanf("%c",&str[i]); i++; } while (i!=MAX&&str[i-1]!=';'); TransToRPN(); CalculateRPN(); painttree(); printf("后缀表达式:"); printf(RPN); printf(" 计算结果: "); printf("%f\n",stackre[0]); DispTree(root,30,12,3); myfree(root); getch(); system("cls"); printf("释放内存"); getch(); system("cls"); } return 0; } void TransToRPN() { char ch; int sum,top,t,j; top=-1; //sum=i; t=0; j=0; ch=str[j]; while (ch!=';') { switch (ch) { case '(': top++; stack[top]=ch; break; case ')': while (stack[top]!='(') { RPN[t]=stack[top]; top--; t++; } top--; break; case '+': case '-': if (top!=-1&&stack[top]!='(') { RPN[t]=stack[top]; t++; top--; } top++; stack[top]=ch; break; case '*': case '/': if (stack[top]=='*'||stack[top]=='/') { RPN[t]=stack[top]; t++; stack[top]=ch; } else { top++; stack[top]=ch; } break; case ' ': break; default: while (ch>='0'&&ch<='9') { RPN[t]=ch; t++; j++; ch=str[j]; } RPN[t]=' '; t++; j--; } j++; ch=str[j]; } while(top!=-1) { RPN[t]=stack[top]; t++; top--; } rpnc=t; } void CalculateRPN() { int top=-1,t=0,iter=0; int num=0; char ch; ch=RPN[t]; for(iter=0;iter<rpnc;iter++) { switch (ch) { case '+': stackre[top-1]+=stackre[top]; top--; break; case '-': stackre[top-1]-=stackre[top]; top--; break; case '*': stackre[top-1]*=stackre[top]; top--; break; case '/': stackre[top-1]/=stackre[top]; top--; break; default: while (ch>='0'&&ch<='9') { num=num*10+ch-'0'; t++; ch=RPN[t]; } top++; stackre[top]=num; num=0; } t++; ch=RPN[t]; } } void towards(char *tmpa,int pos,int a) { char tmpb; int iter=0; int npos; npos=pos; tmpb=*(tmpa+pos); for (iter=0;iter<a;iter++) { *(tmpa+pos)=*(tmpa+pos-1); pos--; } *(tmpa+npos-a)=tmpb; } void painttree() { root=NULL; BiTree stackb[MAX]; BiTree renode; int num=0; int t=0; int iter=0; int top=-1; int ss; char temp[64]; char ch; string ww; for(iter=0;iter<rpnc;iter++) { tmp[iter]=RPN[iter]; } tmp[iter]=';'; iter=0; ch=tmp[iter]; for(iter=0;iter<rpnc;iter++) { switch (ch) { case '+': case '-': case '*': case '/': renode = new BiTNode; renode->data=ch; renode->rchild=stackb[top]; top--; renode->lchild=stackb[top]; stackb[top]=renode; break; default: top++; while (ch>='0'&&ch<='9') { num=num*10+ch-'0'; t++; ch=tmp[t]; } sprintf(temp, "%d", num); renode = new BiTNode; renode->data=temp; renode->rchild=NULL; renode->lchild=NULL; stackb[top]=renode; num=0; } t++; ch=tmp[t]; } root=stackb[0]; } void DispTree(BiTree root,int x,int y,int n) { COORD coord; HANDLE hStdout; hStdout = GetStdHandle(STD_OUTPUT_HANDLE); int i=0; if(root !=NULL) { coord.X = x; coord.Y = y; SetConsoleCursorPosition(hStdout, coord); printf("%s",root->data.c_str()); if(root->lchild != NULL) { DispTree(root->lchild,x-n,y+n,2); ni--; } if(root->rchild != NULL) { DispTree(root->rchild,x+n,y+n,2); } } } BiTree creatbt(string a,BiTree le,BiTree ri,int flag) { BiTree newbtree; newbtree->data=a; newbtree->lchild=le; newbtree->rchild=ri; newbtree->numflag=flag; return newbtree; } void myfree(BiTree p) { if (p->lchild==NULL&&p->rchild==NULL) { ti++; delete(p); } else{ if (p->lchild!=NULL) myfree(p->lchild); if (p->rchild!=NULL) myfree(p->rchild); delete(p); } }