实验4四则运算表达式求值.doc

实验4四则运算表达式求值. 黄栋 软件2班 201326010226 背景 在工资管理软件，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然直接对表达式进行扫描并按照优先级逐步计算，但将中缀表达式转换为逆波兰表达式更容易处理。result is 159 需求分析： 1. 本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。 2.输入输出格式： 输入格式：在字符界面上输入一个中缀表达式，回车表示结束。 请输入表达式： 输入一个中缀表达式 输出格式：如果该中缀表达式正确，那么在字符界面上输出其后缀表达 式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 逆波兰表达式为： 输出逆波兰表达式 运算结果为：输出运算后的结果 测试用例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 概要设计 堆栈的ADT： 对于ADT Stack模板:物理数据类型采用数组 templateclass T class Stack{ --申明堆栈及其基本操作 public: Stack(int size=0);//构造大小为size的堆栈 ~Stack(){delete p;}//撤销堆栈 bool IsFull(){return top==Size;}//判断堆栈是否已满 bool IsEmpty(){return top==0;}//判断堆栈是否为空 void Push(T x);//将x压入堆栈 T Pop(T x);//将栈顶元素弹出用x保存 private: int Size;//大小 int top;//栈顶 T *p;//数组指针 }; 二叉树的ADT typedef struct BiTNode { TElemType data; int len; struct BiTNode * lchild, * rchild; }BiTNode, *BiTree; 算法的基本思想 1）以二叉链表的存储结构创建一棵树。 2）后根遍历为：此中缀表达式的后缀表达式 设str1= a+b)*((c+d)*e+f*h*g)，str2 是目的串。先用一个堆 栈存储operator（首先设置表达式起始符‘#’为运算符栈的栈底元素），遇到数字就不做处理直接放到目的串中，遇到operaor则将其与堆栈顶元素比较优先级，决定是否送到输出串中，直至整个表达式遍历完毕（即运算符栈的栈顶元素和当前读入的字符均为#）这样处理之后能得到一个后续的排列，再建立二叉树。 1.当遇到ab+这样的则建立左右结点为a和b且根为+的树并返回根结点 2.当遇到操作符前面只有一个操作数的如c*这样的就建立右子结点为c的根， 3.当遇到接点为*的，左结点为上次操作返回的子树的根结点（这种情况下就是合并树的情况） 程序的流程 程序由三个模块组成： （1） 输入模块：输入一个运算式 （2） 计算模块：利用栈进行表达式的计算，二叉树来存储。 （3） 输出模块：屏幕上显示出后缀表达式和运算结果。 三．详细设计 物理数据类型 --栈中基本操作的定义 templateclass T --构造堆栈 StackT::Stack(int size) { Size=size;//栈大小为size top=0;//栈顶top指向0 p=new T[Size];//为p开辟Size大小的空间 } templateclass T void StackT::Push(T x){ --向堆栈中压入x p[top++]=x;//将x保存于栈顶，栈顶+1 } templateclass T --弹出栈顶元素 T StackT::Pop(T x){ x=p[--top];//x保存栈顶元素，栈顶-1 return x; } 二叉树的基本操作的实现 void CrtSubTree(stack BiTree PTR, char c) { BiTNode * T; T = (BiTNode *)malloc(sizeof(BiTNode)); T-data = (char *)malloc(DATA_SIZE*sizeof(char)); T-data [0] = c; T-len = 1; T-rchild = PTR.top();