《带括号的表达式求值》课程设计报告

1、数据结构与算法分析课程设计报告课题名称：带括号的算术表达式求值课题负责人名（学号）：0743111298同组成员名单（角色）： 戴维指导教师：评阅成绩：评阅意见：提交报告时间：200 年 月日课程名称：数据结构学生姓名：戴维学生学号：0743111298带括号的算术表达式求值软件工程专业学生戴维指导老师朱宏-25-一、实验一：带括号的算术表达式求值二、实验的目的和要求：1 .采用算符优先数算法，能正确求值表达式；2 .熟练掌握栈的应用；3 .熟练掌握计算机系统的基本操作方法，了解如何编辑、编译、链接和运行个C+程序；4 .上机调试程序，掌握查错、排错使程序能正确运行。三、实验的环境 ：1 .硬

2、件环境：Intel(R) Celeron(R)M CPU520 1.60GHz1.60GHz , 0.99Gb内存2 .软件环环境：操作系统:Microsoft Windows XP版本2002Professinal编译系统版本：MicroSoft Visual C+6.0,编辑软件特点等。包括操作系统，编译系统的版本的特点 四、算法描述：对于带有括号的算术表达式有以下的运算法则:1 .先乘方，再乘除，最后加减。2 .同级运算从左到右。3 .先括号内，再括号外。而运算符号的优先级别如下表所示：运算符=()+ -* / %A优先级12345具体实现如下：1 .先建立两个堆栈，一个是操作符堆栈，一

3、个为操作数堆栈。并且将这两个堆栈先清空，然后在操作符号堆栈当中放入一个“="，以便在后面方便判断表达式是否结束。2 .从输入流当中读取一个字符，循环执行下面的操作：去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“="并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数， 并且将操作数加入到操作数堆栈当中，继续读入下一个字符。如果当前字符是操作符就进行下面的操作：.如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。如果当前字符和操作

4、符的栈顶元素不匹配，例如当前字符是“("，而栈顶字符“)”，显示错误信息。如果操作符栈的栈顶元素是“(”并且当前字符是“)”，则从操作符栈当中取出，去掉括号，然后继续读入下面的字符。如果当前字符是“(”，或者操作符栈顶元素的优先级别比当前字符低，则将当前字符放入到操作符栈当中。继续读入下一个字符。如果操作符栈顶元素的优先级别等于或者大于当前字符的优先级别，那么就取出操作数栈的 RIGHT和LEFT元素，从操作符栈当中取出OP,然后进行操作(LEFT) OP ( RIGHT),结果进入到操作数栈当中五、源程序清单Calculator.h:template<class Data_e

5、lement>class Calculatorprivate :Stack<Data_element> opnd ;/建立一个操作数的栈Stack<char> optr ;/建立一个操作符的栈bool GetTwoOperands(double &left ,double &right);/从操作数栈当中取出最上面的两个数字bool DoOperator(char op);/ run the function "left op right"bool IsOperator(char ch);/判断传入的字符是不是一个操作符void

6、 GetChar(char &ch);/从输入流当中读入一个字符int isp(char op); 堆栈外优先数int icp(char op); 堆栈内优先数public :void Run() ; /运行函数;template<class Data_element>void Calculator<Data_element>:Run()optr.clear() ; /将操作符栈的所有元素清空opnd.clear() ; /将操作数栈的所有元素清空optr.push('=') ; /先在操作符栈中传入一个='号，为了能够更好的判断运算是否

7、已经结束/'='时，运算结束char ch ;/char priorChar ; /char optrTop ; /Data_element operand ;char op = '0'/管GetChar(ch); /optr.top(optrTop); /当从外面的读入的字符是'='并且栈顶符号也是临时的一个字符前一个字符操作符栈的栈顶元素/需要被操作的操作数定义一个操作数为0',便于操作小数的运得到一个字符得到操作符栈的栈顶元素if(optr.top(optrTop片underflow)/如果操作符号栈为空，抛出错误信息cout<

8、;<"表达式有错！"<<endl;return;while(optrTop!='='|ch!='=')/通过判断当前的字符和栈顶的字符其中一个不为“=”的时候,/表示现在运算还没有结束，所以进行下面的操作if(isdigit(ch)11ch='.')/如果当先的字符是一个数字或者当前字符是小数点，那么把该 字符放回到输入流当中，/再把该操作数读入，并且放到操作数栈当中去，把前一个字符赋为0,然后再继续读入字符cin.putback(ch);cin>>operand;opnd.push(operan

9、d);priorChar='0'GetChar(ch);else if(!IsOperator(ch)/除了数字以外应该只有操作符，现在进行判断，如果不是数字, 不是小数点，/也不是操作符号，说明输入有错误，打印错误消息，再不断的 读入字符，直到读到表达式结束cout<<"表达式中出现非法字符!"<<endl;while(cin>>ch,ch!='=');return;elseif(priorChar='='|priorChar='(')&&(ch='

10、+'|ch='-')opnd.push(0);if(isp(optrTop)<icp(ch)/如果操作符栈顶元素的优先级别小于当前操作符号的优先 级别就把当前的/字符放到操作符栈当中，将当前字符赋值给前一个字符，再读入下一个字符optr.push(ch);priorChar=ch;GetChar(ch);else if(isp(optrTop)>icp(ch)/如果操作符栈顶元素的优先级别大于当前操作符号，/删除操作符栈顶元素，在判断OP是不是操作符号，如果不是就返回optr.top(op);optr.pop();if(!DoOperator(op)retu

11、rn;else if(isp(optrTop)=icp(ch)&&ch=')')/如果栈内操作符和栈外操作符的优先级别一样的，并且当 前的字符为等号的时候optr.pop();priorChar=')'GetChar(ch);；if(optr.top(optrTop)=underflow)/如果操作符栈为空的话，输出错误消息cout<<"表达式有错！"<<endl;return;；if(opnd.top(operand)=underflow | optr.pop() = underflow)/如果操作数

12、字栈为空或者是操作符号在删除了栈顶元素厚为空，输出错误信息cout<<"表达式有错!"<<endl;return;else/删除操作数栈的栈顶元素，如果再删除操作符栈栈顶元素成功删除或者能够成功删除/操作数栈的栈顶元素，输出错误信息opnd.pop();if (opnd.pop()=success | optr.pop()=success)cout<<"表达式有错！"<<endl;return;cout<<operand<<endl;return;；template<class

13、 Data_element>int Calculator<Data_element>:isp(char op)/栈外操作符的优先级判断int result;switch(op)case '=':result=0;break;case '(':result=1;break;case '"result=7;break;case '*':case '/':case '%':result=5;break;case '+':case '-':result=3

14、;break;case ')':result=8;return result;； template<class Data_element>/操作符栈内优先级的判断int Calculator<Data_element>:icp(char op) int result;switch(op)case '=':result=0;break;case '(':result=8;break;case '"result=6;break;case case '/':case '%':re

15、sult=4;break;case '+':case '-':result=2;break;case ')':result=1;return result;；template<class Data_element>bool Calculator<Data_element>:GetTwoOperands(double &x,double &y)/从操作数栈当中得到两个数字，如果操作数字栈或者操作符栈的元素少于两 个的时候输出错误信息if(opnd.empty()cout<<"表达式有错！

16、"<<endl;return false;opnd.top(y);opnd.pop();if(opnd.empty()cout<<"表达式有错!"<<endl;return false;opnd.top(x);opnd.pop();return true;；template<class Data_element>bool Calculator<Data_element>:DoOperator(char op)/判断符号，进行相应的操作Data_element x,y;bool result=GetTwoO

17、perands(x,y);if(result=true)switch(op)case '+':opnd.push(x+y);break;case '-':opnd.push(x-y);break;case '*':opnd.push(x*y);break;case '/':if(y=0)cout<<"除数为零！"<<endl;return false;opnd.push(x/y);break;case '%':if(long)y=0) cout<<"

18、除数为零！"<<endl; return false;opnd.push(long)x % (long)y);break;case '"opnd.push(pow(x,y);return true;else return false;template<class ElemType>void Calculator<ElemType>:GetChar(char &ch)/从输入流当中读入字符cin>>ch;while(ch=' '11ch='n') cin>>ch;tem

19、plate<class Data_element>bool Calculator<Data element>:IsOperator(char ch)/判断输入的字符是不是操作符if(ch='='|ch='('|ch='A'|ch='*'|ch='/'11ch='%'11ch='+'|ch='-'|ch=')')return true;elsereturn false;；LK_STACK.h:template<class N

20、ode_entry>struct Node Node_entry entry; /定义一个结点元素Node<Node_entry> *next; /定义一个结点指针Node();/无参数构造函数Node(Node_entry item, Node<Node_entry> *add_on = NULL); 含参构造函数;template<class Stack_entry> class Stack public:Stack(); /无参构造函数bool empty() const; /判断堆栈是不是为空Error_code push(const Stac

21、k_entry &item); / Error_code pop();/Error code top(Stack entry &item) const; /往堆栈当中传入元素删除堆栈的栈顶元素得到堆栈的栈顶元素void clear();/清空堆栈的所有元素Stack();/析构函数Stack(const Stack<Stack_entry> &original); 有参数构造函数void operator =(const Stack<Stack_entry> &original); /操作符重载protected:Node<Stac

22、k_entry> *top_node; /定义一个指针； template<class Node_entry> Node<Node_entry>:Node()构造函数 next = NULL;template<class Node_entry>Node<Node_entry>:Node(Node_entry item, Node<Node_entry> *add_on)/含参数构造函数entry = item;next = add_on;template<class Stack_entry>Stack<Stac

23、k_entry>:Stack()/堆栈的构造函数 top_node=NULL;template<class Stack_entry>bool Stack<Stack entry>:empty() const/判断堆栈是不是为空if(top_node=NULL)return true;elsereturn false;template<class Stack_entry>Error_code Stack<Stack_entry>:push(const Stack_entry &item)/往堆栈中添加元素Node<Stack_e

24、ntry> *new_top = new Node<Stack_entry>(item, top_node);if (new_top = NULL) return overflow;top_node = new_top;return success;template<class Stack_entry>Error_code Stack<Stack_entry>:pop()/删除堆栈的栈顶元素Node<Stack_entry> *old_top = top_node;if (top_node = NULL) return underflow;

25、top_node = old_top->next;delete old_top;return success;template<class Stack_entry>Error code Stack<Stack entry>:top(Stack entry &item) const/得到堆栈的栈顶元素Error_code result;if(empty()return underflow;elseitem=top_node->entry;return success;template<class Stack_entry>void Stack

26、<Stack_entry>:clear()/清空整个堆栈while (!empty()POP()；template<class Stack_entry>Stack<Stack_entry>:Stack()/析构函数clear();Utility.h:#include<string.h> /standard string operations#include<iostream.h> /standard iostream operations#include<limits.h> /numeric limits#include&

27、lt;math.h>/mathematical functions#include<fstream.h> /file input and output#include<ctype.h>/character classification#include<time.h>/date and time function#include<conio.h>/con input and outputenum Error_codesuccess,fail,underflow,overflow; /enum boolfalse,true;Calculator

28、.cpp:#include"Utility.h"#include"LK_STACK.H"#include"Calculator.h"void main()Calculator<double> s;char iscontinue='Y'while(iscontinue='Y') cout<<"输入表达式(以等号"="结束):"<<endl;s.Run();cout<<"是否继续(Y/N)?"cin&

29、gt;>iscontinue;iscontinue=toupper(iscontinue);六、运行结果：1. 一般的整数操作：3+4*5/2=13输入表达式以等号限*吉束八3+4«5/2=13是否继续y/N>?2.小数的计算 425*1+3.25/5=4.93.乘方操作：4人4=2564.取模运算:7%3=1"D:VC+6_ OByProjectsCalculator47x3 =1是否继续<丫>?5.负数运算：（-5） *6/2=156.分母为零的检验:7. 一次程序结束后继续下一次:Q38. 一次程序结束后退出程序:% "D:VC+6.

30、 OXlTProjectsVCalculator：3/0=除数为零？是否继续Y/N?y输入表达式以等号"结束：4/2 =2是否继续"椁?村Press any key to continue七、实验运行情况分析（包括算法、运行结果、运行环境等问题的讨论（一）算法分析：对于带有括号的算术表达式有以下的运算法则：1 .先乘方，再乘除，最后加减。2 .同级运算从左到右。3 .先括号内，再括号外。而运算符号的优先级别如下表所示：运算符=()+ -* / %A优先级12345具体实现如下：1 .先建立两个堆栈，一个是操作符堆栈，一个为操作数堆栈。并且将这两个堆栈先清空，然后在操作符号堆

31、栈当中放入一个“="，以便在后面方便判断表达式是否结束。2 .从输入流当中读取一个字符，循环执行下面的操作：去出操作符号堆栈的栈顶元素，如果栈顶元素是不是“="并且如果当前的字符也是“=”的时候，那么表示表达式已经结束了，当前操作数堆栈的栈顶元素就是表达式的值。如果当前字符不是操作符，就将当前字符放回到输入流当中，读取操作数， 并且将操作数加入到操作数堆栈当中，继续读入下一个字符。如果当前字符是操作符就进行下面的操作：.如果当前字符不是“+”或者“-”，则在当前字符前面加一个“0”放入到操作数栈当中。如果当前字符和操作符的栈顶元素不匹配，例如当前字符是“（"，而栈

32、顶字符“）”，显示错误信息。如果操作符栈的栈顶元素是“（”并且当前字符是“）”，则从操作符栈当中取出，去掉括号，然后继续读入下面的字符。如果当前字符是“（”，或者操作符栈顶元素的优先级别比当前字符低，则将当前字符放入到操作符栈当中。继续读入下一个字符。如果操作符栈顶元素的优先级别等于或者大于当前字符的优先级别，那么就取出操作数栈的 RIGHT和LEFT元素，从操作符栈当中取出OP,然后进行操作（LEFT） OP （ RIGHT）,结果进入到操作数栈当中（二）运行结果分析：1 .对一般的整数，小数进行操作时，只要先输入一个准确的表达式子即可，当计算结束后，屏幕上会显示计算结果，并且征求是否还要继续进行运算。SIm 3小数运算:乘方运算:取模运算:负数运算:e -D:VC-H-6. 0IyProjectsCaC-5>«6/