实验报告11.8.数据结构

1、数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业： 网络工程 班 级： 13网络1班 指导教师： 吴亚峰 姓 名： 霍国豪 学 号： 2 13 / 15文档可自由编辑打印目 录一、设计思想.01二、算法流程图.02三、源代码.04四、运行结果.12五、遇到的问题及解决.13六、心得体会.14一、设计思想1.中缀变后缀表达式的基本思路：使用一个栈和一个数组（栈是运算符栈，数组是用来存放后缀表达式）用于表达式的转换(1) 定义一个字符数组，并输入一个中缀表达式。然后从中缀表达式中从左往右依次读入各个字符。(2) 如果是数字字符，则直接将它们写入后缀表达式中即队列中。(3) 如果遇到的

2、是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。(4) 如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。(5) 重复上述步骤直到缀表达式的结束符标记“#“，弹出栈中所有元素并放入后缀表达，转换结束。2.

3、后缀表达式的计算的基本思路：使用一个栈和一个数组（栈是运算对象，数组是用来存放后缀表达式）用于表达式的计算。从左到右遍历表达式的每一个数字和符号，遇到数字就进栈，遇到运算符号，就将栈顶的两个数字出栈，进行计算，运算结果进栈，直到获得最终结果结束。3.中缀表达式求值要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：a先乘除后加减； b从左到右计算；c 先括号内，后括号外。下表定义的运算符之间的关系: ba+-*/（）#+_*/(#= 为了实现运算符有限算法，在程序中使用了两个工作栈。分别是：运算符栈OPTR,操作数栈OPN

4、D.基本思想：（1） 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2） 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。若大于栈顶元素优先级则如栈，若小于栈顶元素优先级则退出和OPND得操作数进行计算，并把计算结果如OPND栈。直至整个表达式求值完毕（即OPND栈的栈顶元素和当前读入的字符均为“#”）。二、算法流程图1中缀变后缀算法流程图图2后缀表达式计算算法流程图图3中缀表达式计算算法流程三、源代码下面给出的是定义Stack.h文件的源代码：/stack.h#ifndef STACK_H_#define ST

5、ACK_H_class Stackprivate:int top; /定义整形变量enum MAXLEN = 100;/定义长度为100int arrayMAXLEN;/数组public:Stack()top = 0;bool empty();bool full();bool pop(int & e);bool push(int e);#endif下面给出的是中缀表达式转化为后缀表达式并求值算法实现的程序的源代码： #include #include #include #include using namespace std;class Expression public: Expressio

6、n(); static int Compare(char op); static void ITP(string expression);/中缀转化为后缀 static int Clculate();/计算表达式 static vector sResult;/创建矢量字符串 static stack snum; /创建栈的整形变量 ; vector Expression:sResult;/变量sResult所用域为Expression stack Expression:snum; Expression:Expression() sResult.reserve(100);/字符串长度初始值为10

7、0 int Expression:Compare(char op) /比较字符的优先级 int Level = 0; switch(op) case +:case -: Level = 1;break; case *:case /: Level = 2; break; default: break; return Level; void Expression:ITP(string expression) /把中缀表达式转换为后缀表达式 string:size_type nCount = expression.length(); /字符串长度赋给nCount string:size_type i

8、ndex = 0; /初始化索引 stack stmp; /创建stmp是一个栈的对象 bool flag = false;/标志位 stmp.push(); /把压入栈stmp while( index nCount) /索引小于字符串长度 if( expressionindex = () stmp.push(); index+; else if( expressionindex = ) while( stmp.top() != () sResult.push_back( string(1, stmp.top() );/把stmp顶元素压入矢量sResult stmp.pop(); /whi

9、le stmp.pop(); index+; / else if else if( expressionindex = + | expressionindex = - | expressionindex = * | expressionindex = / ) if( expressionindex = - | expressionindex = + ) if(index = 0)/index指向第一个数 index +; flag = true; /标志位为true /if else if( expressionindex-1 = ( )/如果主索引的前一个数是（ index+; flag =

10、 true; /标志位为true /else if else while( Compare( expressionindex ) = Compare( stmp.top() ) /索引指向字符优先级小于stmp栈顶优先级 sResult.push_back(string(1, stmp.top() ); /把stmp顶元素压入矢量sResult stmp.pop(); /while stmp.push( expressionindex ); / 索引指向字符压入stmp index+; /else /if else while( Compare( expressionindex ) = 0 &

11、 expressionindex = 9) temp += expressionindex; index +; /while sResult.push_back( temp ); /把temp元素压入矢量sResult /else /while while(stmp.top() != ) if(stmp.top() = () cout Error in expression endl; exit(-1); sResult.push_back( string(1, stmp.top() ); /把stmp顶元素压入矢量sResult stmp.pop(); / 中缀转化为后缀 int Expre

12、ssion:Clculate() size_t index = 0;/初始化索引为0 int num1 = 0, num2 = 0; for(index = 0; index 1) & (oper0 = + | oper0 = -) ) snum.push( atoi(sResultindex.c_str() );/矢量字符转换 else switch(oper0) case +: num1 = snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); snum.push( num2 + num1); break; case -: num1

13、= snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); snum.push( num2 - num1); break; case *: num1 = snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); snum.push( num2 * num1); break; case /: num1 = snum.top(); snum.pop(); num2 = snum.top(); snum.pop(); if(num1 = 0) cerr Expression worng! end

14、l; exit(-1); snum.push( num2 / num1); break; default: snum.push( atoi(sResultindex.c_str() ); /矢量字符转换 break; /swith /while int result = snum.top(); 栈snum顶元素赋给整形变量result snum.pop(); return result; int main() string Input; cout please input the expression (Enter key for end) Input;/扫描输入字符串 Expression:

15、ITP(Input);/中缀表达式转化为后缀 cout 后缀表达式: endl; for(size_t index = 0; index Expression:sResult.size(); +index) cout Expression:sResultindex ; cout endl; cout 计算结果: endl; cout Expression:Clculate() endl;/输出计算结果 return 0;下面给出的是中缀表达式求值算法实现的程序的源代码：#include #include using namespace std;char Precede(char t1, cha

16、r t2)/判断t1,t2两符号的优先关系(#用#代替)char f;switch(t2) /t1与t2比较case +:case -:if(t1=(| t1=#)f=;/t1;/t1t2break;case *:case /:if(t1=*|t1=/|t1=)f=;/t1t2elsef=;/t1t2break;case (:if(t1=)cout 括号不匹配 endl;exit( 0 );elsef=;/t1t2break;case ):switch(t1)/与t1比较优先级case (: f = =; /t1=t2break;case #: cout 缺乏左括号 ;/t1t2break;c

17、ase #: switch(t1) /与t1比较优先级case #: f= =;/t1=t2break;case (:cout 缺乏右括号 ;/t1t2return f;bool IsOperator(char c)/判断c是否为7种运算符之一switch(c)case +:case -:case *:case /:case (:case ):case #:return true;default: return false;int Operate(int a, char oper, int b)/做运算a theta b,返回运算结果switch(oper)case +:return a+b;

18、case -:return a-b;case *:return a*b;case /: if(b=0) cout Expression worng! endl; return a/b;default:break;int EvaluateExpression()stack OPTR, OPND;/设置操作数栈和操作符栈int a,b,d,x;/定义整形变量a,b,d,xchar c;/ 定义字符串变量cOPTR.push(#);/#压入OPTR栈c=getchar();/当前字符用C表示x=OPTR.top();/OPTR栈顶用X表示while(c!=#|x!=#)/ if(IsOperator

19、(c) /判断c是否为7种运算符之一switch(Precede(x,c) 判断x,c两符号的优先关系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=0&c=9)/字符C大于0且小于9d = d*10+c-0;/字符串转化为相应的值c = getchar();OPND.push(d);elsecout 出现非法字符 endl;exit( 0 );x=OPTR.top();x=OPND.to

20、p();if(OPND.empty()cout 表达式不正确# endl;exit( 0 );/退出return x;int main()cout 请输入算术表达式,负数要用(0-正数)表示，以#号结束n;cout 结果是：EvaluateExpression() endl;return 0;四、运行结果运行程序，输入中缀表达式结束后，敲回车键显示后缀表达式和计算结果，如图4所示：图4 中缀变后缀表达式求值的运行结果图运行程序，输入中缀表达式以#结束后，敲回车键显示计算结果，如图5所示：图5 中缀表达式的运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 如何将一位数变成两位数解决方案：在各数字之间用空格隔开，并且添加语句，主要思想是当第一个数字进栈后，判断下一个进栈的元素，若是数字元素则进栈，若是运算符，则加空格将其与其他数字分开。l 生成后缀表达式时，如何将数和字符存放在一个字符串中解决方案：不把字符数组的数字都截取出来，而是把数字进行一个