数据结构实验三后缀表达式的计算
实验三 后缀表达式的计算实验目的： 熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的 数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。实验内容与要求： 按常规形式输入算术表达式（例如：输入2*（6-4）+8/4），要求能够：（1）生成表达式的后缀表示，并输出；（2）生成表达式的前缀表示，并输出；（3）基于表达式的后缀表示，对该表达式求值；（4）编写一个主程序对表达式求值函数进行测试。算法设计：#include<stdio.h> #include<malloc.h> #include<string.h> #define ERROR 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 struct ElemType *base;ElemType *top;int stacksize;/当前已分配的存储空间SqStack; SqStack OPTR, OPND; SeqQueue SeQ; char PreTab77='>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','x', '>','>','>','>','x','>','>', '<','<','<','<','<','x','='；该矩阵中，X字符表示不存在优先 关系，在分析过程查找到这个值，表示表达 式有错。char *OpretorS="+-*/()#"/运算符集char *Express="2*(6-4)+8/4"/初始化的表达式int InitStack(SqStack *S);/构造空栈int push(SqStack *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)/出队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;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 是否运算符，若是运算符则返回改运算符在运算符集中的位置 int IsOps(char c)int i=0;char *p;p=OpretorS;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-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='*'|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");elsewhile(slen!='0')len+；for(int i=len-1；i>=0；)if(si>=48&&si<=57)pj=si；j+；if(si=')')/假如是回括号，将它压栈。top+；stacktop=si；while(Operator(si)if(top=0|stacktop=')'|f(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前缀表达式为:");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' /将字符转换 成相应的数值Push(&OPND,digit); /操作数入栈EnterQueue (&SeQ,c);操作数入队c=*+ScanChar; elsecl=*(OPTR.top-l);switch(Precede(cl,c)调用哪个函数1case'v':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);
