四则运算表达式

问题描述
四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 #include<string>
  5 #include<sstream>
  6 #include<fstream>
  7 #include<iostream>
  8 #define TRUE 1
  9 #define FALSE 0
 10 #define MAXNUM 1000
 11 using namespace std;
 12 string str1;
 13 typedef int DataType;
 14 
 15 
 16 
 17 struct BinTreeNode;
 18 typedef struct BinTreeNode*PBinTreeNode;
 19 struct BinTreeNode
 20 {
 21     DataType data;
 22     PBinTreeNode left;
 23     PBinTreeNode right;
 24 };
 25 typedef struct BinTreeNode*BinTree;
 26 //typedef BinTree*PBinTree;
 27 
 28 int toTree(BinTree* btree,const char *exp,int len)
 29 {
 30 
 31     char c;
 32     int last,i,bracket;
 33     bool have_bracket=FALSE;
 34     int num,isnum,nint;
 35     int tag1,tag2;
 36 
 37 
 38     if(exp[0]=='('&&exp[len-1]==')')
 39         return toTree(btree,exp+1,len-2);
 40 
 41     bracket=0;
 42     last=len;
 43     for(i=len-1;i>=0;i--)
 44         {
 45             c=exp[i];
 46             if(c==')')
 47                 {
 48                     have_bracket=TRUE;
 49                     bracket++;
 50                 }
 51             if(c=='(') bracket--;
 52             if(bracket<0)
 53                 {
 54                     *btree=NULL;
 55                     return FALSE;
 56                 }
 57             if(bracket>0) continue;
 58             if(c=='+'||c=='-')
 59                 if(last==len||exp[last]=='*'||exp[last]=='/')
 60                     last=i;
 61             if(c=='*'||c=='/')
 62                 if(last==len)
 63                     last=i;
 64         }
 65       //  printf("last   %d
",last);
 66     if(bracket!=0) return FALSE;
 67 
 68     if(last==len)
 69         {
 70             if(have_bracket==TRUE)
 71                 {
 72                     *btree=NULL;
 73                     return FALSE;
 74                 }
 75             nint=0;
 76             isnum=FALSE;
 77             num=0;
 78             for(i=0;i<len;i++)
 79                 {
 80                     c=exp[i];
 81                     switch(c)
 82                         {
 83                             case'0':case'1':case'2':case'3':case'4':
 84                             case'5':case'6':case'7':case'8':case'9':
 85                                 if(isnum==FALSE)
 86                                     {
 87                                         num=c-'0';
 88                                         isnum=TRUE;
 89                                         nint++;
 90                                     }
 91                                 else
 92                                     {
 93                                         num=num*10+c-'0';
 94                                     }
 95                                 break;
 96                             case' ':case'	':case'
':
 97                                 isnum=FALSE;
 98                                 break;
 99                             default:
100                                 *btree=NULL;
101                                 return FALSE;
102                         }
103                 }
104             if(nint!=1)
105                 {
106                     *btree=NULL;
107                     return FALSE;
108                 }
109             *btree=(BinTree)malloc(sizeof(struct BinTreeNode));
110             (*btree)->data=num;
111             (*btree)->left=NULL;
112             (*btree)->right=NULL;
113             return TRUE;
114         }
115     *btree=(BinTree)malloc(sizeof(struct BinTreeNode));
116     (*btree)->data=exp[last];
117 
118     tag1 =toTree(&(*btree)->left,exp,last);
119     tag2 =toTree(&(*btree)->right,exp+last+1,len-last-1);
120     if(tag1==TRUE&&tag2==TRUE)  return TRUE;
121     return FALSE;
122 }
123 
124 int cal(BinTree btree,int*result)
125     {
126 
127         int result1,result2;
128         if(btree==NULL)     return FALSE;
129         if(btree->left==NULL&&btree->right==NULL)
130             {
131                 *result=btree->data;
132                 return TRUE;
133             }
134         if(btree->left==NULL||btree->right==NULL)
135             return FALSE;
136 
137         switch(btree->data)
138             {
139 
140 
141                 case'+':
142                     //cout<<"+"<<endl;
143                     if(cal(btree->left,&result1)==FALSE) return FALSE;
144                     if(cal(btree->right,&result2)==FALSE) return FALSE;
145                     *result=result1+result2;
146                     return TRUE;
147                 case'-':
148                     //cout<<"-"<<endl;
149                     if(cal(btree->left,&result1)==FALSE) return FALSE;
150                     if(cal(btree->right,&result2)==FALSE) return FALSE;
151                     *result=result1-result2;
152                     return TRUE;
153                 case'*':
154                     //cout<<"*"<<endl;
155                     if(cal(btree->left,&result1)==FALSE) return FALSE;
156                     if(cal(btree->right,&result2)==FALSE) return FALSE;
157                     *result=result1*result2;
158                     return TRUE;
159 
160                 case'/':
161                     //cout<<"/"<<endl;
162                     if(cal(btree->left,&result1)==FALSE) return FALSE;
163                     if(cal(btree->right,&result2)==FALSE) return FALSE;
164                     *result=result1/result2;
165                     return TRUE;
166                 default:
167                     return FALSE;
168             }
169     }
170 
171 void lastOrder(BinTreeNode *btree){
172 
173 
174     if(btree){
175 
176         lastOrder(btree->left);
177         lastOrder(btree->right);
178         if((btree->data=='+')&&(btree->left!=NULL)&&(btree->right!=NULL))
179            {cout<<'+';str1+='+';}
180         else if((btree->data=='-')&&(btree->left!=NULL)&&(btree->right!=NULL))
181             {cout<<'-';str1+='-';}
182         else if((btree->data=='*')&&(btree->left!=NULL)&&(btree->right!=NULL))
183             {cout<<'*';str1+='*';}
184         else if((btree->data=='/')&&(btree->left!=NULL)&&(btree->right!=NULL))
185             {cout<<'/';str1+='/';}
186         else
187             {cout<<btree->data<<" ";stringstream ch;ch<<btree->data;string tem;ch>>tem;str1+=tem;str1+=' ';}
188 
189     }
190    // in.close();
191 }
192 
193 int main()
194 {
195     char c,exp[MAXNUM];
196     int result;
197     BinTree btree;
198    // printf("Please input the expression:");
199     fstream in;
200     in.open("exp");
201     cout<<"从文件中读取中缀表达式"<<endl;
202     string str;
203     getline(in,str);
204     strcpy(exp,str.c_str());
205     if(toTree(&btree,exp,strlen(exp))==FALSE)
206     {
207         in<<"Wrong input!
";
208 
209 
210 
211 
212     }
213     else{
214     lastOrder(btree);
215     cout<<endl;
216    // cout<<str1<<endl;
217     in<<"---"<<str1<<endl;
218     if(cal(btree,&result)==TRUE)  in<<result<<endl;
219     else in<<"Wrong input!
";
220 
221 
222     cout<<result<<endl;
223     }
224     in.close();
225 
226 }
View Code