算术表达式求值数据结构代码

1、#include <iostream>#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_SIZE 100#define STACKINCREMENT 10#define OPSIZE 7typedef double ElemType;typedef char SElemType;char

2、 opOPSIZE='+','-','*','/','(',')','#'char priorOPSIZEOPSIZE='>','>','<','<','<','>','>','>','>','<','<','<','

3、;>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','

4、;<','=',' ','>','>','>','>',' ','>','>','<','<','<','<','<',' ','='typedef struct ElemType *top; ElemType *base; int Stacksize;OPND;

5、typedef struct SElemType *top; SElemType *base; int Stacksize;OPTR;void InitStack(OPND *S1) S1->base=(ElemType *)malloc(STACK_SIZE * sizeof(ElemType); if(NULL=S1->base) printf("Init Failed!n"); exit (OVERFLOW); else S1->top=S1->base; S1->Stacksize=STACK_SIZE; int StackEmpty(

6、OPND *S1) if(S1->top=S1->base) return 1; else return 0;int StackEmpty(OPTR *S2) if(S2->top=S2->base) return 1; else return 0;void InitStack(OPTR *S2) S2->base=(SElemType *)malloc(STACK_SIZE*sizeof(SElemType); if(NULL=S2->base) printf("Init Failed!n"); exit (OVERFLOW); els

7、e S2->top=S2->base; S2->Stacksize=STACK_SIZE; void Push(OPND *S1,ElemType e) if(S1->top-S1->base>=S1->Stacksize) S1->base=(ElemType *)realloc(S1->base,(S1->Stacksize+STACKINCREMENT)*sizeof(ElemType); if(!S1->base) exit(OVERFLOW); S1->top=S1->base+S1->Stacksi

8、ze; S1->Stacksize=S1->Stacksize+STACKINCREMENT; *S1->top=e; S1->top+;void Push(OPTR *S2,SElemType e) if(S2->top-S2->base>=S2->Stacksize) S2->base=(SElemType *)realloc(S2->base,(S2->Stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S2->base) exit (OVERFLOW); S2->

9、top=S2->base+S2->Stacksize; S2->Stacksize+=STACKINCREMENT; *S2->top+=e;ElemType Pop(OPND *S1,ElemType *e) if(!StackEmpty(S1) S1->top=S1->top-1; *e=*S1->top; else return ERROR; return OK;SElemType Pop(OPTR *S2,SElemType *e) if(StackEmpty(S2) return ERROR; else *e=*-S2->top; re

10、turn OK;ElemType GetTop(OPND *S1,ElemType *e) if(!StackEmpty(S1) *e=*(S1->top-1); return OK;SElemType GetTop(OPTR *S2,SElemType *e) if(!StackEmpty(S2) *e=*(S2->top-1); return OK;bool Judege(char c,char *op)/判断C是否为运算符 bool check=false; int i; for(i=0;i<OPSIZE;i+) if(c=opi) check = true; retu

11、rn check;int ReturnOpOrd(char c,char *op)/返回运算符c在OP中的位置 int i; for(i=0;i<OPSIZE;i+) if(c=opi) return i; return OK;char Precede(char theat1,char theat2)/g判断运算符栈的栈顶运算符theta1和读入的运算符theta2优先关系 return priorReturnOpOrd(theat1,op)ReturnOpOrd(theat2,op);double Operate(ElemType a,SElemType theat,ElemType

12、b)/操作数进行运算 switch(theat) case '+': return a+b; break; case '-': return a-b; break; case '*': return a*b; break; case '/': if(b!=0) return a/b; else printf("出错！除数为0！n"); return ERROR; break; default: return 0; float EvaluateExpression(char *expression) OPND S

13、1; OPTR S2; char *c=expression; ElemType e1,e2,result,d; char temp10,r2; SElemType e; InitStack(&S1); InitStack(&S2); Push(&S2,'#'); strcpy(temp,"0"); while(*c!='#'|(GetTop(&S2,&e),e)!='#') if(!Judege(*c,op) r0=*c; r1='0' strcat(temp,r);

14、c+; if(Judege(*c,op) d=(float)atof(temp); Push(&S1,d); strcpy(temp,"0"); else switch(Precede( (GetTop(&S2,&e),e),*c) case '<': Push(&S2,*c); c+; break; case '=': Pop(&S2,&e); c+; break; case '>': Pop(&S1,&e1); Pop(&S1,&e2); Pop(&S2,&e); result=Operate(e2,e,e1); Push(&S1,result); bre