数据结构-表达式求值

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 #define STACK_INIT_SIZE 100
  6 #define STACKINCREMENT 10
  7 #define OVERFLOW -2
  8 #define OK 1
  9 #define ERROR 0
 10 
 11 typedef char SElemType;
 12 typedef int ElemType;
 13 
 14 //栈结构体
 15 typedef struct {
 16     SElemType *base;
 17     SElemType *top;
 18     int stacksize;
 19 }SqStackOptr;//运算符栈
 20 
 21 typedef struct {
 22     ElemType *base;
 23     ElemType *top;
 24     int stacksize;
 25 }SqStackOpnd;//运算数栈
 26 
 27 //运算符栈
 28 int InitStackOptr(SqStackOptr *S);//初始化栈
 29 SElemType GetTopOptr(SqStackOptr *S);//取得栈顶元素
 30 int PushOptr(SqStackOptr *S,SElemType e);//入栈
 31 int PopOptr(SqStackOptr *S,SElemType *e);//删除栈中的元素
 32 int DestoryStackOptr(SqStackOptr *S);//销毁栈
 33 //运算数栈
 34 int InitStackOpnd(SqStackOpnd *S);//初始化栈
 35 ElemType GetTopOpnd(SqStackOpnd *S);//取得栈顶元素
 36 int PushOpnd(SqStackOpnd *S,SElemType e);//入栈
 37 int PopOpnd(SqStackOpnd *S,SElemType *e);//删除栈中的元素
 38 int DestoryStackOpnd(SqStackOpnd *S);//销毁栈
 39 //表达式求值
 40 ElemType EvaluateExpression(SqStackOptr *OPTR,SqStackOpnd *OPND);//输入表达式并计算表达式的值
 41 SElemType Precede(char topc,char c);//判断运算符优先级
 42 ElemType Operate(SElemType a,SElemType theta,SElemType b);//计算部分表达式的值              
 43 ElemType In(char c,char op[]);//判断输入的字符是不是运算符
 44 
 45 //初始化栈
 46 int InitStackOptr(SqStackOptr *S) {
 47     S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 48     if(!S->base) {
 49         exit(OVERFLOW);
 50     }
 51     S->top = S->base;
 52     S->stacksize = STACK_INIT_SIZE;
 53     return OK;
 54 }
 55 
 56 int InitStackOpnd(SqStackOpnd *S) {
 57     S->base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
 58     if(!S->base) {
 59         exit(OVERFLOW);
 60     }
 61     S->top = S->base;
 62     S->stacksize = STACK_INIT_SIZE;
 63     return OK;
 64 }
 65 
 66 //取得栈顶元素
 67 SElemType GetTopOptr(SqStackOptr *S) {
 68     if(S->top == S->base) {
 69         return ERROR;
 70     }
 71     return *(S->top-1);
 72 }
 73 ElemType GetTopOpnd(SqStackOpnd *S) {
 74     if(S->top == S->base) {
 75         return ERROR;
 76     }
 77     return *(S->top-1);
 78 }
 79 
 80 //入栈
 81 int PushOptr(SqStackOptr *S,SElemType e) {
 82     if((S->top-S->base)>=S->stacksize) {
 83         S->base = (SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
 84         if(!S->base) exit(OVERFLOW);
 85         S->top = S->base + S->stacksize;
 86         S->stacksize += STACKINCREMENT;
 87     }
 88     *S->top++ = e;
 89     return OK;
 90 }
 91 int PushOpnd(SqStackOpnd *S,ElemType e) {
 92     if((S->top-S->base)>=S->stacksize) {
 93         S->base = (ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
 94         if(!S->base) exit(OVERFLOW);
 95         S->top = S->base + S->stacksize;
 96         S->stacksize += STACKINCREMENT;
 97     }
 98     *S->top++ = e;
 99     return OK;
100 }
101 
102 //删除栈中的元素
103 int PopOptr(SqStackOptr *S,SElemType *e) {
104     if(S->top  == S->base) return ERROR;
105     *e = *--S->top;
106     return OK;
107 }
108 int PopOpnd(SqStackOpnd *S,ElemType *e) {
109     if(S->top  == S->base) return ERROR;
110     *e = *--S->top;
111     return OK;
112 }
113 
114 //销毁栈
115 int DestoryStackOptr(SqStackOptr *S) {
116     S->top = S->base;
117     free(S->base);
118     S->top = NULL;
119     S->base = NULL;
120     return OK;
121 }
122 int DestoryStackOpnd(SqStackOpnd *S) {
123     S->top = S->base;
124     free(S->base);
125     S->top = NULL;
126     S->base = NULL;
127     return OK;
128 }
129 //判断输入的字符是不是运算符
130 ElemType In(char c,char op[]) {
131     int i,f=0;
132     for(i=0; i<7; i++) {
133         if(c == op[i]) {
134             f = 1;
135             break;
136         }
137     }
138     if(f==0) return 0;
139     else return 1;
140 }
141 //比较运算符优先级
142 SElemType Precede(char topc,char c) {
143     if (topc==‘+‘||topc==‘-‘) {
144         if(c==‘+‘||c==‘-‘||c==‘)‘||c==‘#‘) {
145             return ‘>‘;
146         } else {
147             return ‘<‘;
148         }
149     }
150     
151     if (topc==‘*‘||topc==‘/‘) {
152         if(c==‘(‘) {
153             return ‘<‘;
154         } else {
155             return ‘>‘;
156         }
157     }
158 
159     if (topc==‘(‘) {
160         if(c==‘)‘) {
161             return ‘=‘;
162         } else {
163             return ‘<‘;
164         }
165     }
166 
167     if (topc==‘)‘) {
168         return ‘)‘;
169     }
170 
171     if (topc==‘#‘) {
172         if(c==‘#‘) {
173             return ‘=‘;
174         } else {
175             return ‘<‘;
176         }
177     }
178 
179 }
180 
181 ElemType Operate(ElemType a,SElemType theta,ElemType b) {
182      switch(theta) {
183      case ‘+‘:
184          return a+b;
185          break;
186      case ‘-‘:
187          return a-b;
188          break;
189      case ‘*‘:
190          return a*b;
191          break;
192      case ‘/‘:
193          return a/b;
194          break;
195      }
196  }
197 //求表达式的值
198 ElemType EvaluateExpression(SqStackOptr *OPTR,SqStackOpnd *OPND) {
199     //算数表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合
200     SElemType c,theta,x;
201     ElemType a,b;
202     SElemType op[7] = {‘+‘,‘-‘,‘*‘,‘/‘,‘(‘,‘)‘,‘#‘};
203     InitStackOptr(OPTR);
204     InitStackOpnd(OPND);
205     PushOptr(OPTR,‘#‘);
206     printf("请输入表达式：");
207     c = getchar();
208     while(c!=‘#‘|| GetTopOptr(OPTR)!=‘#‘) {
209         if(!In(c,op)) {
210             PushOpnd(OPND,c-‘0‘);
211             c = getchar();
212         } else {
213             switch(Precede(GetTopOptr(OPTR),c)) {
214             case ‘<‘://栈顶元素优先级低
215                 PushOptr(OPTR,c);
216                 c = getchar();
217                 break;
218             case ‘>‘://栈顶元素优先级高
219                 PopOptr(OPTR,&theta);                
220                 PopOpnd(OPND,&b);
221                 PopOpnd(OPND,&a);
222                 PushOpnd(OPND,Operate(a,theta,b));
223                 break;
224             case ‘=‘:
225                 PopOptr(OPTR,&x);
226                 c = getchar();
227                 break;
228             }
229         }
230     }
231     return GetTopOpnd(OPND);
232 }
233 int main()
234 {
235     SqStackOpnd OPND;
236     SqStackOptr OPTR;
237     int result;
238     result = EvaluateExpression(&OPTR,&OPND);
239     printf("表达式的结果为：%d",result);
240     system("pause");
241     return 0;
242 }