c++课程设计报告(二叉树运算)

1、南京理工大学 课程设计报告 设计题目：二叉树解决四则运算问题 院系:自动化院 班级：2002 学号：912110200330 姓名：袁佳泉 指导老师：闫玉德 时间：2013年3月24一程序功能简介利用二叉树的结构解决带括号的四则运算的问题。程序利用二叉树的堆栈将二叉树的结点变成结点中的数据时运算符，左右子树是标准结点形式，或是另外的标准二叉树形式，通过后序遍历，经标准结点中的表达式求出。二 课程设计要求(1) 读懂程序，将程序的运算步骤完整的描述出来。(2) 四则运算的表达式可以接受空格输入(3) 依照运算顺序依次输出四则运算每一步的算式及及结果，最后输出最终计算结果三 课程设计思想这个课题设

2、计要求最关键的就是读懂程序，用类实现四则运算其实不是很难，只是利用二叉树实现带括号的四则运算有些难度。初读源程序觉得摸不到头脑，几遍下来还是能够理解的。在程序中先计算的式子放在栈顶，首先赋值右子树，再赋值左子树，保证优先级。如图： 二叉树类栈 运算符栈 ）*（+ 输入“+”，“（”，“*”三个运算符没有优先级冲突，按顺序压栈，然后输入“”，优先级低于“*”，binary_tree temp_tree; /生成二叉树string thisstring=""thisstring = thisstring + OpStack.top();OpStack.pop() /将栈顶优先级

3、高的运算符移除（即这边的乘号）etree.root = build_node(thisstring);/将优先级高的运算符作为二叉树的根结点copy(temp_tree.root,NodeStack.top().root);/将二叉树堆栈栈顶的二叉树复制到新生成的二叉树中（即把1复制到新的二叉树中）NodeStack.pop();/移除二叉树栈栈顶etree.root->right_child = temp_tree.root;/将二叉树作为新二叉树的右分支temp_tree.root = NULL;copy(temp_tree.root,NodeStack.top().root); /

4、继续将下一个栈顶二叉树复制（即把5复制）etree.root->left_child = temp_tree.root;/成为新二叉树的左分支NodeStack.pop();/移除temp_tree.root = NULL;copy(temp_tree.root, etree.root);NodeStack.push(temp_tree);/新二叉树进栈etree.root = NULL;OpStack.push(c);/优先级低的运算符压栈过程如图： 栈顶二叉树 temp_tree二叉树 Etree二叉树 将temp_tree作为etree的右结点 新的二叉树类栈最后进行一个遍历，判断

5、运算符栈是否处理完，算出最后结果。四 增加的模块（1）对源程序进行两处修改使其能够按运算顺序依次输出四则运算每一步的算式及结果。程序如下：Static int count=0;count+;if(count=1)cout<<"运算过程及结果是"cout<<num1<<prt->data<<num2<<"="<<num<<'t'五 优化程序源程序未能实现负数运算，只能在正数范围内运算。于是便试图把范围推广到整个实数。改编程序如下：if(isok(inf

6、ix) static int m=0,n=0 ;for(int i=0; i < infix.size(); i+) c = infixi;if(IsOperand(c) if(NodeStack.top().root->right_child=0&&NodeStack.top().root->left_child=0&&NodeStack.top().root!=0) string tempstring;tempstring = tempstring + c;if(i+1 < infix.size() && IsOper

7、and(infixi+1)/输入多位数 while(i+1 < infix.size() && IsOperand(infixi+1) tempstring = tempstring + infix+i;binary_tree temp;temp.root = build_node(tempstring);copy(temp.root,NodeStack.top().root); NodeStack.pop(); etree.root->left_child=temp.root;temp.root=NULL;NodeStack.push(etree);elsestr

8、ing tempstring;tempstring = tempstring + c;if(i+1 < infix.size() && IsOperand(infixi+1)/输入多位数 while(i+1 < infix.size() && IsOperand(infixi+1) tempstring = tempstring + infix+i;binary_tree temp;temp.root = build_node(tempstring);NodeStack.push(temp); n+;else if(c = '+' |

9、 c = '-' | c = '*' | c = '/' | c = '') if(OpStack.empty()OpStack.push(c);m+;else if(OpStack.top() = '(')OpStack.push(c);m+;else if(TakesPrecedence(c, OpStack.top()OpStack.push(c);m+;else if(c='-'&&m=n)binary_tree temp_tree;string thisstring=""thisstring=thisstring+'-'etree.root=build_node(thisstring);string thiss=""thiss=thiss+'0'temp_tree.root=build_node(thiss); etree.root->right_child=temp_tree.root; temp_tree.root=NULL; NodeStack.push(temp_tree);/新二叉树进栈 etree.root = N