四则运算表达式求值
- 格式：doc
- 大小：300.50 KB
- 文档页数：13
HUNAN UNIVERSITY背景在工资管理软件中，不可避免的要用到公式的定义及求值等问题。
对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。
问题描述四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。
一．需求分析（1）本程序利用二叉树后序遍历来实现表达式的转换，同时可以使用栈来求解后缀表达式的值。
（2）输入输出的格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和计算结果，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
（3）测试用例：输入：21+23*（12-6）+9输出：21 23 12 6 -*+ 9+result is 168二．概要设计（1）抽象数据类型：由于四则运算表达式中运算符可能有多个后继，而运算的对象无后继，可以采用二叉树来实现把中缀表达式转换为后缀表达式。
数据对象：四则运算符及整数数据关系：运算符有多个后继，二运算对象的值无后继基本操作：后序遍历，二叉树的构建和摧毁，插入，删除经过二叉树的后序遍历后的表达式惊醒运算是满足后进先出的原则，采用栈来实现四则运算表达式的求值。
数据对象：运算符（字符）及整数数据关系：后进先出基本操作：入栈，出栈，栈的构建和删除（2）算法基本思想：用二叉树来存储四则表达式，再通过后序遍历把中缀表达式转换为后缀表达式，最后通过栈来计算表达式的值，最后输出后序表达式和表达式的值。
（3）程序的流程：该程序有三个模块组成：1.输入模块：输入一个中缀表达式2.处理模块：把中缀表达式转换为后缀表达式3.计算模块：计算表达式的值4.输出模块：输出后缀表达式及表达式的值三．详细设计（1）物理数据类型：采用指针来实现二叉树，其中分支节点存储运算符，用叶子节点存储操作数，可以减少二叉树的结构性开销。
采用顺序栈来实现表达式的计算，建立一个栈S 。
从左到右读后缀表达式，如果读到操作数就将它压入栈S中，如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈S中。
如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
伪代码：二叉树的基本操作伪代码：后序遍历：template<class Elem>void nextorder(BinNode<Elem>* subroot){if(subroot==Null) return false;//Empty subtree,do nothingnextorder(subroot->left());visit(subroot); //Perform whatever action is desirednextorder(subroot->right());}二叉树的建立：// Binary tree node classtemplate <class Elem>class BinNodePtr : public BinNode<Elem>{private:Elem it; // The node's valueBinNodePtr* lc; // Pointer to left childBinNodePtr* rc; // Pointer to right childpublic:BinNodePtr(){ lc = rc = NULL; }BinNodePtr(Elem e, BinNodePtr* l =NULL,BinNodePtr* r =NULL){it = e;lc = l;rc = r;}Elem& val(){ return it; }void setVal(const Elem& e){it = e; }inline BinNode<Elem>* left() const{ return lc; }void setLeft(BinNode<Elem>* b){ lc = (BinNodePtr*)b; }inline BinNode<Elem>* right() const{ return rc; }void setRight(BinNode<Elem>* b){ rc = (BinNodePtr*)b; }bool isLeaf(){ return (lc == NULL) && (rc == NULL); } };插入及删除：InsertChild(T, p, LR, c);DestroyBiTree(&T);DeleteChild(T, p, LR);顺序栈的基本操作及伪代码：void init_stack(){ top = -1; } //空线性表初始化top void push_stack(int x){ s[top] = x; } //压栈：void pop_stack(){ top = top -1; } //出栈int top_stack(){ return s[top]; } //取得栈顶元素bool empty_stack(){if(top==-1)return true;elsereturn false;} //判断栈空bool full_stack(){if(top==3)return true;elsereturn false;} //判断栈满int getHeadStack(){return s[top];}//返回栈顶元素的值} 计算表达式的值：Status evaluate (char ch[], float & result){SqStack S;Status St;int i;i=0;St = InitStack(S);while(ch[i]!='#'&&i<100){if(IsDigital(ch[i])){i+=EvalValue(&ch[i], S);}else if(ch[i]==' ')i++;else{EvalExpr(ch[i], S);i++;}}（2） 算法的具体步骤：首先建立一颗二叉树，用二叉树的分支节点存储四则运算的操作符，用二叉树的叶子节点存储二叉树的操作数，然后再对二叉树进行一次后序遍历，把后序遍历得到的压入栈中，当读到n 元运算符时，则取出由栈顶向下的n 项按操作符运算，再将运算的结果代替原栈顶的n 项，压入栈中 。
如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
（3） 算法的时空分析：采用二叉树中分支节点和叶子节点分别存储不同的数据类型，是算法的结构性开销明显降低，对二叉树进行一次后序遍历的时间代价为()n Θ，对顺序栈实行压栈和出栈时()n n T 2=，故计算表达式值时时间开销为()n Θ （4） 输入输出格式：Cout<<”请输入一串中缀表达式：” Cin>>21+23*（12-6）+9;Cout<<”转换为后缀表达式时为：”<<endl;Cout<<21 23 12 6 -*+ 9+<<endl;Cout<<”表达式的值为：”<<endl;Cout<<168<<endl;（5）结果截图：（6）代码：#include <iostream.h>#include <string.h>#include <malloc.h>#include <stdlib.h>#include <stack>#include <string.h>#define STACK_INIT_SIZE 100#define DATA_SIZE 10#define STACKINCREMENT 10#define OK 1#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW -2using namespace std;typedef float SElemtype;typedef int Status;typedef char * TElemType;typedef struct BiTNode {TElemType data;int len; //data字符串中字符的个数struct BiTNode * lchild, * rchild;}BiTNode, *BiTree;typedef struct{SElemtype *base;SElemtype *top;int stacksize;}SqStack;Status IsDigital(char ch){if(ch>='0'&&ch<='9'){return 1; //是数字字母}return 0; //不是数字字母}int CrtNode(stack <BiTree> &PTR, char *c){BiTNode * T;int i=0;T = (BiTNode *)malloc(sizeof(BiTNode));T->data = (char *)malloc(DATA_SIZE*sizeof(char));while(IsDigital(c[i])){T->data [i] = c[i];i++;}T->len = i;T->lchild = T->rchild = NULL;PTR.push (T);return i;}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(); //先右子树，否则运算次序反了PTR.pop ();T->lchild = PTR.top();PTR.pop ();PTR.push (T);}char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符号优先级{'>', '>', '<', '<', '>'},{'>', '>', '>', '>', '>'},{'>', '>', '>', '>', '>'},{'<', '<', '<', '<', '='}};int sym2num(char s) //返回符号对应优先级矩阵位置{switch(s){case '+': return 0; break;case '-': return 1; break;case '*': return 2; break;case '/': return 3; break;case '#': return 4; break;}}char Precede(char a, char b) //返回符号优先级{return(symbol[sym2num(a)][sym2num(b)]);}void CrtExptree(BiTree &T, char exp[]){//根据字符串exp的内容构建表达式树Tstack <BiTree> PTR;//存放表达式树中的节点指针stack <char> OPTR;//存放操作符char op;int i=0;OPTR.push ('#');op = OPTR.top();while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //与{if (IsDigital(exp[i])){//建立叶子节点并入栈PTRi+=CrtNode(PTR, &exp[i]);}else if (exp[i] == ' ')i++;else{switch (exp[i]){case '(':{OPTR.push (exp[i]);i++;break;}case ')':{op = OPTR.top (); OPTR.pop ();while(op!='('){CrtSubTree(PTR, op);op = OPTR.top (); OPTR.pop ();}//end whilei++;break;}default: //exp[i]是+ - * /while(! OPTR.empty ()){op = OPTR.top ();if (Precede(op, exp[i])=='>'){CrtSubTree(PTR, op);OPTR.pop ();}if(exp[i]!='#'){OPTR.push (exp[i]);i++;}break;}}//end switch}//end else}//end whileT = PTR.top();PTR.pop ();}void PostOrderTraverse(BiTree &T, char * exp ,int &count){//后序遍历表达式树T，获取树中每个结点的数据值生成逆波兰表达式exp//T是表达式树的根节点；字符串exp保存逆波兰表达式；count保存exp中字符的个数//后序遍历中，处理根结点时，依据T->len的值，把T->data中的字符依次添加到当前exp字符串的尾端//添加完T->data后，再添加一个空格字符，同时更新count计数器的值。
