《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》實(shí)驗(yàn)2

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)二學(xué)院：自動(dòng)化學(xué)院班級(jí)：學(xué)號(hào)：姓名：一、實(shí)驗(yàn)?zāi)康陌凑账膭t運(yùn)算加、減、乘、除、哥(人)和括號(hào)的優(yōu)先關(guān)系和慣例，編寫計(jì)算器程序。二、實(shí)驗(yàn)內(nèi)容簡(jiǎn)單計(jì)算器。請(qǐng)按照四則運(yùn)算加、減、乘、除、哥(人)和括號(hào)的優(yōu)先關(guān)系和慣例，編寫計(jì)算器程序。 要求： 從鍵盤輸入一個(gè)完整的表達(dá)式，以回車作為表達(dá)式輸入結(jié)束的標(biāo)志。輸入表達(dá)式中的數(shù)值均為大于等于零的整數(shù)。中間的計(jì)算過程如果出現(xiàn)小數(shù)也只取整。例如，輸入：4+2*5=輸出：14輸入：(4+2)*(2-10)=輸出：-48三、程序設(shè)計(jì)概要設(shè)計(jì)1、宏定義#define TRUE 1#define FALSE 0#define OK 1#def

2、ine ERROR 02、基本函數(shù)：(1) void InitStack_char(SqStack *S) /char型棧初始化(2) void InitStack_int(sqStack *S)/int型棧初始化(3) void Push_char(SqStack *S,char ch) /char 型元素進(jìn)棧(4) void Push_int(sqStack *S,int num) /int型元素進(jìn)棧(5) char GetTop_char(SqStack *S) / 取 char 型棧頂元素(6) int GetTop_int(sqStack *S) / 取int 型棧頂元素(7) St

3、atus In(char c) /判斷是否為運(yùn)算符，若是運(yùn)算符則返回，否則返回(8) char Precede(char a,char b) /判斷兩運(yùn)算符的先后次序(9) Status Pop_char(SqStack *S,char &x) /char型棧出棧(10) Status Pop_int(sqStack *S,int &x) /int型棧出棧3計(jì)算a和b運(yùn)算結(jié)果(11) int Operate(int a,char theta,int b) /3、流程圖詳細(xì)設(shè)計(jì)數(shù)據(jù)類型typedef struct node /構(gòu)造 char 型棧char ch;struct no

4、de *next;node;typedef structstruct node *base;struct node *top;SqStack;typedef struct lnode /構(gòu)造 int 型棧int num;struct Inode *next;lnode;typedef structstruct Inode *base;struct Inode *top;sqStack;操作部分void InitStack_char(SqStack *S)S->base = (node *)malloc(sizeof(node);S->base->next=NULL;S->

5、;top = S->base;/char型棧初始化void InitStack_int(sqStack *S)S->base = (lnode *)malloc(sizeof(lnode);S->base->next=NULL;S->top = S->base;/int型棧初始化void Push_char(SqStack *S,char ch)node *p;p=(node*)malloc(sizeof(node);p->ch=ch;p->next=S->top;S->top=p;/char型元素進(jìn)棧Status Push_int(

6、sqStack *S,int num)Inode *p;p=(lnode*)malloc(sizeof(lnode);p->num=num;p->next=S->top;S->top=p;return OK;/int型元素進(jìn)棧char GetTop_char(SqStack *S)return (S->top->ch);/取char型棧頂元素int GetTop_int(sqStack *S)return (S->top->num);/取int型棧頂元素Status Pop_char(SqStack *S,char &x) if(S-&g

7、t;base = S->top)return ERROR;node *p;p=S->top;x=p->ch;S->top=p->next;7free(p)；return OK;/char型棧出棧Status Pop_int(sqStack *S,int &x)if(S->base = S->top)return ERROR;lnode *p;p=S->top;x=p->num;S->top=p->next;free(p);return OK;/int型棧出棧計(jì)算功能int Operate(int a,char theta

8、,int b)int i,z = 1;switch(theta)case '+':z = (a + b);break;case '-':z = (a - b);break;case '*':z = (a * b);break;case '/':z = (a / b);break;case '"for(i = 1;i<=b;i+)z = z*a;break;return 億);/計(jì)算a和b運(yùn)算結(jié)果Status In(char c)(if(C='+'|c='-'|C='*

9、'|C='/'|C='('|C=')'|C='='|C='A')return OK;elsereturn ERROR;/判斷是否為運(yùn)算符char Precede(char a,char b)(if(a='+'|a='-')(if(b='+'|b='-'|b=')'|b='=')return '>'elsereturn '<'if(a='*'11a=

10、9;/')(if(b='('|b='A，)return '<'elsereturn '>'if(a='(')(if(b=')')return '='elsereturn '<'if(a=')')if(b!='(')return '>'if(a='#')if(b='=')return '='else17return '<'if(a

11、='A')return ('>');主函數(shù)int main()/char c,x,theta;int a,b,c1;/SqStack OPTR;/sqStack OPNR;/InitStack_char(&OPTR);判斷兩運(yùn)算符的先后次序主函數(shù)定義變量定義字符棧定義整型棧/初始化InitStack_int(&OPNR); /Push_char(&OPTR,'#'); /c = getchar();/初始化將字符型棧底設(shè)為#從鍵盤輸入得到字符判定是否執(zhí)行循環(huán)switch(Precede(GetTop_char(&am

12、p;OPTR),c) /case '<':Push_char(&OPTR,c);c = getchar();break;入char棧case '=':Pop_char(&OPTR,c);c = getchar();break; /char 棧判定運(yùn)算符的優(yōu)先關(guān)系/當(dāng)前運(yùn)算符優(yōu)先級(jí)高，存運(yùn)算符次序相等，存入while(c!='='|GetTop_char(&OPTR)!='#') /if(!In(c)cl = 0;while(!In(c)cl = c1*10+c-'0'c = getch

13、ar();Push_int(&OPNR,c1);/當(dāng)掃描字符不是運(yùn)算符時(shí)，轉(zhuǎn)化為整型數(shù)存入棧中else當(dāng)前運(yùn)算符優(yōu)先級(jí)低計(jì)算運(yùn)算結(jié)果，并存入int棧繼續(xù)循環(huán)case '>':/Pop_char(&OPTR,theta);Pop_int(&OPNR,b);Pop_int(&OPNR,a);Push_int(&OPNR, Operate(a,theta,b);/break;/printf("%dn",GetTop_int(&OPNR);/計(jì)算完成，取出 int 棧頂元素，并輸出return 0;四、程序調(diào)試分

14、析編寫程序的過程中遇到了很多的問題，最突出的兩個(gè)問題就是整數(shù)和兩位數(shù)的運(yùn)算處理，一開始修改了主函數(shù)部分之后，原來可以執(zhí)行一位數(shù)運(yùn)算的程序出現(xiàn)了error ,由于沒有及時(shí)保存，并且之前的代碼無法恢復(fù)，只得重新編寫一次。 第二次編寫理清思路之后，在課本和網(wǎng)上資料的輔助下，終于成功的編出了程序并且可以完美執(zhí)行。經(jīng)驗(yàn)告訴了我在編程的時(shí)候一定要注意經(jīng)常進(jìn)行調(diào)試，只有學(xué)會(huì)調(diào)試才能處理好大程序的編寫，否則極其容易出錯(cuò)。五、用戶使用說明1 .運(yùn)行程序，2 .將整個(gè)表達(dá)式從鍵盤鍵入，以“二”結(jié)束，回車可得到結(jié)果。六、程序運(yùn)行結(jié)果(1)輸入：(11+3) *5=輸出：70(2)輸入：(31-13)/(9-3)=輸

15、出：6七、程序清單#include<stdio.h>#include<stdlib.h># define TRUE 1# define FALSE 0# define OK 1# define ERROR 0 typedef int Status;構(gòu)造char型棧typedef struct node / char ch;struct node *next;node;typedef struct struct node *base;struct node *top;SqStack;typedef struct Inode /構(gòu)造 int 型棧int num;struct

16、 Inode *next;lnode;typedef struct struct Inode *base;struct Inode *top;sqStack;void InitStack_char(SqStack *S) S->base = (node *)malloc(sizeof(node);S->base->next=NULL;S->top = S->base;/char型棧初始化void InitStack_int(sqStack *S) S->base = (lnode *)malloc(sizeof(lnode);S->base->n

17、ext=NULL;S->top = S->base;/int型棧初始化void Push_char(SqStack *S,char ch) node *p;p=(node*)malloc(sizeof(node);p->ch=ch;p->next=S->top;S->top=p;/char型元素進(jìn)棧Status Push_int(sqStack *S,int num)lnode *p;p=(lnode*)malloc(sizeof(lnode);p->num=num;p->next=S->top;S->top=p;return OK;

18、/intchar GetTop_char(SqStack *S)return (S->top->ch);/int GetTop_int(sqStack *S)return (S->top->num);/Status Pop_char(SqStack *S,char &x) if(S->base = S->top)return ERROR;node *p;p=S->top;x=p->ch;S->top=p->next;free(p);return OK;/char型元素進(jìn)棧取char型棧頂元素取int型棧頂元素型棧出棧Statu

19、s Pop_int(sqStack *S,int &x) if(S->base = S->top) return ERROR;lnode *p;p=S->top;x=p->num;S->top=p->next;free(p);return OK;型棧出棧/intint Operate(int a,char theta,int b)int i,z = 1; switch(theta) case '+':z = (a + b);break;case '-':z = (a - b);break;case '*'

20、;:z = (a * b);break;case '/':z = (a / b);break;case，A，:for(i = 1;i<=b;i+) z = z*a;break;)return 億)；計(jì)算a和b運(yùn)算結(jié)果)/Status In(char c)(if(c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='='|c='A') return OK;elsereturn ERROR;/判斷是否為運(yùn)算符char Prec

21、ede(char a,char b)(if(a='+'|a='-')(if(b='+'|b='-'|b=')'|b='=')return '>'elsereturn '<'if(a='*'11a='/')(if(b='('|b='A')return '<'elsereturn '>'if(a='(')(if(b=')'

22、)return '='elsereturn '<'if(a=')')if(b!='(')return '>'if(a='#')if(b='=')return '='elsereturn '<'if(a='A') return ('>');int main()/char c,x,theta;int a,b,c1;/SqStack OPTR;/sqStack OPNR;/InitStack_char(&OPTR);InitStack_int(&OPNR);Push_