数据结构实验三后缀表达式的计算

1、实验三 后缀表达式的计算实验目的： 熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。实验内容与要求： 按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： （1）生成表达式的后缀表示，并输出；（2）生成表达式的前缀表示，并输出； （3）基于表达式的后缀表示，对该表达式求值； （4）编写一个主程序对表达式求值函数进行测试。算法设计：#include<stdio.h>#include<malloc.h>#include<string.h>#define E

2、RROR 0#define OK 1#define N 50#define STACK_INT_SIZE 10 /存储空间初始分配量#define Queue_Size 20typedef int ElemType; /定义元素的类型typedef structchar QdataQueue_Size; int front,rear;SeqQueue;typedef structElemType *base; ElemType *top; int stacksize; /当前已分配的存储空间SqStack;SqStack OPTR, OPND;SeqQueue SeQ;char PreTab7

3、7='>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>&#

4、39;,'>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','x', '>','>','>','>','x',&#

5、39;>','>', '<','<','<','<','<','x','=' /该矩阵中，X字符表示不存在优先关系，在分析过程查找到这个值，表示表达式有错。char *OpretorS="+-*/()#" /运算符集char *Express="2*(6-4)+8/4" /初始化的表达式int InitStack(SqStack *S); /构造空栈int push(SqStac

6、k *S,ElemType *e); /入栈int Pop(SqStack *S); /出栈void initQueue(SeqQueue *Q) /队列初始化Q->front=0; Q->rear=0;int EnterQueue(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

7、) /出队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 *sizeof(ElemType); if(!S->base) return ERROR; S->top=S->base; S->stacksize=STACK_INT_SIZE; return OK;i

8、nt 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是否运算符，若是运算符则返回改运算符在运算符集中的位置int IsOps(char c)int i=0; char *p; p=Opre

9、torS; while(i<7) if (*p+=c) break; i+; return i;char Precede(char c1,char c2) /返回c1与c2运算符的优先关系 int i,j; i=IsOps(c1); j=IsOps(c2); if ( PreTabij='x') return 0; return PreTabij;int Operate(int a,char TheOp,int b) /进行TheOp计算 switch(TheOp) case'+':return a+b; case'-':return a-

10、b; case'*':return a*b; case'/':return a/b; return 0;int f(char c) /判断运算符级别函数int f=-1; switch(c) case'+': case'-':f=1;break; case'*': case'/':f=2;break; default:f=0;break; return f;int Operator(char c) /判断字符是否为操作符if(c='+'|c='-'|c='*&

11、#39;|c='/') return 1; else return 0;void convert(char sN) /将中缀表达式转化为前缀表达式char pN,stackN; int top=0,j=0, len=0; if(s0=')') printf("算术表达式错误！"); printf("n"); else while(slen!='0') len+; for(int i=len-1;i>=0;) if(si>=48&&si<=57) pj=si; j+; if(

12、si=')') /假如是回括号，将它压栈。 top+; stacktop=si; while(Operator(si) if(top=0|stacktop=')'|f(si)>=f(stacktop) top+; stacktop=si;break; else pj=stacktop; top-;j+; if(si='(') /假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 while(stacktop!=')') pj=stacktop; top-;j+; top-; i-; while(top

13、!=0) /假如输入完毕，栈中剩余的所有操作符出栈并加到输入中 pj=stacktop; j+; top-; pj='0' printf("n前缀表达式为: "); 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(&OP

14、ND); initQueue(&SeQ); ScanChar=Express; c=*ScanChar; while(c!='#'|*OPTR.top!='#') if (c=0) c='#' if (IsOps(c)>=7) /判定是否是运算符，若IsOps的值>=7，则c是操作数 digit=c-'0' /将字符转换成相应的数值 Push(&OPND,digit); /操作数入栈 EnterQueue(&SeQ,c); /操作数入队 c=*+ScanChar; else c1=*(OPTR.

15、top-1); switch(Precede(c1,c) /调用哪个函数 case'<':Push(&OPTR,c); 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"); retu