实验2 栈和队列的应用-算术表达式求值(5页).doc

-1. 实验题目 栈和队列的应用2. 实验内容 算术表达式求值3.实验目的掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。4. 实验要求为了更好的掌握与理解课堂上老师所讲的概念与原理，实验前要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。5.概要设计原理6.详细程序清单及注释说明#include <stdio.h>#include <iostream.h>#include <stdlib.h>#include <string.h>#define NULL 0#define OK 1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 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->stacksize=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=*(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; case '(' : 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)switch(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(*(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'<':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("请输入正确的表达式以'#'结尾:n");dogets(expr);while(!*expr);InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,'#'); /* 将#压入运算符栈 */ InitStack(&OPND); /* 初始化操作数栈 */ printf("表达式的运算结果为:%dn",EvaluateExpression();getchar();return 0;7. 运行与测试及结果8.实验中所遇的问题及解决方法-第 5 页-