《[理學]表達式求解迷宮求解》由會員分享，可在線閱讀，更多相關《[理學]表達式求解迷宮求解（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 課 程 設 計 報 告 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 表達式求解 迷宮求解 專 業(yè) 信息與計算科學 班 級 學 號 姓 名 指導教師 年 月 日 湖南工程學院 課 程 設 計 任 務 書 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題

2、 表達式求值 迷宮求解 專業(yè)班級 學生姓名 學 號 指導老師 審 批 任務書下達日期 2009 年 5 月 15 日 任務完成日期 年 月 日 一、設計內(nèi)容與設計要求 課題1表達式求值 問題描述：設計一編譯器，對讀入的表達式能根據(jù)人們的約定予以正確解釋，并計算結(jié)果。 設計要求：（1

3、）表達式中應包含數(shù)值常量、四則運算符、括號等。 （2）對不合理的解釋應有反應。 設計提示：（1）可用兩個棧（操作數(shù)棧及運算符棧）來存儲原始數(shù)據(jù)及中間結(jié)果。 （2）對表達式進行語法檢查。 （3）用一一維數(shù)組約定運算符的位置，用一二維數(shù)組存放運算符間的優(yōu)先關系。 測試數(shù)據(jù)：3+a*9 2+(1*(7-8)*5 7*(5+6-4*2/(2*7))+9/4-5 課題4 迷宮問題 問題描述：用計算機模擬解決“迷宮問題”，求出其中一條通道。用數(shù)組MAZE[1...M,1..N]表示迷宮，有的可以通行（0表示），有的是路障（1

4、表示），MAZE[1][1]為迷宮入口,MAZE[M][N]為迷宮出口,用非遞歸算法求出一條通路。 設計要求：用“■”標示所輸出的路徑(見運行示例)否則說明沒有通路,繼續(xù)生成迷宮,直到有通路。 算法提示：實現(xiàn)這一算法的具體方法很多（如堆棧,隊列等）,但基本思想一般是回溯法使用MAZE[M][N]表示迷宮（如圖２），為判定過程中是否越界，在其外圍加一圈１作為路障，mark[M][N]作為標志數(shù)組，move[8][2]是行列增量數(shù)組（見圖１－２）；建堆棧．約定（i,j）表示I行j列,direction 表示方向, 從入囗開始探索路徑：沿０－１八個方向依次試探，若某方向可通（為０），則該點連同

5、方向入堆棧，從該點繼續(xù)試探；若八個方向都不通，則取出堆棧頂點，從其標記的方向開始試探其余方向；直至找到出口（有通路）或堆棧為空(沒有通路). 下面是利用一隨機函數(shù)生成的0/1方陣及運行示例: 二、進度安排 日 期 上午 下午 15周星期一 課題講解 明確任務查資料 15周星期二 上機調(diào)試 上機調(diào)試 15周星期三 上機調(diào)試 上機調(diào)試 16周星期二 上機調(diào)試 上機調(diào)試 16周星期五 上機調(diào)試及答辯 答辯 目錄 1 表達式求值 1.1問

6、題分析…………………………………………………………… 1.2算法描述…………………………………………………………… 1.3運行結(jié)果…………………………………………………………… 1.4設計體會…………………………………………………………… 2 迷宮求解 2.1問題分析…………………………………………………………… 2.2算法描述…………………………………………………………… 2.3運行結(jié)果…………………………………………………………… 2.4設計體會……………………………………………………………

7、 1表達式求值 1.1問題分析 設計一個編譯器，能對一個含有數(shù)值常量，四則運算符，括號的表達式根據(jù)人們給予約定計算正確的結(jié)果，并且對于不合理的表達式有所反應。關于表達式求值，輸入的數(shù)據(jù)用棧這一數(shù)據(jù)結(jié)構(gòu)儲存，建立一個數(shù)據(jù)棧（OPND），用來存儲表達式中的數(shù)據(jù)；一個運算符棧（OPTR），用來存儲表達式中的四則運算符；用一個二維數(shù)組約定運算符之間的優(yōu)先級別。通過對兩個棧進行元素的進棧與出棧以及中間結(jié)果的計算，得到輸入表達式的值。 1.2算法描述 表達式求值是棧應用的一個典型列子

8、，我采用的是一種簡單直觀、廣為使用的算法，通常稱為“算符優(yōu)先法”。任何一個表達式都是由操作數(shù)、運算符和界限符組成的，其中操作數(shù)是是用戶從鍵盤終端輸入的整型變量，運算符為‘+’、‘-’，‘*’，‘/’，界限符有左右括號和表達式結(jié)束符。在本程序中，我把運算符和界限符統(tǒng)稱為算符，他們構(gòu)成的集合命名為OP。根據(jù)三條運算法則： （1）先乘除，后加減； （2）從左算到右； （3）先括號內(nèi)，后括號外； 在運算的每一步，任意兩個相繼出現(xiàn)的算符@1和@2之間的優(yōu)先關系至多是下面三種關系之一： @1<@2 @1的優(yōu)先權低于@2 @1>@2 @2的優(yōu)先權高于@2 @1=@2 @1的優(yōu)

9、先權等于@2 表A定義了算符之間的這種優(yōu)先關系： （表A） @1 @2 + - * / （ ） # + > > < < < > > - > > < < > * > > > > < < < / > > > > < < < （ < < < <

10、 < = ） > > > > ? > > # < < < <

11、以下的這個算法描述了這個過程： OperandType EvaluateExpression(){ //算術表達式求值的算符優(yōu)先算法。設OPTR和OPND分別為運算符棧和運算數(shù)棧 // OP為運算符集合 InitStack(OPTR); Push(OPTR,‘#’)； InitStack(OPND);c=getchar(): do{ if(!In(c,OP) { Push(OPND,c);c=getchar;}//不是運算符則進棧 else switch(Precede（GetTop(OPTR),c） { case’

12、<’://棧頂元素優(yōu)先權低 Push(OPTR,c);c=getchar(); Break; Case’=’://脫括號并接收下一字符 Pop(OPTR,x); c=getchar(); Break; Case’>’://退棧并將運算結(jié)果入棧 Pop(OPTR,theta); Pop(OPND,b);

13、Pop(OPND,a); Push(OPND,Operate(a,theta,b)); Break; }//switch }while(!OPTR); Return GetTop(OPND); }//EvaluateExpression ? 算法中調(diào)用了兩個函數(shù)，其中Precede是判定運算符棧棧頂?shù)脑谸1與讀入的@2之間優(yōu)先關系的函數(shù)；Operate為進行二元運算a @ b的函數(shù)，如果是編譯表達式，則產(chǎn)生這個運算的一組相應指令并返回存放結(jié)果的中間變量名；如果是解釋執(zhí)行表達式，則直接進行運算

14、，并返回運算的結(jié)果。 流程圖 Main函數(shù)流程圖： 開始 N Y Y N Y 輸入一個表達式，存在數(shù)組c[N]中 建立數(shù)據(jù)棧（OPND） 運算符棧（OPTR） 將字符‘?！瘔喝? 棧OPTR中 c[i]為?；蛘逴PTR的棧頂元素為

15、＃ i＝0 c[i]為運算符 ] C[i]入棧 i++ OPTR的棧頂元素與c[i]優(yōu)先級比較 <：c[i]入棧 i++,break =：脫括號 i++;break >：計算中間結(jié)果 break 輸出結(jié)果 判斷OPTR是否為空 N i++ 結(jié)束 子函數(shù) Operate(char a,char b,char c) int a1=a-‘0’ int c1=c-‘0’ 將字符型的數(shù)字轉(zhuǎn)化為整型 Switch(b) case ‘+’:result=a1+c1 case ‘-’: result=a1-c1 case ‘*’: result=

16、a1*c1 case ‘/’: result=a1/c1 將計算結(jié)果轉(zhuǎn)化為字符型，作為返回值 開始 結(jié)束 取兩個運算數(shù)a,c; 取一個四則運算符b 子函數(shù) Precede(char a,char b) 開始 結(jié)束 用變量i，j 分別找到字符a，b的下標 用一維數(shù)aa[7]組約定字符的位置 用二維數(shù)組bb[7][7]約定兩字符的優(yōu)先級別 把bb[i][j]作為字符型的返回值 得到需要優(yōu)先級比較的字符a,b 1.3運行結(jié)果 在tc中輸入代碼中，不斷的編譯調(diào)試，不斷的發(fā)現(xiàn)問題，然后再找解決的辦法。我在調(diào)試

17、中主要遇到的問題如下： 1) 在剛看到課題的時候，不知道應該如何用一個二維數(shù)組約定運算符間的優(yōu)先級別，于是，翻閱了教科書，也試圖從圖書館中找到相應的資料，但是，失敗了，后來，在看書的時候，教科書中的表格，讓我突然的明白過來，于是，在上機的時候，用一維數(shù)組約定非運算數(shù)的位置，利用相應的下標在二維數(shù)組中得到優(yōu)先級別，并把它作為子函數(shù)Precede（char a,char b）的返回值。調(diào)試的時候，當我輸入‘+’，‘*’時，得到了預期中的結(jié)果‘<’。 2) 在一個一個子函數(shù)的代碼編寫中，當我遇到要計算中間結(jié)果的時候，不知道怎樣把從字符型棧中出棧的字符型的運算數(shù)，轉(zhuǎn)換為相應的整型，進而進行四則運算

18、。向老師請教，老師說是字符型的字符減去一個‘0’，就可以轉(zhuǎn)換成數(shù)字了，比如說 char a=’3’,做相應的處理：a1=a-‘0’；就得到了數(shù)字3。還有，怎樣把字符型的運算能，能進行運算呢，通過和同學的討論，可以選用switch 語句，根據(jù)運算的類型，做相應的代數(shù)運算，并把得到的結(jié)果返回。比如說，我要計算的是 ‘3’‘+’‘2’；先a1=‘3’-‘0’=3;c1=‘2’-‘0’=2；b==‘+’；result=3+2=5。又解決了一個問題。后來在與同學互相交流的時候，他們還告訴我一個方法，強制轉(zhuǎn)換成int 型再加上48就可以得到相應的整型值了。 3) 經(jīng)過一段時間的努力后，程序代碼總算是完

19、成了，編譯后沒有錯誤，沒有警告，但是就是得不到正確的計算結(jié)果，可以運行，但是進入了死循環(huán)，經(jīng)過一步步的調(diào)試，發(fā)現(xiàn)了問題是出在元素進棧的時候，運行結(jié)果總是打印“”The stack is full”,后來，知道了在main函數(shù)中的一個循環(huán)中應該把break該成continue，該了之后，再運行，可以得到一個結(jié)果了，但是不是正確的結(jié)果，而且無論我輸入的表達式是怎樣的，都得到結(jié)果49。后來，還是找了同學幫忙，他發(fā)現(xiàn)了我邏輯上的一個錯誤，在我的while循環(huán)中，我的第一個運算符不會入棧，所以中間結(jié)果沒有計算，直接就結(jié)束了，而把while語句改成do…while的時候，就可以把第一個運算符入棧了。 4

20、) 問題是一個接一個的解決了，但是，我的編譯器還是沒成功，后來，意識到了一個問題，那就是，我原先是用一個一維數(shù)組接收的求值表達式，如果我輸入的是一個2位數(shù)的數(shù)字，它就會成為2個字符儲存，出棧的時候，就會發(fā)生錯誤，導致得不到正確的結(jié)果。可，我輸入的是一位數(shù)的表達式時，很遺憾，還是出錯了。已經(jīng)自己發(fā)現(xiàn)不了錯誤，于是，去找老師請教，老師很耐心的給我的程序一步步的測試，一會之后，就發(fā)現(xiàn)了問題的所在，我的Operate的函數(shù)的返回值是int型的，然而，入棧的時候我直接用了Push（OPND，Operate（m，theta，n）），把一個int型的數(shù)據(jù)放進了一個字符型的棧，從而導致了其他的邏輯錯誤，應改成

21、Push（OPND，Operate（m，theta，n）+‘0’）；同時，在最后得到的表達式的計算結(jié)果時，也應將字符型的改回int型，即:printf(“\nthe result is:%d”,GetTop(OPND)-‘0’)。做了這樣了修改之后，程序終于能成功運行出正確的結(jié)果了。測試了一下8-2*（7-6）, 運行結(jié)果是 the result is:6 。 1.4設計體會 通過一星期的努力，終于把課題“表達式求值”完成了，

22、雖然做出來的編譯器之能進行一位數(shù)的四則運算，但是，我自己已經(jīng)很高興了。 這一星期的學習，我頗有感觸體會： (一) 因為知識的需要，報課本細致的看了一些，重新溫習了書本，對于之前的學習起了很大的補充作用，也對原有的知識進行了鞏固。 (二) 一個大的收獲應該是學以致用吧。把所學的知識用到了實處，不再是停留在理論的程度上，把所學進行組合，然后實實在在的做出了一點東西，有了信心，也有了小小的成就感，同時也產(chǎn)生了學習的興趣與樂趣。 (三) 在和同學老師的交流中學會了很多，認識到了自己的差距與不足，從優(yōu)秀的同學那里學到了很多的知識，也看了他們學習的認真和效果，從老師那里再一次深刻的體會到了學海無涯

23、，我們還有很多的東西尚需虛心學習。我要繼續(xù)努力，好好學習，天天向上。 (四) 一段時間的學習，發(fā)現(xiàn)了學好一樣東西并不難，只要有恒心，有堅持，有學習的情緒，或許，這并不是我最新的體會，可是，這次的學習，有體會到了它的真實性，好好的學，即便是理論上的東西，現(xiàn)在可能我們用不上，但，對于以后，誰能夠下定論呢，時間擺在我的眼前，與其虛度光影不如好好的學，不至于以后落得個數(shù)到用時方恨少。 (五) 做表達式求值這個課題，應該就算是做一個簡單的計算器吧，以前用計算器的時候，總覺得很神奇，輕輕一按，就可以得到計算結(jié)果，現(xiàn)在明白了一些原理，也對當前的科技對了幾分的敬佩。同時，也知道了有些東西，其實我們自己也可

24、以做到，只是我們目前的知識有限。應該說，這次的程序設計，激發(fā)了我對學習的部分熱情吧，對我所不知的世界、領域產(chǎn)生了想去探究的想法。 (六) 通過這段時間的共同學習，和同學們之間的友情加深了。一起談論學習，共同探討問題的答案，互相幫助，歡聲笑語也夾雜其中，很高興，能有愉快的學習氛圍。 完成了課程設計表達式求值，我覺得我的收獲真的很大，總結(jié)之后，更是發(fā)現(xiàn)了自己學會了很多，得到了很多，無論是學習還是思想上的一些東西。 2迷宮求解 2.1問題分析 三、報告要求 1 課程設

25、計說明書裝訂順序：封面、任務書、目錄、正文、評分、附件（A4大小的圖紙及程序清單）。 2 每課題應包含：問題分析、算法描述、運行結(jié)果、設計體會等。 正文 宋體5號 一 附錄 1 表達式求值 # include # include # define N 100 # define TRUE 1 # define FALSE 0 typedef struct { char stack[N]; int top; } SeqStack; SeqStack

26、 *InitStack() { SeqStack *s; s=malloc(sizeof(SeqStack)); if(!s) {printf("do not have enoughf space");return NULL; } else s->top=-1; return s; } char GetTop(SeqStack *s) { if(s->top==-1) {printf("\nthis is a empty stack!");return FALSE;} else return (s->stack[s->top]); } SeqSta

27、ck *Push(SeqStack *s,char x) { if(s->top==N-1) {printf("\n the stack is full!"); return NULL;} else { s->top++; s->stack[s->top]=x; return s; } } char Pop(SeqStack *s) { if(s->top==-1) { printf("\nThe sequence stack is empty!"); return FALSE; } (s->top)--; return (s->stack[s-

28、>top+1]); } int StackEmpty(SeqStack *s) { if(s->top==-1) return TRUE; else return FALSE; } int match(char *c) { int i=0; SeqStack *s; s=InitStack(); while(c[i]!='#') { switch(c[i]){ case '(':Push(s,c[i]);break; case ')':if(!StackEmpty(s)&&GetTop(s)=='(') { Pop(s);break;

29、} /* end if */ else return FALSE; } /* end switch */ i++; } /* end while */ return (StackEmpty(s)); } char Precede(char a,char b) { int i,j; char aa[7]={'+','-','*','/','(',')','#'}; char bb[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>'

30、,'>'}, {'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','@'},{'>','>','>','>','@','>','>'}, {'<','<','<','<','<','@','='}}; for(i=0;i<7;i++){ if(a==aa[i]) break; } for(j=0;j<7;j++) { if(b==aa[j]) break; } return bb[i][j]; }

31、int YSF(char y) { if(y=='+'||y=='-'||y=='*'||y=='/'||y=='('||y==')') return TRUE; else return FALSE; } int Operate(char a,char b,char c) { int a1,c1,result; a1=a-'0'; c1=c-'0'; switch(b){ case '+':result=a1+c1;break; case '-':result=a1-c1;break; case '*':result=a1*c1;break; case '/'

32、:result=a1/c1;break; } return result; } void main() { char c[N]; int i,j; char m,n,theta; SeqStack *OPTR; /* yunsanfu */ SeqStack *OPND; /* yunsanshu */ OPTR=InitStack(); Push(OPTR,'#'); OPND=InitStack(); i=0; do { c[i]=getchar(); i++; }while(c[i-1]!='#'); print

33、f("\nthe equation you input is below:\n"); for(j=0;j

34、 switch(Precede(GetTop(OPTR),c[i])) { case '<':Push(OPTR,c[i]);i++;break; case '=':Pop(OPTR);i++;break; case '>':{ theta=Pop(OPTR); n=Pop(OPND); m=Pop(OPND); Push(OPND,Operate(m,theta,n)+'0'); } break; } /* end swtich */ } while(c[i]!='#'||GetTop(OPTR)!='#');

35、 /*end while */ printf("the result of the equation is: %d", GetTop(OPND)-'0'); getchar(); } /* end main() */ 2迷宮求解： #include #include /************************************************************** 數(shù)據(jù)定義 *************************

36、*************************************/ typedef enum { ERROR, OK } Status; typedef struct { int row; //row表示“行”號 int line; //line表示“列”號 }PosType; //位置的元素類型 typedef struct { int ord; //該通道在路徑上的“序號” PosType seat; /

37、/通道塊在迷宮中的“坐標位置” int di; //從此通道走向下以通道塊的“方向” }SElemType; //棧的元素類型 typedef struct { SElemType * base; SElemType * top; int stacksize; }SqStack; /************************************************************** 函數(shù)原型說明 ********************

38、******************************************/ Status InitStack(SqStack &S); //創(chuàng)建一個空棧S Status Push(SqStack &S,SElemType &a); //插入新元素a Status Pop(SqStack &S,SElemType &a); //刪除棧頂元素，a返回其值 Status StackEmpty(SqStack S); //檢查是否

39、空棧 Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end); //找通路 void Initmaze(int maze[12][12],int size); //初始化迷宮 void printmaze(int maze[12][12],int size); //顯示迷宮 Status Pass(int maze[12][12],PosType CurPos); //判斷當前位置是否可通 void Markfoot(int maz

40、e[12][12], PosType CurPos); //標記當前位置不可通 PosType NextPos(PosType CurPos, int Dir); //進入下一位置 void printpath(int maze[12][12],SqStack S,int size); //顯示通路 /************************************************************** 主函數(shù) **********************************

41、****************************/ void main (void) { SqStack S; int size,maze[12][12]; for(int n=0;n<10;n++) { printf("創(chuàng)建一個正方形迷宮，請輸入迷宮尺寸(注意不要大于10):\n"); //設置迷宮大小 scanf("%d",&size);if(size<1 || size>10){printf("輸入錯誤!");return;} Initmaze(maze,size); //初始化迷宮

42、printmaze(maze,size); //顯示所創(chuàng)建的迷宮 PosType start,end; //設置入口和出口 printf("輸入入口行坐標和列坐標:");scanf("%d",&start.row);scanf("%d",&start.line); printf("輸入出口行坐標和列坐標:");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(maze,S,start,end)) //若有通路，顯示通路

43、 printpath(maze,S,size); else printf("找不到通路!\n\n"); } } /************************************************************** 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中 **************************************************************/ Status MazePath(int maze[12][12],SqStack &S, P

44、osType start, PosType end) { PosType curpos; int curstep; SElemType e; InitStack(S); curpos = start; // 設定"當前位置"為"入口位置 curstep = 1; // 探索第一步 do { if (Pass(maze,curpos)) // 當前位置可通過，即是未曾走到過的通道塊 { Markfoot(

45、maze,curpos); // 留下足跡 e.di =1; e.ord = curstep; e.seat= curpos; Push(S,e); // 加入路徑 if (curpos.row==end.row && curpos.line==end.line) return OK; // 到達終點（出口） curpo

46、s = NextPos(curpos, 1); // 下一位置是當前位置的東鄰 curstep++; // 探索下一步 } else // 當前位置不能通過 { if (!StackEmpty(S)) { Pop(S,e); while (e.di==8 && !StackEmpty(S)) {

47、 Markfoot(maze,e.seat); // 留下不能通過的標記，并退回一步 Pop(S,e); } if (e.di<8) { e.di++; // 換下一個方向探索 Push(S, e); curpos = NextPos(e.seat, e.di); // 當前位置設為新方向的相鄰塊

48、 } } } } while (!StackEmpty(S)); return ERROR; } /************************************************************** 初始化迷宮 **************************************************************/ void Initmaze(int maze[12][12],int size) { for(int i

49、=0;i

50、* 顯示迷宮 **************************************************************/ void printmaze(int maze[12][12],int size) { printf("\n\n"); printf("顯示所建的迷宮(#表示外面的墻):\n"); for(int i=0;i

51、,'#'); for(int j=1;j

52、*****************************************************/ void printpath(int maze[12][12],SqStack S,int size) { printf("\n\n通路路徑為:\n"); SElemType * p=S.base; while(p!=S.top) { maze[p->seat.row][p->seat.line]=2; //標記為路徑中的點 p++; } for(int i=0;i

53、printf("\n"); for(i=1;i

54、 /************************************************************** 判斷當前位置是否可通 **************************************************************/ Status Pass(int maze[12][12],PosType CurPos) { if (maze[CurPos.row][CurPos.line]==0) return OK; //

55、如果當前位置是可以通過，返回1 else return ERROR; // 其它情況返回0 } /************************************************************** 標記當前位置不可通 **************************************************************/ void Markfoot(int maze[12][12],PosType CurPos) { maze[Cur

56、Pos.row][CurPos.line]=1; } /************************************************************** 進入下一位置 **************************************************************/ PosType NextPos(PosType CurPos, int Dir) //進入下一位置 { PosType ReturnPos; switch (Dir) { case 1:

57、 ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line; break; case 2: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line+1; break; case 3: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line+1; break;

58、 case 4: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line+1; break; case 5: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line; break; case 6: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line-1;

59、 break; case 7: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line-1; break; case 8: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line-1; break; } return ReturnPos; } /**********************************************************

60、**** 創(chuàng)建一個空棧S **************************************************************/ Status InitStack(SqStack &S) { S.base=(SElemType *)malloc(100*sizeof(SElemType)); if(!S.base)return ERROR; S.top=S.base; S.stacksize=100; return OK; } /***********************************

61、*************************** 插入新元素a **************************************************************/ Status Push(SqStack &S,SElemType &a) { *S.top++=a; return OK; } /************************************************************** 刪除棧頂元素，a返回其值

62、 **************************************************************/ Status Pop(SqStack &S,SElemType &a) { if(S.top==S.base)return ERROR; a=*--S.top; return OK; } /************************************************************** 檢查是否空棧 **************************************************************/ Status StackEmpty(SqStack S) { if(S.top==S.base)return OK; return ERROR; }