数据结构实验四：四则运算表达式.doc

数据结构实验报告

HUNAN UNIVERSITY

课程实验报告

题 目： 四则运算
学生姓名
学生学号
专业班级
指导老师 李 晓 鸿
完 成 日 期 2 0 1 5年 12 月 10日

一、需求分析
1．程序的功能
本程序要求首先输入一组数据进行四则运算，输入的数据是按照中缀表达式的结构输入的，完成初始化后，把中缀表达式用后缀表达式(逆波兰表达式)输出，同时输出计算结果。
2． 输入的形式
输入一个平时所用的正常的四则运算表达式（不需要特别注意输入式子是否正确），输入的数字的范围是（0至2^16）的小数或者整数,输入的符号限于（+-*/^）
3． 输出的形式
程序的输出就是转化后的后缀表达式以及计算的结果，输出结果间用空格隔开；
4． 测试数据

①正常的输入
输入
21+23*（12-6）
输出
后续表达式为 21 23 12 6 - * +
计算结果为 159

②输入有两个符号的错误情况
输入
6*3++4*（14-8）
输出
非括号运算符不能直接接非括号运算符
ERROR

③输入有小数的情况
输入
2.0*(11.2-5.3)+2.5
后续表达式为
2.0 11.2 5.3 - * 2.5 +
计算结果为 14.3

④有整数小数的情况
输入
2/（3.0+5）*3
输出
后续表达式为 2 3.0 5 + / 3 *
计算结果为0.75

⑤错误的输入
输入
2a+3
输出
a为非法字符
error

二、概要设计
1.抽象数据类型
本题目中，首先需要按顺序读取数字和操作符，将它们分别保存到两个数据结构中，如果最先保存的操作符优先级不大于接下来保存的操作符，将一直不被调用直到上一级操作符被调用，满足先进后出的数据结构，所以用栈来保存操作符。
对于保存的数字，每次调用操作符时，同时将最后保存的两位数字调用，满足先进后出的数据结构，所以用栈来保存数字。
由于需要用后缀表达式输出，按照进栈出栈的顺序，我们将符号作为节点，数字作为左右子树，依次相连成为一颗二叉树，通过后续遍历将二叉树输出。

2. 算法的基本思想
①．本题目在之后的操作中需要将数字和操作符进入不同的栈，所以我们在程序设计之前需要先设计函数判断读取的字符是数字还是操作符。
②.本题中需要设计函数对操作符的优先级进行比较，即‘）’的优先级大于‘*’‘/’的优先级大于‘+’‘-’的优先级大于‘（’的优先级。
③．对输入的式子进行顺序扫描，依次将数字和操作符依次进栈，当操作符进栈且前一个元素不为空时进行判断，将要进栈的操作符I与上一个操作符进行优先级比较，上一个操作符优先级级别大于操作符I，则弹出上一个操作符，同时弹出两个操作数建立二叉树，操作符做根节点，将二叉树的的结点存进数字栈，操作符I进操作符栈;若上一个操作符优先级级别小于或等于操作符I，操作符I进操作符栈。
④．当式子扫描完毕，对于操作符栈剩下的元素，一次出栈，同时数字栈出两个元素，操作符作为结点，两个元素作为左右子树，再将节点存进数字栈，重复以上操作，知道操作符栈中没有元素。
⑤．当操作符栈中没有元素，此时已经建好了一棵二叉树，我们通过后续遍历输出二叉树，同时进行计算。输出遍历二叉树每个结点的值，输出计算结果。

3．ADT
ADT BinNode
数据对象：包含结点的值，同时包含结点的左右指针
数据关系：每个结点都有各自的值
若结点左右指针为空，则该节点称为叶子结点
基本操作：
int val() //返回结点的数值
Void setVal（const Elem&）//设置节点的值
inline BinNode* left()const //获取左结点
inline BinNode* right()const //获取右结点
void setLeft(Node* it) //设置左结点
void setRight(Node* it) //设置右结点
Bool isLeaf（） //判断叶子结点

ADT BinTree
数据对象D：D是BinNode类的数据元素的集合
数据关系R：
若D为空集，则称为空树 。
否则:
(1) 在D中存在唯一的称为根的数据元素root；
(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。
基本操作：
void preorder(Binnode<Elem>* subroot)//后续输出二叉树
bool evaluate(BinNode *prt) //计算二叉树一个节点
void clear_help(BinNode *rt)//删除二叉树
BinNode *build_node(string x)//构建二叉树
void copy(BinNode *&r1,BinNode* r2)//拷贝树

ADT Stack
数据对象：D＝{ ai | ai ∈binNode, i=1,2,...,n, n≥0
数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶，a1 端为栈底。
若栈中没有元素，则为空栈。
基本操作：
bool push（const BinNode&item）；
bool pop（BinNode&it）；
bool topValue（BinNode&it）；
int length()；const

4．程序的流程
程序由五个模块组成：
（1） 初始化模块：完成中缀表达式的输入；
（2） 检测模块：检测中缀表达式输入是否正确；
（3） 转换建树模块：中缀表达式建树，并利用后序遍历输出树。
（4） 计算模块：利用后缀表达式计算表达式；
（4）输出模块：输出后缀表达式及计算结果。

三、详细设计
1.物理数据类型
本题中使用到了栈和树，由于不知道栈的大小，所以用链表实现栈；由于不知道树的结点数等，用链表实现树。string来保存输入的字符串，用float型来储存储存数字，char型储存操作符，计算结果为float型。
2. 算法的具体步骤
判断运算符与数字——设置优先级——检测表达式——建树与后序输出——计算结果
判断运算符与数字：运算符可为+-*/^%,数字中.（小数点）也可通过判断。
bool IsOperator(char ops) //判断一个字符是否是运算符
{
if (ops == '+' || ops == '-' || ops == '*' || ops == '/' || ops == '^' || ops == '%' || ops == '(' || ops == ')')
return true;
else
return false;
}

bool IsOperand(char ch) //判断是否是数字
{
if (((ch >= '0') && (ch <= '9')) || (ch == '.'))
return true;
else
return false;
}

检测表达式：依次遍历表达式的每一个字符，判断其是操作符还是运算数，如果是运算数“.”，则判断其前一位和下一位是否是运算数，若不是，则表达式有误，如果字符是“)”，则判断下一位是否为运算符“+ -* % ^”，若不是，则表达式有误，如果是“（”，则下一位是否为“-”或运算数，若不是，则表达式有误，如果，字符是“+ -* % ^”，判断其下一位是否为“+ -* % /^”，若是，则表达式错误；遍历过程中，记录“（”“）”的数目，判断他们是否相等，若不相等，这表达式错误。
bool isok(string exp) //判断输入是否正确
{
char check;
int error=0,lb=0,rb=0,numofoperand=0,numofoperator=0;
for(int m=0;m<exp.size();m++)
{
check=exp[m];
if(IsOperand(check))
{
if(check=='.')
{
if(!(exp[m-1]>='0'&&exp[m-1]<='9')&&(exp[m+1]>='0'&&exp[m+1]<='9'))
{
error++;
cout<<"浮点型数据输入有误!!!"<<endl;
}
}
numofoperand++;
}
else if(IsOperator(check))
{
if(check==')')
{
rb++;
if(rb>lb)
{
error++;
cout<<"右括号不可能大于左括号!!!"<<endl;
}
if(IsOperator(exp[m+1])&&(exp[m+1]=='+'||exp[m+1]=='-'||exp[m+1]=='*'||exp[m+1]=='/'||exp[m+1]=='^'||exp[m+1]==')'||exp[m+1]=='%'))
{
numofoperator++;
m++;
if(exp[m]==')')
rb++;
}
else if(IsOperator(exp[m+1])||IsOperand(exp[m+1]))
{
error++;
cout<<"右括号后不可能直接跟数据或左括号!!!"<<endl;
}
}
else if(check=='(')
{
lb++;
if(IsOperator(exp[m+1])&&exp[m+1]=='(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
{
error++;
cout<<"左括号后运算符只能跟左括号!!!"<<endl;
}
}
else
{
numofoperator++;
if(IsOperator(exp[m+1])&&exp[m+1]=='(')
{
m++;
lb++;

}
else if(IsOperator(exp[m+1]))
{
error++;
cout<<"非括号的运算符不能直接接非括号运算符!!!"<<endl;
}
}
}
else
{
error++;
cout<<check<<"为非法字符!!!"<<endl;
}
}
if((error==0)&&(lb==rb)&&(numofoperand!=0)&&(numofoperator!=0))
return true;
else
return false;
}
设置优先级：考虑所有操作符的组合，若是操作符A的优先级大于操作符B，返回ture，否则返回false。
bool TakesPrecedence(char OperatorA, char OperatorB) //按照优先级用if从最优至最后从上至下排列，从而达到比较A与B的优先级
{
if (OperatorA == '(')
return false;
else if (OperatorB == '(')
return false;
else if (OperatorB == ')')
return true;
else if (addition(OperatorA, OperatorB))
return false;
else if ((OperatorA == '^') && (OperatorB == '^'))
return false;
else if (OperatorA == '^')
return true;
else if (OperatorB == '^')
return false;
else if ((OperatorA == '%') && (OperatorB == '%'))
return false;
else if (OperatorA == '%')
return true;
else if (OperatorB == '%')
return false;
else if ((OperatorA == '*') || (OperatorA == '/'))
return true;
else if ((OperatorB == '*') || (OperatorB == '/'))
return false;
else if ((OperatorA == '+') || (OperatorA == '-'))
return true;
else
return true;
}
建树：算法利用两个临时的栈，一个存操作数，一个存操作符，检测到操作数，建立叶子节点，压入存入操作数栈，遇到操作符，存入操作符栈，每次存操作符时与前一个操作符做运算级别比较，若上一个操作符级别大，则弹出上一个操作符，同时弹出两个操作数建立二叉树，操作符做根节点，在把根节点压入操作数栈，括号做优先级最高处理，遇到右括号（前提是有了左括号和必要的运算式），操作符栈弹出，同时弹出两个操作数，建立二叉树，根节点压入操作数的栈，如果遇到负号，则将0压入操作数栈中，把负号压入操作符中。

if(isok(infix))
{
for(int i=0;i<infix.size();i++)//遍历字符串
{
c=infix[i];
if(i==0 && c=='-') //若开始为负，则把零压入运算数栈，把'-'压入运算符栈
{
binary_tree temp;
temp.root=build_node("0");
NodeStack.push(temp);
OpStack.push('-');
}
else
if(IsOperand(c))//若c是0~9的字符，检测他后边的是否为0~9的字符，直到不是0~9的字符为止，将他们转换位数字，压入运算数栈中
{
string tempstring="";
tempstring=tempstring+c;
while(i+1<infix.size()&&IsOperand(infix[i+1]))
{
tempstring+=infix[++i];
}
binary_tree temp;
temp.root=build_node(tempstring);
NodeStack.push(temp);
}
else if(c=='+'||c=='-'||c=='/'||c=='*'||c=='^'||c=='%')//若c为运算符
{
if(OpStack.empty())//运算符栈为空，将该字符压入栈中
OpStack.push(c);
else if(OpStack.top()=='(')//如果栈顶为（，将c压入运算符栈中
OpStack.push(c);
else if(TakesPrecedence(c,OpStack.top()))//如果栈顶的操作符优先级小于c的优先级，则将c压入运算符栈中
OpStack.push(c);
else
{
while(!OpStack.empty()&&(TakesPrecedence(OpStack.top(),c)||addition(OpStack.top(),c)))//如果栈顶操作符优先级大于等于c的优先级
{
binary_tree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
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);
}
}
if(c=='(') //若中间遇到括号，则判断下一位是否为'-'，如是，建立数据0的二叉树，并将其压入节点栈中，-压入符号栈中
{
OpStack.push(c);
if(infix[i+1]=='-')
{
binary_tree temp;
temp.root=build_node("0");
NodeStack.push(temp);
OpStack.push('-');
++i;
}
}
else if(c==')')
{
while(OpStack.top()!='(')
{
binary_tree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
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.pop();
}
}
while(!OpStack.empty())
{
binary_tree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
if(!OpStack.empty())
etree.root=NULL;
}

计算：若根节点是运算符且左右子树为运算数，则将他们做计算，并将结果保存在根节点中，若不是，则计算其左子树，计算其右子树，直到，左右子树为空。
void evaluate(void){evaluate(root);}
bool evaluate(BinNode *prt) //计算二叉树一个节点
{
if(IsOperator(prt->data)&&!IsOperator(prt->left_child->data)&&!IsOperator(prt->right_child->data))
{
float num=0;
float num1=atof(prt->left_child->data.c_str());
float num2=atof(prt->right_child->data.c_str());

if(prt->data=="+")
num=num1+num2;
else if(prt->data=="-")
num=num1-num2;
else if(prt->data=="*")
num=num1*num2;
else if(prt->data=="/")
{
if(num2==0.0)
{
cout<<"除数为零!!!运算出错";
return false;
}
else
num=num1/num2;
}
else if(prt->data=="^")
num=pow(num1,num2);//extern float pow(float x, float y); 用法:#include <math.h> 功能:计算x的y次幂
else if(prt->data=="%")
{
if(num2==0.0)
{
cout<<"除数为零!!!运算出错";
// system("pause");

return false;
}
else
num=(long)num1%(long)num2;
}
stringstream bob;
bob<<num;
string suzzy(bob.str());
prt->data=suzzy; //计算机结果给根节点，其左右孩子置空
prt->left_child=NULL;
prt->right_child=NULL;
}
else if(prt->left_child==NULL&&prt->right_child==NULL);
else
{
evaluate(prt->left_child);
evaluate(prt->right_child);
evaluate(prt);
}
return true;
}

3.算法的时空分析及改进设想 
输入的式子有n个字符，遍历式子进栈出栈每一步的复杂度都是O(n),后续遍历的复杂度是O(n)，计算后序表达式的复杂度是O(n)，由于建树的复杂度要大于其他部分功能的复杂度，本程序的时间复杂度即为建树的复杂度。
4.输入和输出格式
①．输入表达式（检测输入时输入的空格）
输入 //输入表达式
getline(cin, infix);
for (int j = 0; j<infix.size(); j++)
{
if (infix[j] == ' ')
{
infix.erase(j, 1);
j--;
}
②．输入的数据有误时的输出
输出 ：浮点型数据输入有误
if (!(exp[m - 1] >= '0'&&exp[m - 1] <= '9') && (exp[m + 1] >= '0'&&exp[m + 1] <= '9'))
{
error++;
cout << "浮点型数据输入有误!!!" << endl;
}
else
{
error++;
cout << check << "为非法字符!!!" << endl;

③．输入括号内没有值报错的输出
输出：右括号后不可能直接跟数据或左括号
else if (IsOperator(exp[m + 1]) || IsOperand(exp[m + 1]))
{
error++;
cout << "右括号后不可能直接跟数据或左括号!!!" << endl;
}
④．在计算过程中发现除数为零
输出：除数为零,运算出错
if (num2 == 0.0)
{
cout << "除数为零,运算出错" << endl;
return false;
}

四、 测试结果
①正常的输入

②输入有两个符号的错误情况

③输入有小数的情况

④有整数小数的情况

⑤错误的输入

五． 试验心得
如何将输入的字符串转换为表达式树，是本题中的难点，在数字和操作符进栈和出栈结束后就能得到表达式的值。
六． 附录

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cmath>
using namespace std;

bool IsOperator(string mystring) //判断字符串是否是运算符
{
if (mystring == "-" || mystring == "+" || mystring == "*" || mystring == "/" || mystring == "^" || mystring == "%")
return true;
else
return false;
}

bool IsOperator(char ops) //判断一个字符是否是运算符
{
if (ops == '+' || ops == '-' || ops == '*' || ops == '/' || ops == '^' || ops == '%' || ops == '(' || ops == ')')
return true;
else
return false;
}

bool IsOperand(char ch) //判断是否是数字
{
if (((ch >= '0') && (ch <= '9')) || (ch == '.'))
return true;
else
return false;
}

bool isok(string exp) //判断输入是否正确
{
char check;
int error = 0, lb = 0, rb = 0, numofoperand = 0, numofoperator = 0;
for (int m = 0; m<exp.size(); m++)
{
check = exp[m];
if (IsOperand(check))
{
if (check == '.')
{
if (!(exp[m - 1] >= '0'&&exp[m - 1] <= '9') && (exp[m + 1] >= '0'&&exp[m + 1] <= '9'))
{
error++;
cout << "浮点型数据输入有误!!!" << endl;
}
}
numofoperand++;
}
else if (IsOperator(check))
{
if (check == ')')
{
rb++;
if (rb>lb)
{
error++;
cout << "右括号不可能大于左括号!!!" << endl;
}
if (IsOperator(exp[m + 1]) && (exp[m + 1] == '+' || exp[m + 1] == '-' || exp[m + 1] == '*' || exp[m + 1] == '/' || exp[m + 1] == '^' || exp[m + 1] == ')' || exp[m + 1] == '%'))
{
numofoperator++;
m++;
if (exp[m] == ')')
rb++;
}
else if (IsOperator(exp[m + 1]) || IsOperand(exp[m + 1]))
{
error++;
cout << "右括号后不可能直接跟数据或左括号!!!" << endl;
}
}
else if (check == '(')
{
lb++;
if (IsOperator(exp[m + 1]) && exp[m + 1] == '(')
{
m++;
lb++;
}
else if (IsOperator(exp[m + 1]))
{
error++;
cout << "左括号后运算符只能跟左括号!!!" << endl;
}
}
else
{
numofoperator++;
if (IsOperator(exp[m + 1]) && exp[m + 1] == '(')
{
m++;
lb++;

}
else if (IsOperator(exp[m + 1]))
{
error++;
cout << "非括号的运算符不能直接接非括号运算符!!!" << endl;
}
}
}
else
{
error++;
cout << check << "为非法字符!!!" << endl;
}
}
if ((error == 0) && (lb == rb) && (numofoperand != 0) && (numofoperator != 0))
return true;
else
return false;
}
bool addition(char OperatorA, char OperatorB) //A=B返回TRUE.
{
if (OperatorA == OperatorB || (OperatorA == '*'&&OperatorB == '/') || (OperatorA == '/'&&OperatorB == '*') || (OperatorA == '+'&&OperatorB == '-') || (OperatorA == '-'&&OperatorB == '+'))
return true;
else
return false;
}

bool TakesPrecedence(char OperatorA, char OperatorB) //按照优先级用if从最优至最后从上至下排列，从而达到比较A与B的优先级
{
if (OperatorA == '(')
return false;
else if (OperatorB == '(')
return false;
else if (OperatorB == ')')
ret