数据结构 表达式求值（中缀）实验报告

1、?算法与数据结构?课程设计报告 题目名称 表达式求值 学 号 姓 名 指导教师 日 期 一 设计题目 表达式求值中缀二 需求分析1. 问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行，在程序设计时，借助栈实现。2. 表达式求值这个程序，主要利用栈和数组，把运算的先后步骤进行分析并实现简单的运算，以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。利用的算符优先关系，实现对算术四那么运算的求值，在求值中运用栈、运算栈、输入字符和主要操作的变化过程。该程序相当于一个简单的计算机计算

2、程序，只进行简单的加减乘除和带括号的四那么运算。三 概要设计1、根本思想中缀表达式求值要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四那么运算的规那么即：（1） 先乘除后加减；（2） 从左到右计算；（3） 先括号内，后括号外。下表定义的运算符之间的关系:ba+-*/#+>><<<>>_>><<<>>*>>>><>>/>>>><>>(<<<<<

3、;=)>>>>>>#<<<<<= 为了实现运算符有限算法，在程序中使用了两个工作栈。分别是：运算符栈OPTR,操作数栈OPND.根本思想：（1） 首先置操作数栈为空栈，表达式起始符“#为运算符栈的栈底元素；（2） 依次读入表达式中每个字符，假设是操作数那么进OPND栈，假设是运算符那么和OPTR栈得栈顶运算符比拟优先级后作相应操作。假设大于栈顶元素优先级那么如栈，假设小于栈顶元素优先级那么退出和OPND得操作数进行计算，并把计算结果如OPND栈。直至整个表达式求值完毕即OPND栈的栈顶元素和当前读入的字符均为“#。2、 栈的抽象

4、数据类型的定义：ADT Stack 数据对象：D=ai| aiIntegerSet，i=1，2，n，n0数据关系：R1=ai-1，ai|ai-1， aiD， i=1，2，n 约定an端为栈顶，ai端为栈底 根本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmptyS 初始条件：栈S已存在。 操作结果：假设栈S为空栈，那么返回True，否那么返回False。 StackLengthS

5、 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 GetTopS，&e 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push&S，e 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop&S，&e 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverseS，visit 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit。一旦visit失败，那么操作失败。ADT Stack3、根本操作我选择的是中缀表达式求值，在转换和计算中

6、主要用到了以下几个函数1) char Precede(char t1, char t2)作用：判断运算符t1和t2的优先关系。如：case '+': case '-': if(t1='('| t1='#') f='<'/t1<t2elsef='>'/t1>t2break; 2bool IsOperator(char c)作用：判断c是否为7种运算符之一bool IsOperator(char c)/判断c是否为7种运算符之一switch(c)case '+':

7、case '-':case '*':case '/':case '(':case ')':case '#': return true;default: return false;3int Operate(int a, char oper, int b)作用：int Operate(int a, char oper, int b)switch(oper)case '+':return a+b;case '-':return a-b;case '*':re

8、turn a*b;default:break;return a/b; 4int EvaluateExpression()作用：中缀表达式求值的算法int EvaluateExpression()stack<int> OPTR, OPND;/设置操作数栈和操作符栈int a,b,d,x;char c;OPTR.push('#');c=getchar();x=OPTR.top();while(c!='#'|x!='#')if(IsOperator(c)switch(Precede(x,c)case'<':OPTR.p

9、ush(c);c = getchar();break;case'=':x=OPTR.top();OPTR.pop();c = getchar();break;case'>':x=OPTR.top();OPTR.pop();b=OPND.top();OPND.pop();a=OPND.top();OPND.pop();OPND.push(Operate(a,x,b);else if(c>='0'&&c<='9')d=0;while(c>='0'&&c<=&

10、#39;9')d = d*10+c-'0'c = getchar();OPND.push(d);elsecout << "出现非法字符" << endl;exit( 0 );x=OPTR.top();x=OPND.top();if(OPND.empty()cout << "表达式不正确#" << endl;exit( 0 );return x;四 详细设计#include <iostream>#include <stack>using namespace st

11、d;int EvaluateExpression();int main()cout << "请输入算术表达式,负数要用(0-正数)表示n"cout << EvaluateExpression() << endl;return 0;char Precede(char t1, char t2)/判断t1,t2两符号的优先关系('#'用'#'代替)char f;switch(t2)case '+':case '-':if(t1='('| t1='#'

12、)f='<'/t1<t2elsef='>'/t1>t2break;case '*':case '/':if(t1='*'|t1='/'|t1=')')f='>'/t1>t2elsef='<'/t1<t2break;case '(':if(t1=')')cout << "括号不匹配" << endl;exit( 0 );elsef=

13、'<'/t1<t2break;case ')':switch(t1)case '(': f = '=' /t1=t2break;case '#': cout << "缺乏左括号" << endl;exit( 0 );default: f='>'/t1>t2break;case '#': switch(t1)case '#': f= '='/t1=t2break;case '(&

14、#39;:cout << "缺乏右括号" << endl;exit( 0 );default: f='>'/t1>t2return f;bool IsOperator(char c)/判断c是否为7种运算符之一switch(c)case '+':case '-':case '*':case '/':case '(':case ')':case '#': return true;default: return fa

15、lse;int Operate(int a, char oper, int b)/做死者运算a theta b,返回运算结果switch(oper)case '+':return a+b;case '-':return a-b;case '*':return a*b;default:break;return a/b;int EvaluateExpression()stack<int> OPTR, OPND;/设置操作数栈和操作符栈int a,b,d,x;char c;OPTR.push('#');c=getchar()

16、;x=OPTR.top();while(c!='#'|x!='#')if(IsOperator(c)switch(Precede(x,c)case'<':OPTR.push(c);c = getchar();break;case'=':x=OPTR.top();OPTR.pop();c = getchar();break;case'>':x=OPTR.top();OPTR.pop();b=OPND.top();OPND.pop();a=OPND.top();OPND.pop();OPND.push(Op

17、erate(a,x,b);else if(c>='0'&&c<='9')d=0;while(c>='0'&&c<='9')d = d*10+c-'0'c = getchar();OPND.push(d);elsecout << "出现非法字符" << endl;exit( 0 );x=OPTR.top();x=OPND.top();if(OPND.empty()cout << "表达式不正确#" << endl;exit( 0 );return x; while(i<j);ri=r0;c+;q(r，s，j-1);q(r，j+1，t);六 测试结果 七 附录和设计心得体会这次的课程设计，表达式求值。我首先选择的是后缀表达式求值，将中缀转换成后缀并计算。后来又采用了栈的标准库，但只因为后缀比中缀难度大一些，并且标准库的算法较为复杂，我选择的方法