實驗2棧和隊列的應(yīng)用-算術(shù)表達式求值

1、1 .實驗題目棧和隊列的應(yīng)用2 .實驗內(nèi)容算術(shù)表達式求值3 .實驗?zāi)康恼莆諚：完犃械母拍罴肮ぷ髟?，運用其原理完成實驗題目中的內(nèi)容。4 .實驗要求為了更好的掌握與理解課堂上老師所講的概念與原理，實驗前要認(rèn)真預(yù)習(xí)所 做的實驗內(nèi)容及編寫源程序偽碼（寫在紙上及盤中均可）以便在實驗課中完成老 師所布置的實驗內(nèi)容。5 .概要設(shè)計原理6 .詳細(xì)程序清單及注釋說明#include <stdio.h>#include <iostream.h>#include <stdlib.h>#include <string.h># define NULL 0# define

2、 OK 1# define OVERFLOW -2# define STACK_INIT_SIZE 100# define STACKINCREMENT 20/*定義字符類型棧*/ typedef struct fint stacksize;char *base;char *top;(SqStack;/*全局變量*/SqStack OPTR,OPND;定義運算符棧和操作數(shù)棧 char expr255; /*存放表達式串*/ char *ptr=expr;int InitStack(SqStack *s) 構(gòu)造運算符棧s->base=(char *)maIloc(STACK_INIT_SI

3、ZE*sizeof(char); if(!s->base) exit(OVERFLOW);s->top=s->base;s->stacksize=STACKJNIT_SIZE: return OK;charln(charch) 判斷字符是否是運算符，運算符即返回1(retum(ch='+'llch='-'llch='*'llch=7'llch='('llch=')'llch=#);int Push(SqStack *s,char ch) 運算符棧插入ch為新的棧頂元素(*s->

4、top=ch;s->top+;return 0;charPop(SqStack*s) 刪除運算符棧s的棧頂元素，用p返回其值 (char p;s->top-;p=*s->top;return p;)char GetTop(SqStack s)用p返回運算符棧s的棧頂元素(char p=*(s.top-l);return p;/*判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的*/char Precede(char c 1 ,char c2)(int i=0,j=0;static char array49='>!<；k',>> '> 

5、9;< ><','<'>'<'!'< '< '< <switch(c 1)/* i為下面array的橫標(biāo)*/ case '+' : i=O;break; case : i=l;break; case : i=2;break; case 7 : i=3;break; case : i=4;break; case y : i=5;break; case : i=6;break;)switch(c2)/* j為下面array的縱標(biāo)*/case '+

6、9; : j=O;break;case : j=l;break;case: j=2;break;case 71: j=3;break;case V : j=4;break; case *)*: j =5;break; case *#*: j=6;break;)return (array7*i+jj); /* 返回運算符 */ 1/*操作函數(shù)*/int Operate(int a,char opjnt b)(switch(op)case '+' : return (a+b);case: return (a-b);case: return (a*b);case 7 : return

7、 (a/b);)return 0;)int num(int n)返回操作數(shù)的長度char p 101；itoa(n,p,10);把整型轉(zhuǎn)換成字符串型 n=strlen(p);return n;int EvaluateExpression()主要操作函數(shù)char c,theta,x; int n,m;int a,b;c = *ptr+;while(c!='#,IIGetTop(OPTR) !='#')(if(!In(c) if(!In(*(ptr-l) ptr=ptr-l;m=atoi(ptr); 取字符串前面的數(shù)字段 n=num(m);Push(&OPND,m)

8、;ptr=ptr+n;c=*ptr+;)elseswitch(Precede(GetTop(OPTR),c)(case,<,:Push(&OPTR,c)；c=*ptr+:break; case=,:x=Pop(&OPTR);c=*ptr+;break; case''：theta=Pop(&OPTR); b=Pop(&OPND); a=Pop(&OPND);Push(&OPND,Operate(a,theta,b);break;)return GetTop(OPND);)int main()(printf("請輸入正

9、確的表達式以#結(jié)尾:n ");do gets(expr);) while(! *expr);InitStack(&OPTR); /*初始化運算符棧*/ Push(&OPTR：#1); /*將#壓入運算符棧*/ InitStack(&OPND); /*初始化操作數(shù)棧*/ printf("表達式的運算結(jié)果為:%dn ",EvaluateExpression(); getchar();return 0;7 .運行與測試及結(jié)果Bl 二 e e 9 Q又 dddeeee e fCA WC; Docu>ent s and 5”“11&541>11115，131:。1桌面。61)11名運用棧表達式求