四则运算表达式求值栈+二叉树c++版文档格式.docx

1、3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如+、-号的优先级比*、/号的 低，当遇到*、/号时，要判断树以上的节点中是否有+、-号，有的话要与其交换位置。遇到时要反复创建二叉树的结点，构建子二叉树，考虑到括号要处理的步骤可能会较多，可以考虑用递归。遇到时那么直接完毕此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。4、对创建好的二叉树进展后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。程序的流程程序由三个模块组成：（1）输入模块：完成一个中缀表达式的输入，存入字符串

2、数组arrayMax中。（2）计算模块：设计一个建立二叉树的函数，Node* crtTree（Node* root），传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char getOp（Node *temp），其将数字字符存入一个结点，并返回数字字符的后一个符号。void deal（）函数功能是对字符数组进展处理。void output（Node *root）; 函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。（3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；三、详细设计物理数据类型题目要求输入的四那么运算表达式运算符只有

3、加减乘除，操作数有整数和小数，为了能够存储，采用C语言中的字符串数组。char chMax;算法的时空分析算法的运行时间主要消耗在二叉树的建立过程中。可以发现，每当遇到一个运算符或操作数时，都要调用一次函数char getOp（Node *temp），来将其存入二叉树的结点中，其中也会遇到递归的情况，但耗时可以忽略。所以假设输入的字符串中字符个数为N，那么算法的时间复杂度为O（N）。输入和输出的格式输入本程序可以将输入的四那么运算表达式中缀表达式转换为后缀表达式 /提示 请输入四那么运算表达式：/提示 等待输入 输出 /提示后缀表达式为：/输出结果的位置表达式的值为：四、调试分析 本次实验的难

4、点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改良采用字符串数组来存储操作数，成功解决了问题。另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。五、测试结果六、用户使用说明可选1、本程序的运行环境为DOS操作系统2、运行程序时提示输入四那么运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果 后缀表达式为：七、附录可选程序源代码c+1、利用二叉树后序遍

5、历来实现表达式的转换：#include stringstackiomanipconst int Max=100;using namespace std;class Node public: char chMax; /考虑到数值有时会是两位数，所以使用字符串数组 Node* lChild; Node* rChild; Node（） strcpy（ch,）; lChild=rChild=NULL; Node（） if（lChild!=NULL） delete lChild; if（rChild! delete rChild;static int count=0;static char arrayM

6、ax; /保存原始的中缀表达式static char str2*Max; /保存后序遍历出来的字符串，为表达式求值提供方便static int k=0;char getOp（Node *temp）; /temp指针保存每个结点，返回的是运算符Node* crtTree（Node* root）; /传入根结点指针，返回根结点指针 /获得处理后的字符串bool isError（char）; /判断字符是否有问题void deal（）; /对字符数组进展处理double value（string）; / 计算后缀表达式，得到其结果。int main（） Node* root=NULL; cout输入

7、中缀表达式：; cin.getline（array,40）; deal（）; root=crtTree（root）;输出后缀表达式： output（root）;strendl;输出后缀表达式的值： if（value（str）!=0）fixedsetprecision（2）value（str） elseA Wrong Input! return 0; /将数字字符存入一个结点，并返回数字字符的后一个符号char getOp（Node *temp） int i=0; if（ isError（arraycount） ） exit（0）; while（arraycount0|arraycount=.）

8、 temp-chi=arraycount; i+; count+; chi=0 return arraycount-1;/传入根结点指针，返回根结点指针Node* crtTree（Node* root） Node *p,*q; char op; if（root=NULL） root=new Node; p=new Node; op=getOp（root）; while（op! q=new Node; q-ch0=op;ch1= switch（op） case +:-lChild=root; root=q; op=getOp（p）; root-rChild=p; break;*/ if（root

9、-ch0=|root- strcpy（p-ch,root-ch）; p-rChild=q; root=p; else break;（ p=root; while（p-rChild） p=p-rChild; if（p-lChild=NULL） lChild=crtTree（p-lChild）; /递归创建括号里的指针 op=arraycount; else rChild=crtTree（p-rChild）;） return root;/传入根结点，后序遍历,赋值给另一个字符数组主要是为了给后序的计算表达式值提供方便void output（Node *root） int n; if（root） o

10、utput（root- n=0; while（root-chn!） strk+=root-chn+; strk+= bool isError（char ch） /判断每个字符是否有错 if（ch!ch!（ch）&） cout 字符错误！ return true; return false;void deal（） /对字符数组进展处理 int i=0,n=0; while（arrayi） if（arrayi=|arrayi= arrayn+=arrayi+; arrayn+= arrayn=double value（string s2） / 计算后缀表达式，得到其结果。 stack s; dou

11、ble x,y; int i = 0; while（i =2） x = s.top（）; s.pop（）; x += s.top（）; x =s.top（）-x; x *= s.top（）; if（ s.top（）=0） return 0; else x = s.top（）/x; default : x = 0; while（ = s2i&s2i = x = x*10+s2i - double k = 10.0; y = 0; y += （s2i-）/k）; k *= 10; x += y; if（x! s.push（x）; if（ s.size（）=1 ） return s.top（）;2、

12、利用堆栈来实现中缀表达式转换为后缀表达式。#include s.push（# s1.length（） /分成四个级别来检验中缀表达式 /s1.length（）是为了s1的长度，不包括0 if（s1i = ） /级别一 s.push（s1i+）; else if（s1i = ） /级别二 while（ s.top（） ! ） s2 += s.top（）; s2 += else if（ s1i = |s1i = ） /级别三 while（ cmp（s.top（） = cmp（s1i） ） s.push（s1i）; else /级别四= s1i&s1i s2.length（）-1） /由于s2的最后一位是空格，影响判断，所以用s2.length（）-1 switch（s2i） =2） x = s.top（）; else return 0;=2）x = s.top（）; string s1,s2;输入中缀表达式： cins1; s2= change（s1,s2）; if（value（s2）输出1后缀表达式：s2输出2表达式的值：value（s2）A wrong input!