《实验2 栈和队列的应用-算术表达式求值(5页).doc》由会员分享，可在线阅读，更多相关《实验2 栈和队列的应用-算术表达式求值(5页).doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-1. 实验题目 栈和队列的应用2. 实验内容 算术表达式求值3.实验目的掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。4. 实验要求为了更好的掌握与理解课堂上老师所讲的概念与原理，实验前要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。5.概要设计原理6.详细程序清单及注释说明#include #include #include #include #define NULL 0#define OK 1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCRE
2、MENT 20/* 定义字符类型栈 */ typedef structint stacksize;char *base;char *top;SqStack;/* - 全局变量- */ SqStack OPTR,OPND;/ 定义运算符栈和操作数栈char expr255; /* 存放表达式串 */char *ptr=expr;int InitStack(SqStack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!s-base) exit(OVERFLOW); s-top=s-base; s-stacksi
3、ze=STACK_INIT_SIZE;return OK; char In(char ch) /判断字符是否是运算符，运算符即返回1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#);int Push(SqStack *s,char ch) /运算符栈插入ch为新的栈顶元素*s-top=ch;s-top+;return 0;char Pop(SqStack *s) /删除运算符栈s的栈顶元素，用p返回其值char p;s-top-;p=*s-top;return p;char GetTop(SqStack s)/用p返回运算符栈s的栈顶元素char p=*(
4、s.top-1);return p;/* 判断运算符优先权，返回优先权高的 */ char Precede(char c1,char c2)int i=0,j=0;static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1)/* i为下面array的横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; ca
5、se ( : i=4;break; case ) : i=5;break; case # : i=6;break;switch(c2) /* j为下面array的纵标 */ case + : j=0;break;case - : j=1;break;case * : j=2;break;case / : j=3;break;case ( : j=4;break;case ) : j=5;break;case # : j=6;break;return (array7*i+j); /* 返回运算符 */ /*操作函数 */ int Operate(int a,char op,int b)switc
6、h(op)case + : return (a+b);case - : return (a-b);case * : return (a*b);case / : return (a/b);return 0;int num(int n)/返回操作数的长度 char p10;itoa(n,p,10);/把整型转换成字符串型n=strlen(p);return n;int EvaluateExpression()/主要操作函数 char c,theta,x; int n,m;int a,b;c = *ptr+;while(c!=#|GetTop(OPTR)!=#) if(!In(c) if(!In(*
7、(ptr-1) ptr=ptr-1; m=atoi(ptr);/取字符串前面的数字段 n=num(m); Push(&OPND,m);ptr=ptr+n;c=*ptr+;elseswitch(Precede(GetTop(OPTR),c) case: theta=Pop(&OPTR); b=Pop(&OPND); a=Pop(&OPND); Push(&OPND,Operate(a,theta,b);break;return GetTop(OPND);int main( )printf(请输入正确的表达式以#结尾:n);dogets(expr);while(!*expr);InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,#); /* 将#压入运算符栈 */ InitStack(&OPND); /* 初始化操作数栈 */ printf(表达式的运算结果为:%dn,EvaluateExpression();getchar();return 0;7. 运行与测试及结果8.实验中所遇的问题及解决方法-第 5 页-