实验4四项表达评估.docVIP

实验4四则运算表达式求值. 黄栋 软件2班 201326010226 背景 在工资管理软件中，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。 问题描述 四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。 基本要求 使用二叉树来实现。 实现提示 利用二叉树后序遍历来实现表达式的转换，同时可以使用栈来求解后缀表达式的值。 输入输出格式： 输入：在字符界面上输入一个中缀表达式，回车表示结束。 输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和计算结果，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 测试用例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 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