四则运算表达式求值实验报告

1、wordHUNAN UNIVERSITY课程实习报告题 目： 四那么运算表达式求值 学生姓名： 学生学号： 专业班级： 指导老师： 完 成 日 期 ： 一、需求分析四那么运算表达式求值，将四那么运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。测试数据输入：21+23*12-6输出：21 23 12

2、6 -*+二、详细设计输入和输出的格式输入本程序可以将输入的四那么运算表达式中缀表达式转换为后缀表达式输出后缀表达式为：/输出结果的位置表达式的值为：/输出结果的位置三、调试分析本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改良采用字符串数组来存储操作数，成功解决了问题。另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。四、测试结果五、用户使用说明

3、可选1、运行程序时提示输入四那么运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果请输入四那么运算表达式：输出后缀表达式为：表达式的值为：程序源代码c+#include<iostream> #include<string> #include<stack>#include<iomanip>const int Max=100;using namespace std; class Node public: char chMax; /考虑到数值有时会是两位数，所以使用字符串数组Node* lChild; Node* rChild; Node()

4、 strcpy(ch,""); lChild=rChild=NULL; Node() if(lChild!=NULL) delete lChild; if(rChild!=NULL) delete rChild; ; static int count=0; static char arrayMax; /保存原始的中缀表达式static char str2*Max; /保存后序遍历出来的字符串，为表达式求值提供方便static int k=0; char getOp(Node *temp); /temp指针保存每个结点，返回的是运算符Node* crtTree(Node* r

5、oot); /传入根结点指针，返回根结点指针void output(Node *root); /获得处理后的字符串bool isError(char); /判断字符是否有问题void deal(); /对字符数组进行处理double value(string); / 计算后缀表达式，得到其结果。 int main() Node* root=NULL; cout<<"输入中缀表达式："cin.getline(array,40); deal(); root=crtTree(root); cout<<"输出后缀表达式："output(r

6、oot); cout<<str<<endl; cout<<"输出后缀表达式的值："if(value(str)!=0)cout<<fixed<<setprecision(2)<<value(str)<<endl; elsecout<<"A Wrong Input!"<<endl;return 0; /将数字字符存入一个结点，并返回数字字符的后一个符号char getOp(Node *temp)int i=0; if( isError(arraycou

7、nt) ) exit(0); while(arraycount<='9'&&arraycount>='0'|arraycount='.') temp->chi=arraycount; i+; count+; temp->chi='0' count+; return arraycount-1; /传入根结点指针，返回根结点指针Node* crtTree(Node* root) Node *p,*q; char op; if(root=NULL) root=new Node;p=new Node

8、; op=getOp(root); while(op!='=') q=new Node; q->ch0=op; q->ch1='0' switch(op) case '+': case '-':q->lChild=root; root=q;p=new Node; op=getOp(p); root->rChild=p; break; case '*': case '/':if(root->ch0='+'|root->ch0='-')

9、 p=new Node; strcpy(p->ch,root->ch); p->lChild=root; p->rChild=q; op=getOp(root); root=p; else q->lChild=root; root=q; p=new Node; op=getOp(p);root->rChild=p; break; case '(':p=root; while(p->rChild) p=p->rChild; if(p->lChild=NULL) p->lChild=crtTree(p->lChild

10、); /递归创立括号里的指针op=arraycount; count+; break; else p->rChild=crtTree(p->rChild); /递归创立括号里的指针op=arraycount; count+; break; case ')': return root; return root; /传入根结点，后序遍历,赋值给另一个字符数组主要是为了给后序的计算表达式值提供方便void output(Node *root) int n; if(root) output(root->lChild); output(root->rChild);

11、 n=0; while(root->chn!='0') strk+=root->chn+;strk+=' ' bool isError(char ch) /判断每个字符是否有错if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch<='9'&&ch>='0')&&ch!='.'&&ch!

12、='('&&ch!=')')cout << "字符错误！" return true; return false; void deal() /对字符数组进行处理int i=0,n=0; while(arrayi) if(arrayi=' '|arrayi='=') i+; arrayn+=arrayi+; arrayn+='='arrayn='0' double value(string s2) / 计算后缀表达式，得到其结果。 stack < d

13、ouble> s; double x,y; int i = 0; while(i < s2.length() ) if(s2i = ' ') i+; switch(s2i) case '+': if(s.size()>=2)x = s.top(); s.pop(); x += s.top(); s.pop(); i+; break; elsereturn 0;case '-': if(s.size()>=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; break; el

14、sereturn 0;case '*': if(s.size()>=2)x = s.top(); s.pop(); x *= s.top(); s.pop(); i+; break; elsereturn 0; case '/': if(s.size()>=2)if( s.top()=0) return 0;elsex = s.top(); s.pop(); x = s.top()/x; s.pop(); i+; break; elsereturn 0; default : x = 0; while('0' <= s2i&&s2i <= '9') x = x*10+s2i - '0' i+; if(s2i = '