算术表达式求值演示程序

数理学院
课程设计报告书
课程名称数据结构课程设计
设计题目算术表达式求值演示
专业班级
学号
姓名
指导教师
2014 年12 月
操作结果：a与b进行运算，op为运算符，返回其值。

num(n)
操作结果：返回操作数的长度。

EvalExpr()
初始条件：输入表达式合法。

操作结果：返回表达式的最终结果。

}ADT Stack
主程序的流程：
EvaluateExpression()函数实现了对表达式求值的功能，main()函数直接调用EvaluateExpression()对输入的表达式求值输出。

算法流程图
4.2.3
函数的调用关系图
main ReturnOpOrd
调用关系图
4.4测试与分析
4.4.1测试
4.4.2
实验分析：表达式求值程序是一个多次调用函数的过程，且调用的过程较为复杂，调试花费时间较多。

在while循环时指针移动容易出错，因此多次出现内存错误，对于涉及的循环的操作开始和结束条件设置很关键。

本次实验熟悉了栈数据结构的表示与实现方法。

算法时间和空间分析：算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据
EvaluateExpression
Operat
输出
- --
- . -word资料-。

需求分析(附代码)一、需求分析（1）首先定义两个栈OPTR、OPND，栈OPTR用于存放运算符，栈OPND 用于存放操作数；定义一个一维数组expr【】存放表达式串。

（2）主函数主要包括两部分：（1）判断运算符优先权，返回优先权高的；（2）操作函数。

（3）开始将‘#’入操作符栈，通过一个函数来判别算术运算符的优先级。

且规定‘#’的优先级最低。

在输入表达式的最后输入‘#’，代表表达式输入结束。

在表达式输入过程中，遇操作数则直接入栈。

遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。

如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。

（4）最初实现的加、减、乘、除及带小括号的基本运算，但考虑到实用性，后来的设计中有加上了乘方运算。

在乘方运算中借用了C库中自带的乘方函数pow。

二、概要设计1、设定栈的抽象数据类型定义：ADT Stack {数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n,n≥0 }数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }约定an端为栈顶，a1端为栈底。

基本操作：InitStack(&S)操作结果：构造一个空栈S。

DestroyStack(&S)初始条件：栈S已存在。

操作结果：栈S被销毁。

StackEmpty(S)初始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则FALE。

StackLength(S)初始条件：栈S已存在。

操作结果：返回S的元素个数，即栈的长度。

GetTop(S, &e)初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

ClearStack(&S)初始条件：栈S已存在。

汇编语言实训课程设计任务书题目：表达式求值程序班级：计算机科学与技术一班学生姓名：赵旭尧学号： 14730141 题目类型：软件工程（R）指导教师：刘树群一．题目简介该设计要求学生使用汇编语言，设计并开发出针对四则运算表达式进行求值的命令行或窗口程序。

通过该题目的设计过程，可以培养学生结构化程序设计的思想，加深对汇编语言基本语言要素和流程结构的理解，针对汇编语言中的重点和难点内容进行训练，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格。

得到软件工程的综合训练，提高解决实际问题的能力。

二．设计任务1、查阅文献资料，一般在5篇以上；2、通过键盘输入表达式，进行针对整数的“加减乘除”四则运算表达式进行求值，有良好的界面；3、完成软件结构设计和算法设计；4、完成系统的软件开发和测试工作；5、撰写设计说明书；6、做好答辩工作。

三．主要内容、功能及技术指标1、实现功能及指标：①使用Win32的窗口程序模式，实现表达式求值程序及测试界面程序的设计与开发；②支持整数的四则运算、位运算和小括号等；③使用文本框对表达式进行交互式编辑和输出。

2、问题分析及解决方案框架确定：充分地分析和理解问题本身，弄清要求做什么。

在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结构清晰、合理、简单和易于调试。

最后确定每个过程和函数的简单功能，以及过程（或函数）之间的调用关系，并画出函数之间的调用关系图。

3、详细设计和编码：定义相应的存储结构，确定各个函数的算法，并画出流程图，在此基础上进行代码设计，每个明确的功能模块程序一般不超过200行，否则要进一步划分。

4、完成课程设计报告①需求和规格说明：设计题目和问题描述：题目要解决的问题是什么；②设计思路：主要算法思想，程序功能图，函数之间的调用关系图；设计表示：每个函数或过程的功能，列出每个过程或函数所调用的过程或函数，并画出各函数的流程图；详细设计：主要算法的伪代码；③调试报告：调试过程中遇到的主要问题，是如何解决的；对设计和编码的回顾讨论和分析；改进设想；经验和体会等；④程序实现注释；⑤附录：源程序清单和结果。

算术表达式求值 表达式求值是实现程序设计语⾔的基本问题之⼀，也是栈的应⽤的⼀个典型例⼦。

设计⼀个程序，演⽰⽤算符优先法对算术表达式求值的过程 (1)从键盘输⼊任意⼀个语法正确的（中缀）表达式，显⽰并保存该表达式。

(2)利⽤栈结构，把上述（中缀）表达式转换成后缀表达式，并显⽰栈的状态变化过程和所得到的后缀表达式。

(3)利⽤栈结构，对上述后缀表达式进⾏求值，并显⽰栈的状态变化过程和最终结果。

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <ctype.h>#define N 100#define M 10char suffix[N]; //后缀表达式char ret[2]; //字符串栈进⾏弹出时的返回值（弹出元素）char tokens[N][M]; //令牌，将中缀表达式分解后的字符串数组char ctokens[N][M]; //令牌，将后缀表达式分解后的字符串数组int count; //tokens令牌的个数int value; //表达式的值int l = 0; //ctokens令牌的个数typedef struct stack1{ //操作符栈int top;char elem[N][2];}stacki;typedef struct stack2{ //操作数栈int top;int elem[N];}stackj;typedef stacki* STACK; //指向操作符栈的指针typedef stackj* DSTACK; //指向操作数栈的指针void toSuffix(char *str); //将中缀表达式转化成后缀表达式int PreParse(char tokens[][M],char *str); //将中缀表达式分解成令牌返回令牌中字符串个数int GetProsity(char *ch); //获得操作符的优先级并返回void push(STACK S,char *opt); //操作符栈的⼊栈char *pop(STACK S); //操作符栈的出栈，并返回出栈元素int IsEmpty(STACK S); //判断操作符栈是否为空void MakeNull(STACK S); //将操作符栈制空void PrintStack(STACK S); //打印操作符栈void dpush(DSTACK S,int opd); //操作符数的⼊栈void dpop(DSTACK S); //操作符数的出栈void PrintStack1(DSTACK S); //打印操作数栈void MakeNull1(DSTACK S); //将操作数栈制空int Evalute(char ctokens[][M]); //计算后缀表达式的值并返回int main(){char str[N];printf("Please input a expression：\n");gets(str); //输⼊所求中缀表达式strtoSuffix(str); //将中缀表达式转化成后缀表达式puts(suffix); //输出转化后的后缀表达式value = Evalute(ctokens); //计算后缀表达式的值printf("%d",value);return0;}void toSuffix(char *str){int i;stacki stacks; //定义⼀个操作符栈stacksSTACK optstack = &stacks; //定义操作符栈指针optstackMakeNull(optstack);count = PreParse(tokens,str);for(i = 0;i < count;i++){if(!(strcmp(tokens[i],"+") && strcmp(tokens[i],"-") && strcmp(tokens[i],"*") && strcmp(tokens[i],"/") && strcmp(tokens[i],"(") && strcmp(tokens[i],")"))){if(IsEmpty(optstack)){push(optstack,tokens[i]);PrintStack(optstack);}else{if(!strcmp(tokens[i],"(")){push(optstack,tokens[i]);PrintStack(optstack);}else if(!strcmp(tokens[i],")")){while(strcmp(optstack->elem[optstack->top],"(")) //循环直到遇见左括号{strcpy(ctokens[l],optstack->elem[optstack->top]);l++;strcat(suffix,pop(optstack));PrintStack(optstack);}pop(optstack); //左括号弹出PrintStack(optstack);}else{if(GetProsity(tokens[i]) > GetProsity(optstack->elem[optstack->top])){push(optstack,tokens[i]);PrintStack(optstack);}else{while(optstack->top < 100){if(GetProsity(tokens[i]) <= GetProsity(optstack->elem[optstack->top])){strcpy(ctokens[l],optstack->elem[optstack->top]);l++;strcat(suffix,pop(optstack));PrintStack(optstack);}else{break;}}push(optstack,tokens[i]);PrintStack(optstack);}}}}else//是数字则直接加到suffix的后⾯{strcpy(ctokens[l],tokens[i]);l++;strcat(suffix,tokens[i]);}}while(optstack->top < 100) //将剩余元素弹出{strcpy(ctokens[l],optstack->elem[optstack->top]);l++;strcat(suffix,pop(optstack));}PrintStack(optstack);}int PreParse(char tokens[][M],char *str){char p[N];char temp[2];int i=0,j = 0,l,k = 0;for(i = 0;i < strlen(str);i++) //删除表达式中的空格{if(str[i] == '') continue;else{p[j] = str[i];j++;}}p[j] = '\0';i = 0;for(j = 0;j < strlen(p);j++){if(p[j] == '+' || p[j] == '-' || p[j] == '*' || p[j] == '/' || p[j] == '(' || p[j] == ')') //运算符转化为字符串 {temp[0] = p[j];temp[1] = '\0';strcpy(tokens[k],temp);}else{for(l = 0;isdigit(p[j]);l++) //得到多位数字的字符串 {tokens[k][l] = p[j];j++;}tokens[k][l] = '\0';j--;}k++;}return k ;}int GetProsity(char *ch){int prosity;if(!(strcmp(ch,"("))){prosity = 0;}if(!(strcmp(ch,"+") && strcmp(ch,"-"))){prosity = 1;}if(!(strcmp(ch,"*") && strcmp(ch,"/"))){prosity = 2;}return prosity;}void push(STACK S,char *opt){if(S->top == 0){return ;}S->top--;strcpy(S->elem[S->top],opt);return ;}char *pop(STACK S){strcpy(ret,S->elem[S->top]);S->top++;return ret;}int IsEmpty(STACK S){if(S->top > N - 1)return1;elsereturn0;}void MakeNull(STACK S){S->top = N ;}void MakeNull1(DSTACK S){S->top = N ;}void PrintStack(STACK S){int i;for(i = N-1;i >= S->top;i--){printf("%s",S->elem[i]);}printf("\n");}void dpush(DSTACK S,int opd){if(S->top == 0){return ;}S->top--;S->elem[S->top] = opd;}void dpop(DSTACK S){S->top++;}void PrintStack1(DSTACK S){int i;for(i = N-1;i >= S->top;i--){printf("%d ",S->elem[i]);}printf("\n");}int Evalute(char ctokens[][M]){int i;int ropd,lopd;int t;stackj stack; //定义⼀个操作数栈DSTACK opdstack = &stack; //初始化操作数栈指针MakeNull1(opdstack);for(i = 0;i < l;i++){if(!strcmp(ctokens[i],"+")) //操作符则弹出两栈内元素进⾏相应运算 {ropd = opdstack->elem[opdstack->top];dpop(opdstack);lopd = opdstack->elem[opdstack->top];dpop(opdstack);t = lopd + ropd;dpush(opdstack,t);PrintStack1(opdstack);}else if(!strcmp(ctokens[i],"-")){ropd = opdstack->elem[opdstack->top];dpop(opdstack);lopd = opdstack->elem[opdstack->top];dpop(opdstack);t = lopd - ropd;dpush(opdstack,t);PrintStack1(opdstack);}else if(!strcmp(ctokens[i],"*")){ropd = opdstack->elem[opdstack->top];dpop(opdstack);lopd = opdstack->elem[opdstack->top];dpop(opdstack);t = lopd * ropd;dpush(opdstack,t);PrintStack1(opdstack);}else if(!strcmp(ctokens[i],"/")){ropd = opdstack->elem[opdstack->top];dpop(opdstack);lopd = opdstack->elem[opdstack->top];dpop(opdstack);t = lopd / ropd;dpush(opdstack,t);PrintStack1(opdstack);}else//操作数⼊栈{dpush(opdstack,atoi(ctokens[i]));PrintStack1(opdstack);}}value = opdstack->elem[opdstack->top];return value;}。

C#算术表达式求值（后缀法），看这⼀篇就够了⼀、种类介绍算术表达式有三种：前缀表达式、中缀表达式和后缀表达式。

⼀般⽤的是中缀，⽐如1+1，前后缀就是把操作符移到前⾯和后⾯，下⾯简单介绍⼀下这三种表达式。

1、前缀表⽰法前缀表⽰法⼜叫波兰表⽰法，他的操作符置于操作数的前⾯（例：+ 1 2），是波兰数学家扬·武卡谢维奇1920年代引⼊的，⽤于简化命题逻辑。

因为我们⼀般认为操作符是在操作数中间的，所以在⽇常⽣活中⽤的不多，但在计算机科学领域占有⼀席之地。

⼀般的表⽰法对计算机来说处理很⿇烦，每个符号都要考虑优先级，还有括号这种会打乱优先级的存在，将使计算机花费⼤量的资源进⾏解析。

⽽前缀表⽰法没有优先级的概念，他是按顺序处理的。

举个例⼦：9-2*3这个式⼦，计算机需要先分析优先级，先乘后减，找到2*3，再进⾏减操作；化成前缀表⽰法就是：- 9 * 2 3，计算机可以依次读取，操作符作⽤于后⼀个操作数，遇到减就是让9减去后⾯的数，⽽跟着9的是乘，也就是说让9减去乘的结果，这对计算机来说很简单，按顺序来就⾏了。

2、中缀表⽰法这也就是我们⼀般的表⽰法，他的操作符置于操作数的中间（例：1 + 2），前⾯也说过这种⽅法不容易被计算机解析，但他符合⼈们的普遍⽤法，许多编程语⾔也就⽤这种⽅法了。

在中缀表⽰法中括号是必须有的，要不然运算顺序会乱掉。

3、后缀表⽰法后缀表⽰法⼜叫逆波兰表⽰法，他的操作符置于操作数的后⾯（例：1 2 +），他和前缀表⽰法都对计算机⽐较友好，但他很容易⽤堆栈解析，所以在计算机中⽤的很多。

他的解释过程⼀般是：操作数⼊栈；遇到操作符时，操作数出栈，求值，将结果⼊栈；当⼀遍后，栈顶就是表达式的值。

因此逆波兰表达式的求值使⽤堆栈结构很容易实现，且能很快求值。

注意：逆波兰记法并不是简单的波兰表达式的反转。

因为对于不满⾜交换律的操作符，它的操作数写法仍然是常规顺序，如，波兰记法/ 6 3的逆波兰记法是6 3 /⽽不是3 6 /；数字的数位写法也是常规顺序。

一、设计思想计算算术表达式可以用两种方法实现：1.中缀转后缀算法此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算。

具体实现方法如下：（1）中缀转后缀需要建一个操作符栈op和一个字符数组exp，op栈存放操作符，字符数组用来存放转换以后的后缀表达式。

首先，得到用户输入的中缀表达式，将其存入str数组中。

对str数组逐个扫描，如果是数字或小数点，则直接存入exp数组中，当扫描完数值后，在后面加一个#作为分隔符。

如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组，直到遇到左括号，左括号丢掉。

然后继续扫描下一个字符，直到遇到str中的结束符号\0，扫描结束。

结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空。

到此在exp数组最后加结束字符\0。

我们就得到了后缀表达式。

（2）后缀表达式计算此时需要一个数值栈od来存放数值。

对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。

当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。

继续扫描，知道扫描结束，此时值栈中的数值就是计算的结果，取出返回计算结果。

2.两个栈实现算法此算法需要两个栈，一个值栈od，一个操作符栈op。

将用户输入的数学表达式存入str数组中，对其数组进行逐个扫描。

当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中；当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。

如果遇到操作符，若op栈为空，直接入栈；若栈不为空，与栈顶元素比较优先等级，若比栈顶操作符优先等级高，直接入op栈，如果低于或等于栈顶优先等级，op栈出栈，再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op栈。

实验报告题目：算术表达式求值演示班级：网络工程2班姓名：陈智鸣学号：1225112005 完成日期：2013.10.24一、需求分析1. 问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个经典例子。

设计一个程序演示用算符优先法对算术表达式求值的过程。

2. 基本要求：利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值。

3. 测试数据：教科书例3-1的算术表达式3*（7-2）。

二、概要设计（算法描述）基本操作：InitStack_f(&S)操作结果：构造一个空栈S。

GetTop_f(&S,&e)初始条件：栈S已存在。

操作结果：用e返回S的栈顶元素。

Push_f(&S，ch)初始条件：栈S已存在。

操作结果：插入元素ch为新的栈顶元素。

Pop_f(&S,&e)初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。

}ADT SqStack_f三、详细设计代码如下:#include <iostream>#include <stack>using namespace std;int Operate(int x,char op,int y) //四则运算符的运算定义{switch(op){case'+': return x+y;case'-': return x-y;case'*': return x*y;case'/': return x/y;}}char Precede(char op1,char op2) //判断符号的优先级{if(((op1=='+'||op1=='-')&&(op2=='+'||op2=='-'||op2==')'||op2=='#'))||((op1=='*'||op1=='/')&&( op2=='+'||op2=='-'||op2=='*'||op2=='/'||op2==')'||op2=='#')))return '>';if((op1=='('&&op2==')')||(op1=='#'&&op2=='#'))return '=';elsereturn '<';}void Tonumber(char &c,stack<int>&OPND) //转化为数字{ int number=0;if(((c-'0')>=0&&(c-'0')<=9)){while(((c-'0')>=0&&(c-'0')<=9)){number=number*10+(c-'0');cin>>c;}OPND.push(number);}}int main(){stack<char> OPTR;stack<int> OPND;//设OPTR和OPND分别为运算符栈和运算数栈OPTR.push('#'); //出栈时的结尾判断char c,op1,op2,op;int x,y,temp=1;cout<<"输入表达式，以'#'结束:";cin>>c;while(c!='#'||OPTR.top()!='#'){Tonumber(c,OPND);if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='('&&c!=')'&&c!='#'){OPND.push(c);cin>>c;}else{op1=OPTR.top();op2=c;switch(Precede(op1,op2)){case '<': //栈顶元素优先级低OPTR.push(c);cin>>c;break;case '=': //脱括号并接受下一个字符OPTR.pop();cin>>c;break;case '>': op=OPTR.top(); //退栈并将运算结果入栈OPTR.pop();x=OPND.top();OPND.pop();y=OPND.top();OPND.pop();OPND.push(Operate(y,op,x));int a=OPND.top();break;}}}cout<<"计算结果是:"<<OPND.top()<<endl;return 0;}四、调试分析1、在编程过程中，为了增加程序的实用性，将程序适用范围扩大到了实数型，并增加了连续输入功能；2、在编程过程中，为了增加程序的健壮性，在运算除法时，考虑到除数为“0”时的报错和及时退出；3、在调试过程中，最初一下子出来程序就出错，为了方便检查错误，故在主函数中增加了检查后缀表达式是否转换正确的函数，并在每一步计算都跟踪结果是否正确；4、从程序实验题的编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的栈的应用。

算术表达式求值演示（实验类型：综合型）1）问题描述：从键盘输入一个算术表达式并输出它的结果2）实验要求：算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现。

3) 实现提示：✧表达式作为一个串存储，如表达式“3*2-(4+2*1)”,其求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因后面可能还有更高的运算，正确的处理过程是：⏹需要两个栈：对象栈OPND和算符栈OPTR;⏹自左至右扫描表达式, 若当前字符是运算对象，入OPND栈;⏹对运算符，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从OPND栈出栈两个数，从OPTR栈出栈一运算符进行运算，并将其运算结果入OPND栈，继续处理当前字符，直到遇到结束符。

4）注意问题✧重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。

注意算法的各个函数之间值的传递情况。

#include<stdio.h>#include<stdlib.h>typedef int StackElementType;typedef struct node{StackElementType data;struct node *next;}LinkStack;/**/Intpriority[8][8]={3,3,1,1,1,1,3,3,3,3,1,1,1,1,3,3,3,3,3,3,3,1,3,3,3,3,3,3,3,1,3, 3,3,3,3,3,3,1,3,3,1,1,1,1,1,1,2,2,3,3,3,3,3,0,3,3,1,1,1,1,1,1,0,2};int IsEmpty(LinkStack *top){return top?0:1;/*top?0:1等价于top!=NULL?0:1*/}LinkStack *Push(LinkStack *top,StackElementType x){LinkStack *p;p=(LinkStack *)malloc(sizeof(LinkStack));if(p){p->data=x;/**/p->next=top;top=p;}else{printf("内存空间不足，停止运行！\n");exit(0);}return top;}LinkStack *Pop(LinkStack *top,StackElementType *elem){ LinkStack *temp;if(IsEmpty(top)){printf("空栈，出栈操作失败！\n");return NULL;} else {temp=top;*elem=top->data;/**/top=top->next;free(temp);return top; }}StackElementTypeGetTop(LinkStack *top){if(IsEmpty(top)){printf("空栈，读取操作失败！\n");return 0;}else return top->data;}int sub(StackElementType c){switch(c){case'+': return 0;case'-':return 1;case'*':return 2;case'/':return3;case'%':return 4;case'(':return 5;case')':return 6;case'#':return 7;}}int main(){StackElementType x1,x2,i,j,op,temp;char ch;LinkStack *OPTR=NULL;LinkStack *OPND=NULL;OPTR=Push(OPTR,'#');printf("输入求值表达式：");ch=getchar();while(! (ch=='#'&&GetTop(OPTR)=='#')){if( ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'||ch=='('||ch==')'||ch=='#'){i=sub(GetTop(OPTR));j=sub(ch);if(priority[i][j]==3){OPTR=Pop(OPTR,&op);OPND=Pop(OPND,&x2);OPND=Pop(OPN D,&x1);switch(op){case'+':OPND=Push(OPND,x1+x2);break;case'-':OPND=Push(OPND,x1-x2);break;case'*':OPND=Push(OPND,x1*x2); break;case'/':OPND=Push(OPND,x1/x2);break;case'%':OPND=Push(OPND ,x1%x2);}continue;}if(priority[i][j]==1)OPTR=Push(OPTR,ch);if(priority[i][j]==2)OPTR =Pop(OPTR,&temp);}else OPND=Push(OPND,ch-48);ch=getchar();}printf("表达式的值=%d\n",GetTop(OPND));//return ;}5）实验心得：经过一次上机实践，我认为实践课很重要，上理论课只是纸上谈兵，只是被动地接受，而实践课上能将学过的知识利用起来，同时还有一些东西只能是自己上机实践才能慢慢探索出的。

一、设计思想计算算数表达式并求值，可以采取两种算法：1.先将算术表达式转化为后缀表达式，然后对后缀表达式进行计算。

2.直接对算术表达式进行计算。

下面依次对两种方法进行分析：第一种算法有两步1.先将算数表达式转化为后缀表达式。

在计算过程中，第一，要先建立一个存放操作符的栈和一个存放数字的数组。

首先对用户输入的表达式进行扫面，如果是数字或者是小数点，直接存入数组。

如果是操作符，就判断是否为空或者是否为“（”或者是否它的优先级大于操作符栈顶的优先级，如果是，就入栈，索引后移；如果它的优先级不大于栈顶操作符，栈顶的操作符出栈，进入数组，如此循环，直到栈顶的优先级小于扫描到的操作符的优先级的时候，操作符入栈，索引后移。

当遇到标识符\0时，扫描结束。

数组中存放的就是后缀表达式。

2.利用后缀表达式进行计算。

得到后缀表达式后，要计算就需要用到数值栈。

首先对后缀表达式进行扫描，遇到数字字符，将数字字符转化为浮点类型，放入数值栈中，遇到操作符，就从数值栈中取出两个数，进行计算后将计算结果再放入数值栈中，扫描下一个，最后的计算结果就存到了数值栈中，直接取出数值栈栈顶元素，就是计算的最后结果。

第二种算法首先要建立两个栈，一个存放操作符的栈，一个是存放数值的栈。

然后开始对用户输入的表达式进行扫描，如果是数值或是小数点，就将其转化为浮点型数据，然后进入数值栈；如果是操作符，当前索引下的操作符的优先级如果不大于栈顶操作符的优先级，就将栈顶操作符取出来，从数值栈中取出两个数值，进行计算，结果存入数值栈。

如此循环，直到栈顶操作符的优先级小于当前索引的操作符的优先级是，操作符入栈，然后对下一个字进行扫描。

如果是左括号，则不进行优先级的比较，直接入栈。

如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号丢弃，扫描下一个。

扫描结束后，数值栈中存放的数值就是计算产生的结果，最后把数值从数值栈中取出，就是所得的计算结果。

算术表达式求值演示实习报告题目：算术表达式求值演示。

一、需求分析1.以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。

2.利用教科书表3.1给出的算符优先关系，实现对算数四则混合运算表达式的求值。

3.仿照教科书的例子在求值中运用符栈、运算数栈、输入字符和主要操作的变化过程。

4.程序执行的命令包括：(1)构造空栈；(2)判断符号优先级;(3) 判断是否为七种运算符之一;(4)运算求解算术表达式。

5.测试数据(1)3*(7-2);(2)8;(3)1+2+3+4;(4)88-1*5;(5)1024*4/8;(6)(20+2)*(6/2);(7)3-3-3;(8)8/(9-9);(9)2*(6+2*(3+6*(6+6)));(10)(((6+6)*6+3)*2+6)*2;二、概要设计1.设定栈的抽象数据类型定义：ADT Stack{数据对象：D={a i|a i∈CharSet,i=1,2,…，n,n≥0} 数据关系：R1={< a i-1,a i >| a i-1, a i∈D,i=2,…，n} 基本操作：InitStack（&S）操作结果：构造一个空栈S。

GetTop (S，&e)初始条件：栈S已存在。

操作结果：若栈S不空，则以e返回栈顶元素。

Push(&S, e)初始条件：栈S已存在。

操作结果：在栈S的栈顶插入新的栈顶元素e。

Pop(&S, &e)初始条件：栈S已存在。

操作结果：删除S的栈顶元素，用e返回其值。

} ADT Stack2.设定运算表达式的抽象数据类型为：ADT EvaluateExpression{数据对象：D={a i| a i为数字及运算符，i=1,2,…，n,n≥0}数据关系：R1={ }基本操作：Precede(a1 , a2)初始条件：字符a1，a2存在。

操作结果：判定运算符的优先级In( d )初始条件：字符d存在。

题目:算术表达式求值演示班级：031021班 姓名：李鑫 学号：03102067 完成日期：2011.12一、 需求分析1. 问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个经典例子。

设计一个程序演示用算符优先法对算术表达式求值的过程。

2. 基本要求：利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值。

3. 测试数据：教科书例3-1的算术表达式3*（7-2）。

二、 概要分析栈的抽象数据类型定义ADT SqStack{数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n ≥0}数据关系：R1={<a i-1,a i >| a i-1,a i ∈D,i=1,2,3,……，n}约定其中a i 端为栈底，a n 端为栈顶。

操作集合：(1)void InitStack1(SqStack1 &S1);//声明栈建立函数(2)void InitStack2(SqStack2 &S2);//声明栈建立函数(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数(4)void Push1(SqStack1 &S1,char e);//声明入栈函数(5)void Push2(SqStack2 &S2,float e);//声明入压栈函数(6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数(7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数(8)char Pop1(SqStack1 &S1);//声明出栈函数(9)float Pop2(SqStack2 &S2);//声明出栈函数(10)char Compare(char m,char n);//声明比较函数(11)float Operate(float a,char rheta,float b);//声明运算函数(12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素(13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素}ADT SqStack三、 详细设计源程序#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct //运算符栈{char *base;char *top;int stacksize;}SqStack1;typedef struct //运算数栈{float *base;float *top;int stacksize;}SqStack2;void InitStack1(SqStack1 &S1);//声明栈建立函数void InitStack2(SqStack2 &S2);//声明栈建立函数void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数void Push1(SqStack1 &S1,char e);//声明入栈函数void Push2(SqStack2 &S2,float e);//声明入压栈函数char GetTop1(SqStack1 &S1);//声明取栈顶元素函数float GetTop2(SqStack2 &S2);//声明取栈顶元素函数char Pop1(SqStack1 &S1);//声明出栈函数float Pop2(SqStack2 &S2);//声明出栈函数char Compare(char m,char n);//声明比较函数float Operate(float a,char rheta,float b);//声明运算函数void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素/*主函数*/void main(){SqStack1 S1;//定义运算符栈SqStack2 S2;//定义运算数栈//freopen("data1.in","r",stdin);//freopen("data1.out","w",stdout);InitStack1(S1);//调用栈建立函数InitStack2(S2);//调用栈建立函数evaluate(S1,S2);//调用确定如何入栈函数cout<<"按任意键结束!"<<endl;}/*运算符栈函数*/void InitStack1(SqStack1 &S1)//构造一个空栈S1{S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char));if(!S1.base)cout<<"存储分配失败！";//存储分配失败S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;}void Push1(SqStack1 &S1,char e)//入栈{if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间{S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base) cout<<"存储分配失败！";else{S1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;}}*S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移}char GetTop1(SqStack1 &S1)//取栈顶元素{char e;if(S1.top==S1.base)cout<<"\n\t\t\t运算符栈已空!\n";else e=*(S1.top-1);return e;}void DispStack1(SqStack1 &S1)//从栈底到栈顶依次输出各元素{char e,*p;if(S1.top==S1.base)cout<<" ";else{p=S1.base;while(p<S1.top){e=*p;p++;cout<<e;}}}char Pop1(SqStack1 &S1)//出栈{char e;if(S1.top==S1.base)cout<<"\n\t\t\t运算符栈已空!\n";e=*(--S1.top);return e;}/*运算数栈函数*/void InitStack2(SqStack2 &S2)//构造一个空栈S2{S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float));if(!S2.base)cout<<"存储分配失败！";//存储分配失败S2.top=S2.base;S2.stacksize=STACK_INIT_SIZE;}void Push2(SqStack2 &S2,float e)//入栈{if(S2.top-S2.base>=S2.stacksize)//栈满，追加存储空间{S2.base=(float*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));if(!S2.base)cout<<"存储分配失败！";else{S2.top=S2.base+S2.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;}}*S2.top=e;S2.top=S2.top+1;//将元素e入栈，指针上移}void DispStack2(SqStack2 &S2)//从栈底到栈顶依次输出各元素{float e,*p;if(S2.top==S2.base)cout<<" ";else{p=S2.base;while(p<S2.top){e=*p;p++;cout<<e;}}}float GetTop2(SqStack2 &S2)//取栈顶元素{float e;if(S2.top==S2.base) cout<<"\n\t\t运算数栈已空!";else e=*(S2.top-1);return e;}float Pop2(SqStack2 &S2)//出栈{float e;if(S2.top==S2.base)cout<<"\n\t\t运算数栈已空!";e=*(--S2.top);return e;}/*确定如何入栈函数*/void evaluate(SqStack1 &S1,SqStack2 &S2){char c;float t,e;int n=0,i=1,j=0,k=0,l=0;char ch[STACK_INIT_SIZE];int s=1;int flag=0,flag2=0;float p1,p2;char ch1;Push1(S1,'#');//将'#'入栈，作为低级运算符cout<<"请输入不含变量的表达式（以#结束!）：\n ";cin>>ch;c=ch[0];cout<<"\n对表达式求值的操作过程如下："<<"\n____________________________________________________________________ ____________\n"<<"步骤\t运算符栈S1\t运算数栈S2\t输入字符\t\t主要操作";while(c!='#'||GetTop1(S1)!='#'){cout<<"\n________________________________________________________________ ________________\n";cout<<i++<<"\t";DispStack1(S1);cout<<"\t\t";DispStack2(S2);cout<<"\t\t";if(flag==1){k--;flag=0;}if(flag2){k+=flag2;flag2=0;}for(l=0;l<k;l++)cout<<' ';for(j=k;ch[j]!='\0';j++)cout<<ch[j];if(ch[k]!='#'&&flag!=1) {k++;flag=0;}as:if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')){//输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数if(!(c=='.')&&n>=0){e=float(c-48);n++;if(n==1)t=e;else if(n>1)t=t*10+e;c=ch[s++];}if(n==-1){e=float(c-48);t=t+e/10;c=ch[s++];}if(c=='.'){n=-1;c=ch[s++];}if((c>='0'&&c<='9')||c=='.'){flag2++;goto as;}if(c<'0'||c>'9'){Push2(S2,t);}cout<<"\t\tPush2(S2,"<<t<<")";}else//输入的是运算符{n=0;//非运算型数据计数器清零switch(Compare(GetTop1(S1),c))//比较运算符的优先级{case '<'://栈顶元素优先级低，则入栈且继续输入Push1(S1,c);cout<<"\t\tPush1(S1,"<<c<<")";c=ch[s++];break;case '='://栈顶元素优先级相等，脱括号并接收下一字符Pop1(S1);cout<<"\t\tPop1(S1)";c=ch[s++];break;case '>'://栈顶元素优先级高，则退栈并将运算结果入栈p1=Pop2(S2);p2=Pop2(S2);ch1=Pop1(S1);Push2(S2,Operate(p2,ch1,p1));cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';flag=1;break;}}}cout<<"\n________________________________________________________________ ________________\n";cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";for(j=0;j<k;j++) cout<<' ';cout<<"#"<<"\t\t"<<"RETURN(GETTOP(S2))";cout<<"\n________________________________________________________________ ________________\n";if(S2.top-1==S2.base)//显示表达式最终结果cout<<"\n表达式的结果为："<<GetTop2(S2)<<endl;else cout<<"\n表达式出错!\n";}char Compare(char m,char n)//运算符的优先级比较{if(n=='+'||n=='-')//输入符号为"+"、"-"{if(m=='('||m=='#')return '<';//栈顶元素为"("、"#",此时栈顶符号优先级低，返回"<"else return '>';//否则，栈顶符号优先级高,返回">"}else if(n=='*'||n=='/')//输入的符号为"*"、"/"{if(m==')'||m=='*'||m=='/')return '>';//栈顶元素为")"、"*"、"/",此时栈顶符号优先级高，返回">"else return '<';//否则，栈顶符号优先级低,返回"<"}else if(n=='(')return'<';//输入的符号为"(",则直接返回"<"else if(n==')')//输入的符号为")"{if(m=='(')return'=';//栈顶元素为"(",此时优先级同，返回"="else return '>';//否则，栈顶符号优先级高,返回">"}else //输入符号为其他{if(m=='#')return'=';//栈顶元素为"#",此时优先级同，返回"="else return '>';//否则，栈顶符号优先级高,返回">"}}float Operate(float a,char theta,float b)//运算函数{float tmp=0;if (theta=='+')tmp=a+b;//从运算符栈取出的符号为"+"，则运算数栈的两元素相加，并返回else if(theta=='-')tmp=a-b;//从运算符栈取出的符号为"-"，则运算数栈的两元素相减，并返回else if(theta=='*')tmp=a*b;//从运算符栈取出的符号为"*"，则运算数栈的两元素相乘，并返回else if(theta=='/') //从运算符栈取出的符号为"/"，则运算数栈的两元素相除，并返回{if(b==0) cout<<"\n表达式出错!除数不能为0!\n";else tmp=a/b;}return tmp;}四.调试分析五、总结与心得经过两个星期的实际操作和搜索相关资料，终于让我完成了任务。

课前讲解—表达式求值一、表达式求值的规则表达式求值是程序设计语言编译中的一个基本问题。

它的实现就是对“栈”的典型应用。

首先了解算术四则运算的运算规则：（1）先乘除，后加减。

（2）从左到右计算（3）先算括号内，再算括号外因此，下面这个算数表达式的计算顺序应为：4+2*3 - 10/5= 4 + 6 - 10 / 5= 10 - 10 / 5= 10 - 2= 8任何一个表达式都由操作数（operand）、运算符（operator）和界定符组成：●操作数即可以是常量，也可以是被说明为变量或常量的标识符。

●运算符可以分为算术运算，关系运算和逻辑运算符。

●界定符有左右括号和结束符等。

为了叙述的简洁，我们仅讨论简单算数表达式的求值问题，这种表达式只包含加、减、乘、除等四种算术运算。

需要时，不难把它推广到更一般的表达式上。

二、运算符优先级对于连个相继出现的操作符θ1和θ2有三种关系：θ1<θ2θ1的优先级低于θ2θ1 =θ2θ1的优先级等于θ2θ1>θ2θ1的优先级高于θ2由此可以列出“+-*/”之间的优先级。

如下表：加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当θ1=θ2 ，令θ1>θ2为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。

“（”=“）”当一对括号相遇时表示括号内已运算完成。

“）”和“（”、“#”和“(”、“(”和“#”无法相继出现，如果出现则表达式出现语法错误。

(实现时，可以用0存储) 这个表如何理解呢？例如：a+b+c，这里有两个运算符，运算符θ1为+，运算符θ2也为+ ，查上表，得到“>”的关系，那么意味着先计算前面的+号，也就是先算a+b，得到结果后，再考虑算后面的表达式。

三、算法思路为实现优先算法，可以使用两个工作栈，一个是OPTR，用于寄存运算符，一个是OPND，用于寄存操作数和运算结果。

算法的基本思想是：1. 首先置操作数栈为空栈，表达式起始符“#”为栈底元素。