实验4栈的应用

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验4栈的应用学生姓名： 班 级： 班内序号： 15学 号： 日 期： 2015年12月28日1 实验要求表达式求值是程序设计语言编译中最近本的问题，它要求把一个表达式翻译成能够直接求值的序列。例如用户输入字符串“14+(13-2)*2-11*5)*2”，程序可以自动计算得到最终的结果。在这里，我们将问题简化，假定算数表达式的值均为非负整数常数，不包含变量、小数和字符常量。试设计一个算术四则运算表达式求值的简单计算器。基本要求：1、 操作数均为非负整数常数，操作符仅为+、-、*、/、（和）；2、 编写main函数进行测试。2.1 存储结

2、构 顺序栈： int型数字栈 char型字符栈/*-+121 Top=-1 Top=-1 2.2 关键算法分析1.判断输入字符是否为运算符int IsOpr(char c) /判断输入字符是否为运算符 if (c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='#') return 1; else return 0; 2. 判断字符的优先级将判断条件分为多种情况:如果栈顶元素是+、-的情况与刚取得的字符大小比较如果是+、-则返回>，如果是*、/则返回&

3、lt;，如果是左括号则返回<，如果是右括号则返回>，其他情况则返回>如果栈顶元素是*、/的情况与刚取得的字符大小比较如果是+、-则返回>，如果是*、/则返回>，如果是左括号则返回<，如果是右括号则返回>，其他情况则返回>如果栈顶元素是（的情况与刚取得的字符大小比较，除了右括号是=以外，其他都是返回<如果栈顶元素是)的情况与刚取得的字符大小比较，都是返回>如果栈顶元素是#的情况与刚取得的字符大小比较，除了#返回=以外，其他都是返回>这个方法即将中序表达式转换为后缀表达式char Precede(char s,char c) /判断

4、字符的优先级 switch(s) case '+': case '-': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '<' else if(c='(') return '<' else if(c=')') return '>' else return '>' break; case '

5、;*': case '/': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '>' else if(c='(') return '<' else if(c=')') return '>' else return '>' break; case '(': if(c=')')

6、 return '=' else return '<' break; case ')': return '>' break; case '#': if(c='#') return '=' else return '<' break; 3.计算int Operate(int x,char opr,int y) /计算 int result; switch (opr) case '+': result = x + y; break; ca

7、se '-': result = x - y; break; case '*': result = x * y; break; case '/': result = x / y; break; return result; 3. 程序运行结果程序运行图开始 定义数字栈S1符号栈S2输入字符串S读取字符SjSj!=0 N YSj是计算符号？ NS1.push(sj) Y与栈顶符号比较优先级结束循环J+输出S1.POP><Theta=S2.pop ( )=S2.pop ( )S2.push(sj)结束a=S1.pop ( )J+J+b=S

8、1.pop ( )计算（a，theta，b）S1.push(结果)源代码:#include<iostream>#include<string>using namespace std;const int Max=128;template<class T>class Stackpublic:Stack()top=-1;void Push(T x); /入栈T Pop(); /进栈T GetTop(); /取栈顶元素int isEmpty(); /判断栈是否为空private:int top;T dataMax;template<class T>voi

9、d Stack<T>:Push(T x)if(top>=Max-1) throw "上溢"top +;datatop=x;template<class T>T Stack<T>:Pop()if(isEmpty() throw "下溢"top-;return datatop+1;template<class T>T Stack<T>:GetTop()if(isEmpty()throw "下溢"return datatop;template<class T>in

10、t Stack<T>:isEmpty()if(top=-1)return 1;elsereturn 0;int IsOpr(char c); /判断输入字符是否为运算符 char Precede(char s,char c); /判断字符的优先级 int Operate(int x,char opr,int y); /计算 int IsOpr(char c) /判断输入字符是否为运算符 if (c='+'|c='-'|c='*'|c='/'|c='('|c=')'|c='#

11、9;) return 1; else return 0; char Precede(char s,char c) /判断字符的优先级 switch(s) case '+': case '-': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '<' else if(c='(') return '<' else if(c=')') retur

12、n '>' else return '>' break; case '*': case '/': if(c='+'|c='-') return '>' else if (c='*'|c='/') return '>' else if(c='(') return '<' else if(c=')') return '>' else retu

13、rn '>' break; case '(': if(c=')') return '=' else return '<' break; case ')': return '>' break; case '#': if(c='#') return '=' else return '<' break; int Operate(int x,char opr,int y) /计算 int result;

14、switch (opr) case '+': result = x + y; break; case '-': result = x - y; break; case '*': result = x * y; break; case '/': result = x / y; break; return result; void main()Stack<int> s1;/运算数栈Stack<char> s2;/运算符栈s2.Push('#');int a,b,result,i,n,j=0; c

15、har theta;string s;cout<<"请输入算式,出入#号结束"<<endl;cin>>s;while(sj!='0')if(!IsOpr(sj) /是运算数的情况 i=sj-'0'/将字符型转为整型j+; while(!IsOpr(sj) /使得可以输入几位数 n=sj-'0'i=i*10+n;j+; s1.Push(i); else switch(Precede(s2.GetTop(),sj) /比较栈顶运算符和刚输入运算符的优先级 case '<':

16、 s2.Push(sj); j+; break; case '=': theta=s2.Pop(); j+;break; case '>': theta=s2.Pop(); b=s1.Pop(); a=s1.Pop(); result=Operate(a,theta,b); s1.Push(result); break; cout<<s1.GetTop()<<endl;4. 总结这次的实验选了题目四，用栈做计算器，在写之前一直觉得这是一个很简单的实验，主要是在网上看到栈做计算器的想，所以觉得应该没什么难度，但是真正做起来才发现难上加难。尤其是在做中缀转成后缀的时候，其实这个本来有个想法是用树来做，中缀表达式是树的中序遍历（当然要注意运算符的优先级），而后缀表达式是树的后序遍历，最初的想法是将中缀表达式转化成为树，然后对树做后序遍历就能得到后缀表达式，但是此次实验是以栈、队