數(shù)據(jù)結(jié)構(gòu)實驗三后綴表達式的計算

1、實驗三 后綴表達式的計算實驗?zāi)康模?熟練掌握棧和隊列的存儲結(jié)構(gòu)設(shè)計及基本操作的實現(xiàn)；學(xué)會分析實際問題中具有棧特點的數(shù)據(jù)結(jié)構(gòu)；了解表達式的前綴、中綴、后綴等計算機內(nèi)表示形式。實驗內(nèi)容與要求： 按常規(guī)形式輸入算術(shù)表達式（例如：輸入2*(6-4)+8/4），要求能夠： （1）生成表達式的后綴表示，并輸出；（2）生成表達式的前綴表示，并輸出； （3）基于表達式的后綴表示，對該表達式求值； （4）編寫一個主程序?qū)Ρ磉_式求值函數(shù)進行測試。算法設(shè)計：#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字符表示不存在優(yōu)先關(guān)系，在分析過程查找到這個值，表示表達式有錯。char *OpretorS="+-*/()#" /運算符集char *Express="2*(6-4)+8/4" /初始化的表達式int InitStack(SqStack *S); /構(gòu)造空棧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運算符的優(yōu)先關(guān)系 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) /判斷運算符級別函數(shù)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) /將中綴表達式轉(zhuǎn)化為前綴表達式char pN,stackN; int top=0,j=0, len=0; if(s0=')') printf("算術(shù)表達式錯誤！"); 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是操作數(shù) digit=c-'0' /將字符轉(zhuǎn)換成相應(yīng)的數(shù)值 Push(&OPND,digit); /操作數(shù)入棧 EnterQueue(&SeQ,c); /操作數(shù)入隊 c=*+ScanChar; else c1=*(OPTR.

15、top-1); switch(Precede(c1,c) /調(diào)用哪個函數(shù) 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算術(shù)表達式錯誤！n"); retu