《数据结构实验三后缀表达式的计算》由会员分享，可在线阅读，更多相关《数据结构实验三后缀表达式的计算（4页珍藏版）》请在金锄头文库上搜索。
1、实验三 后缀表达式的计算实验目的： 熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的 数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。实验内容与要求： 按常规形式输入算术表达式（例如：输入2*（6-4）+8/4），要求能够：（1）生成表达式的后缀表示，并输出；（2）生成表达式的前缀表示，并输出；（3）基于表达式的后缀表示，对该表达式求值；（4）编写一个主程序对表达式求值函数进行测试。算法设计：#include #include #include #define ERROR 0 #define OK 1 #define N 50#define STACK_
2、INT_SIZE 10/存储空间初始分配量#define Queue_Size 20typedef int ElemType;/定义元素的类型typedef structchar QdataQueue_Size; int front,rear;SeqQueue; typedef struct ElemType *base;ElemType *top;int stacksize;/当前已分配的存储空间SqStack; SqStack OPTR, OPND; SeqQueue SeQ; char PreTab77=, , , , ,x, ,front=0;Q-rear=0;int EnterQue
3、ue(SeqQueue *Q,char c)/入队if (Q-rear=Queue_Size)printf(n队列满，无法入队！ n); return ERROR;Q-QdataQ-rear=c;Q-rear+;return OK;int OutQueue(SeqQueue *Q,char *e)/出队if(Q-front=Q-rear)printf(n队列空，无法出队！ n);return ERROR;*e=Q-QdataQ-front+; return OK;int InitStack(SqStack *S)S-base=(ElemType*)malloc(STACK_INT_SIZE *
4、sizeof(ElemType);if(!S-base) return ERROR; S-top=S-base; S-stacksize=STACK_INT_SIZE; return OK;int Push(SqStack *S,ElemType e)if (S-top-S-base)STACK_INT_SIZE) return 0;*S-top=e;S-top+;return OK;int Pop(SqStack *S)int e;if (S-top=S-base) return 0;S-top-;e=*S-top;return *S-top;/判定 c 是否运算符，若是运算符则返回改运算符
5、在运算符集中的位置 int IsOps(char c)int i=0;char *p;p=OpretorS;while(i=0；)if(si=48&si=f(stacktop)top+；stacktop=si；break；elsepj=stacktop；top-；j+；if(si=()/假如是开括号，栈中运算符逐个出栈并输出，直到遇到 闭括号。闭括号出栈并丢弃。while(stacktop!=)pj=stacktop；top-；j+；top-；i-；while(top!=0)/假如输入完毕栈中剩余的所有操作符出栈并加到输入中pj=stacktop；j+；top-；pj=0；printf(n前缀
6、表达式为:);for(；j=0；j-)printf(%c,pj); printf(n);int main()char *ScanChar;char c1,c;char TheOp;int b,a,digit;InitStack(&OPTR);Push(&OPTR,#);InitStack(&OPND); initQueue(&SeQ);ScanChar=Express; c=*ScanChar;while(c!=#|*OPTR.top!=#)if (c=0) c=#;if (IsOps(c)=7)/判定是否是运算符，若 IsOps 的值=7，则 c 是操作数digit=c-0; /将字符转换
7、成相应的数值Push(&OPND,digit); /操作数入栈EnterQueue (&SeQ,c);操作数入队c=*+ScanChar; elsecl=*(OPTR.top-l);switch(Precede(cl,c)调用哪个函数1casev:Push(&OPTR,c);printf(其结果为：dn,Pop(&OPND);输出表达式的值return 0;实验结果：c=*+ScanChar;break;case=:TheOp=Pop(&OPTR);if(c!=0&c!=#)c=*+ScanChar;break;脱括号case:TheOp=Pop (&OPTR );参与计算的运算符出栈EnterQueue (&SeQ,TheOp);参与运算的运算符入队b=Pop(&OPND);a=Pop(&OPND);Push(&OPND,Operate(a,TheOp,b);break;default:printf(n 算术表 达式错误！ n);return ERROR;printf(算术表达式为：%s n后缀表达 式为：”,Express);while(SeQ.rear-SeQ.front!=0) 将队 列输出即为表达式的后缀形式OutQueue (&SeQ，&c); printf(%c,c);convert(Express);
