一、需求分析
1. 利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。
2. 输入输出格式：
输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
二、概要设计
抽象数据类型
为实现上述程序的功能，前序遍历输入，以后序遍历输出。
算法的基本思想
用一个字符串储存输入的二项式，一次读取各个字符。如果遇见数据，累乘后存入后序遍历的数组当中（将字符型转换为整数类型）；如果遇见前括号，存入运算符栈中；如果遇见后括号，将前括号及前括号之后的运算符全部弹出；如果遇见加减号，在运算符栈为空或下一个为括号运算符时，运算符入栈，否则，将栈顶元素存入后序遍历的数组中，再运算符入栈；如果遇见乘除号，在运算符栈为空或下一个为括号运算符时及栈内第一个元素为乘号或除号时，运算符入栈，否则，将栈顶元素存入后序遍历的数组中，再运算符入栈。
程序的流程
程序由三个模块组成：
（1） 输入模块：输入正确的四则运算表达式。
（2） 计算模块：利用栈实现四则运算。
（3） 输出模块：屏幕上显示后序遍历的结果。
三、详细设计
物理数据类型
1、用数组存储输入的表达式和输出的表达式。
2、用栈存储操作
算法的具体步骤
求逆序遍历的算法
算法的时空分析
后序遍历的时间代价为Θ(n)
空间代价为一个数组.
输入和输出的格式
输入：请输入中序表达式：xxx#(#结束符)
输出：输出的后缀是：
五、测试结果
输入：5*(3+2)!
输出：5#3#2#+*
The result is:25
六、用户使用说明（可选）
1、“! ” 结束符
2、输入的包括符号请不要超过十位
七、实验心得（可选）
1：
这次试验的优点是在不断地调试和运行之后终于实现了这个代码，完成了c++创建栈的全部过程，让我的这个小组对栈的了解有人更加深入的认识，完成了栈的所有的基本操作，但是缺点在于这次试验的代码并不是完全符合条件，没有用树的遍历实现。二叉树实现参考附录二。
2：
此次实验要求我们用中序输入一个四则运算的表达式，计算出结果后，再通过后续遍历输出。我们组采用的是栈的方式做出了结果。
但是我跟别的组的夏晓玲讨论出了另一种想法时，先把四则运算表达式按照优先级加好括号，这样建树时一遇到括号就建这个子树，然后再返回到原来的根节点，继续往下建树。
夏晓玲同学加括号的代码写了100多行，我们还在考虑有没有更简洁的写法。但是在建树的过程中出现了问题，一旦表达式过长，就会失败。这也是我们未能解决的问题。这次实验，真正是我收获最大的一次，但问题是懂得了算法，写不出代码。嗯，所以，在接下来的学习中，还要加深对代码这一块的了解和掌握。
3：
每次的数据结构试验，我总是抱着笨鸟先飞的心态，提早写程序，就算写不出来，也能把思路整理的差不多，这样才不至于在实验室里“手足无措”
本次试验是用二叉树实现将中缀表达式转化成后缀表达式输出。二叉树掌握情况不是很好的我，首先想到的还是用栈来实现。即使用栈首先要思考的还是如何进行符号优先级的判断。思路如下：
case'*':
case'/':while(op.top!=-1&&op.data[op.top]!='('&&op.top!='*'&&op.data[op.top]!='/')//遇到‘*’或者‘/’, 如果这是栈中为空并且不为‘（’并且不是‘*’、‘/’，则将栈顶元素赋值给数组，
跳出循环，然后将给符号压入栈中。
case'+':
case'-': while(op.top!=-1&&op.data[op.top]!='(')
遇到‘+’、‘-’则需要判断如果栈顶不是空且不是‘（’，则将栈定元素赋给数组，跳出循环，然后将符号压入栈中
遇到‘（’压入栈中，遇到数字写入数组，遇到符号比照以上操作，遇到‘）’，将栈内符号依次输入数组，‘（’弹出。
——————————————以上是我们用栈的方案的主要思路
本次题目的要求是用二叉树来实现，我暂时没有自己实现成功，但是我借鉴了以为同学的。建二叉树最首要的任务就是优先级的判断，其主要思想是，从中缀表达式的最末符号来检测其优先级。假设遇到括号，则跳过括号，遇到‘*’‘/’号记录其位置，若遇到‘+’、‘-’则替换掉‘*’、‘/’的位置。最终i 记录的位置即为优先级最低的运算符，为二叉树的根节点，i 左边的表达式调用运算符优先级判断的函数然后递归返回左子树，右侧同理。 ——————————————————以上为二叉树方法的思想
无论是用哪种方式实现的，都是一次力度很强的知识点巩固。锻炼我们分析问题的深度以及细致度，更是理论应用实践的方式，所以总是尽力先自己思考，是在解决不了，那就请教“大神们”了，从中可以学到自己不会的东西。
七、附录（可选）
附录一：用栈实现
/*******************************************************************************
测试数据：
输入：5*(3+2)!
输出：5#3#2#+*
The result is:25
********************************************************************************/
#include
using namespace std;
/*********************************栈的抽象类的定义****************************/
//template
class stack {
public:
virtual bool isEmpty() = 0;
virtual void push(const int& d) = 0;
virtual int pop() = 0;
virtual int top() = 0;
};
/*******************************顺序栈类的定义********************************/
//template
class seqStack:public stack {
public:
seqStack(int initSize = 10); //构造函数，默认栈的容量为10
bool isEmpty(); //判断栈是否为空
void push(const int& d); //进栈函数
int pop(); //出栈函数
int top(); //返回栈顶元素
~seqStack(); //析构函数
// private:
int *data; //栈顶指针
int maxSize; //栈的容量
int top_p; //栈顶指针
void resize(); //将栈的容量扩大一倍
int trans(char exp[]);//四则运算
};
/*********************************顺序栈类的实现******************************/
seqStack::seqStack(int initSize) {
maxSize = initSize;
data = new int[maxSize];
top_p = -1;
cout
}
bool seqStack::isEmpty(){
return top_p == -1;
}
void seqStack::resize() {
maxSize *= 2;
int* tmp = data;
data = new int[maxSize];
for (int i = 0; i
data[i] = tmp[i];
}
delete tmp;
void seqStack::push(const int& d) {
if (top_p == maxSize-1) throw 0;
data[++top_p] = d;
cout
}
int seqStack::pop() {
//如果栈为空，抛出异常值0
if (top_p == -1) {
throw 0;
}
return data[top_p--];
}
int seqStack::top() {
//如果栈为空，抛出异常值0
if (top_p == -1) {
throw 0;
}
return data[top_p];
}
seqStack::~seqStack() {
delete []data;
}
/*********************************trans函数的实现******************************/ /**********************exp算数表达式 postexp 后缀表达式***********************/ int seqStack::trans(char exp[])
{
char postexp[10];//注意只有10位
char ch;
int i=0,j=0;
top_p=-1;
ch=exp[i];
i++;
for(;ch!='!';)//输入叹号结束
{
switch(ch)
{
case '(': //“（”情况
{
top_p++; data[top_p]=ch; break;
}
case ')':{ //“）”情况
while(data[top_p]!='(')
{
postexp[j]=data[top_p];
j++;
top_p--;
}
top_p--;
break;
}
case '+': //“+”情况
case '-': //“-”情况
{
while((top_p!=-1)&&(data[top_p]!='('))//(top_p!=-1)&&(data[top_p]!='(')时出栈
{
postexp[j]=data[top_p];
j++;
top_p--;
}
top_p++;
data[top_p]=ch;//压入栈中
break;
}
case '*': //“*”情况
case '/': //“/”情况
{
while((top_p!=-1)&&(data[top_p]!='(')&&(data[top_p]=='*'||data[top_p]=='/'))//(top_p!=-1)&&(data[top_p]!='(')&&(data[top_p]=='*'||data[top_p]=='/'))时出栈
{
postexp[j]=data[top_p];
j++;
top_p--;
}
top_p++;
data[top_p]=ch;//压入栈中
break;
}
case ' ':break;
default:
{
while(ch>='0'&&ch
{
postexp[j]=ch;
j++;
ch=exp[i];
i++;
}
i--;
postexp[j]='#';j++;//数字区分符
}
}
ch=exp[i];
i++;
}//结束循环
while(top_p!=-1)//将运算符全部出栈
{
postexp[j]=data[top_p];
j++;
top_p--;
}
postexp[j]='\0';//‘\0’结束
cout
/*********************************value函数的实现******************************/ float d=0;
char sh;
int k=0;
top_p=-1;
sh=postexp[k];
k++;
while(sh!='\0')
{
switch(sh)
{
case '+':
{
data[top_p-1]=data[top_p-1]+data[top_p];
top_p--;
break;
}
case '-':
{
data[top_p-1]=data[top_p-1]-data[top_p];
top_p--;
break;
}
case '*':
{
data[top_p-1]=data[top_p-1]*data[top_p];
top_p--;
break;
}
case '/':
{
if(data[top_p]!=0)
data[top_p-1]=data[top_p-1]/data[top_p];
else
{
cout
exit(0);
}
top_p--;
break;
}
default:
{
d=0;//初始化数字
while(sh>='0'&&sh
{
d=10*d+sh-'0';
sh=postexp[k];
k++;
}
top_p++;
data[top_p]=d;
}
}
sh=postexp[k];
k++;
}
cout
return data[top_p];
}
/*********************************main函数的实现******************************/ int main()
{
seqStack a(10);
cout
cin.getline(b,100); a.trans(b); return 0;
}
一、需求分析
1. 利用二叉树后序遍历来实现表达式的转换，同时可以使用实验3的结果来求解后缀表达式的值。
2. 输入输出格式：
输入：在字符界面上输入一个中缀表达式，回车表示结束。
输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。
二、概要设计
抽象数据类型
为实现上述程序的功能，前序遍历输入，以后序遍历输出。
算法的基本思想
用一个字符串储存输入的二项式，一次读取各个字符。如果遇见数据，累乘后存入后序遍历的数组当中（将字符型转换为整数类型）；如果遇见前括号，存入运算符栈中；如果遇见后括号，将前括号及前括号之后的运算符全部弹出；如果遇见加减号，在运算符栈为空或下一个为括号运算符时，运算符入栈，否则，将栈顶元素存入后序遍历的数组中，再运算符入栈；如果遇见乘除号，在运算符栈为空或下一个为括号运算符时及栈内第一个元素为乘号或除号时，运算符入栈，否则，将栈顶元素存入后序遍历的数组中，再运算符入栈。
程序的流程
程序由三个模块组成：
（1） 输入模块：输入正确的四则运算表达式。
（2） 计算模块：利用栈实现四则运算。
（3） 输出模块：屏幕上显示后序遍历的结果。
三、详细设计
物理数据类型
1、用数组存储输入的表达式和输出的表达式。
2、用栈存储操作
算法的具体步骤
求逆序遍历的算法
算法的时空分析
后序遍历的时间代价为Θ(n)
空间代价为一个数组.
输入和输出的格式
输入：请输入中序表达式：xxx#(#结束符)
输出：输出的后缀是：
五、测试结果
输入：5*(3+2)!
输出：5#3#2#+*
The result is:25
六、用户使用说明（可选）
1、“! ” 结束符
2、输入的包括符号请不要超过十位
七、实验心得（可选）
1：
这次试验的优点是在不断地调试和运行之后终于实现了这个代码，完成了c++创建栈的全部过程，让我的这个小组对栈的了解有人更加深入的认识，完成了栈的所有的基本操作，但是缺点在于这次试验的代码并不是完全符合条件，没有用树的遍历实现。二叉树实现参考附录二。
2：
此次实验要求我们用中序输入一个四则运算的表达式，计算出结果后，再通过后续遍历输出。我们组采用的是栈的方式做出了结果。
但是我跟别的组的夏晓玲讨论出了另一种想法时，先把四则运算表达式按照优先级加好括号，这样建树时一遇到括号就建这个子树，然后再返回到原来的根节点，继续往下建树。
夏晓玲同学加括号的代码写了100多行，我们还在考虑有没有更简洁的写法。但是在建树的过程中出现了问题，一旦表达式过长，就会失败。这也是我们未能解决的问题。这次实验，真正是我收获最大的一次，但问题是懂得了算法，写不出代码。嗯，所以，在接下来的学习中，还要加深对代码这一块的了解和掌握。
3：
每次的数据结构试验，我总是抱着笨鸟先飞的心态，提早写程序，就算写不出来，也能把思路整理的差不多，这样才不至于在实验室里“手足无措”
本次试验是用二叉树实现将中缀表达式转化成后缀表达式输出。二叉树掌握情况不是很好的我，首先想到的还是用栈来实现。即使用栈首先要思考的还是如何进行符号优先级的判断。思路如下：
case'*':
case'/':while(op.top!=-1&&op.data[op.top]!='('&&op.top!='*'&&op.data[op.top]!='/')//遇到‘*’或者‘/’, 如果这是栈中为空并且不为‘（’并且不是‘*’、‘/’，则将栈顶元素赋值给数组，
跳出循环，然后将给符号压入栈中。
case'+':
case'-': while(op.top!=-1&&op.data[op.top]!='(')
遇到‘+’、‘-’则需要判断如果栈顶不是空且不是‘（’，则将栈定元素赋给数组，跳出循环，然后将符号压入栈中
遇到‘（’压入栈中，遇到数字写入数组，遇到符号比照以上操作，遇到‘）’，将栈内符号依次输入数组，‘（’弹出。
——————————————以上是我们用栈的方案的主要思路
本次题目的要求是用二叉树来实现，我暂时没有自己实现成功，但是我借鉴了以为同学的。建二叉树最首要的任务就是优先级的判断，其主要思想是，从中缀表达式的最末符号来检测其优先级。假设遇到括号，则跳过括号，遇到‘*’‘/’号记录其位置，若遇到‘+’、‘-’则替换掉‘*’、‘/’的位置。最终i 记录的位置即为优先级最低的运算符，为二叉树的根节点，i 左边的表达式调用运算符优先级判断的函数然后递归返回左子树，右侧同理。 ——————————————————以上为二叉树方法的思想
无论是用哪种方式实现的，都是一次力度很强的知识点巩固。锻炼我们分析问题的深度以及细致度，更是理论应用实践的方式，所以总是尽力先自己思考，是在解决不了，那就请教“大神们”了，从中可以学到自己不会的东西。
七、附录（可选）
附录一：用栈实现
/*******************************************************************************
测试数据：
输入：5*(3+2)!
输出：5#3#2#+*
The result is:25
********************************************************************************/
#include
using namespace std;
/*********************************栈的抽象类的定义****************************/
//template
class stack {
public:
virtual bool isEmpty() = 0;
virtual void push(const int& d) = 0;
virtual int pop() = 0;
virtual int top() = 0;
};
/*******************************顺序栈类的定义********************************/
//template
class seqStack:public stack {
public:
seqStack(int initSize = 10); //构造函数，默认栈的容量为10
bool isEmpty(); //判断栈是否为空
void push(const int& d); //进栈函数
int pop(); //出栈函数
int top(); //返回栈顶元素
~seqStack(); //析构函数
// private:
int *data; //栈顶指针
int maxSize; //栈的容量
int top_p; //栈顶指针
void resize(); //将栈的容量扩大一倍
int trans(char exp[]);//四则运算
};
/*********************************顺序栈类的实现******************************/
seqStack::seqStack(int initSize) {
maxSize = initSize;
data = new int[maxSize];
top_p = -1;
cout
}
bool seqStack::isEmpty(){
return top_p == -1;
}
void seqStack::resize() {
maxSize *= 2;
int* tmp = data;
data = new int[maxSize];
for (int i = 0; i
data[i] = tmp[i];
}
delete tmp;
void seqStack::push(const int& d) {
if (top_p == maxSize-1) throw 0;
data[++top_p] = d;
cout
}
int seqStack::pop() {
//如果栈为空，抛出异常值0
if (top_p == -1) {
throw 0;
}
return data[top_p--];
}
int seqStack::top() {
//如果栈为空，抛出异常值0
if (top_p == -1) {
throw 0;
}
return data[top_p];
}
seqStack::~seqStack() {
delete []data;
}
/*********************************trans函数的实现******************************/ /**********************exp算数表达式 postexp 后缀表达式***********************/ int seqStack::trans(char exp[])
{
char postexp[10];//注意只有10位
char ch;
int i=0,j=0;
top_p=-1;
ch=exp[i];
i++;
for(;ch!='!';)//输入叹号结束
{
switch(ch)
{
case '(': //“（”情况
{
top_p++; data[top_p]=ch; break;
}
case ')':{ //“）”情况
while(data[top_p]!='(')
{
postexp[j]=data[top_p];
j++;
top_p--;
}
top_p--;
break;
}
case '+': //“+”情况
case '-': //“-”情况
{
while((top_p!=-1)&&(data[top_p]!='('))//(top_p!=-1)&&(data[top_p]!='(')时出栈
{
postexp[j]=data[top_p];
j++;
top_p--;
}
top_p++;
data[top_p]=ch;//压入栈中
break;
}
case '*': //“*”情况
case '/': //“/”情况
{
while((top_p!=-1)&&(data[top_p]!='(')&&(data[top_p]=='*'||data[top_p]=='/'))//(top_p!=-1)&&(data[top_p]!='(')&&(data[top_p]=='*'||data[top_p]=='/'))时出栈
{
postexp[j]=data[top_p];
j++;
top_p--;
}
top_p++;
data[top_p]=ch;//压入栈中
break;
}
case ' ':break;
default:
{
while(ch>='0'&&ch
{
postexp[j]=ch;
j++;
ch=exp[i];
i++;
}
i--;
postexp[j]='#';j++;//数字区分符
}
}
ch=exp[i];
i++;
}//结束循环
while(top_p!=-1)//将运算符全部出栈
{
postexp[j]=data[top_p];
j++;
top_p--;
}
postexp[j]='\0';//‘\0’结束
cout
/*********************************value函数的实现******************************/ float d=0;
char sh;
int k=0;
top_p=-1;
sh=postexp[k];
k++;
while(sh!='\0')
{
switch(sh)
{
case '+':
{
data[top_p-1]=data[top_p-1]+data[top_p];
top_p--;
break;
}
case '-':
{
data[top_p-1]=data[top_p-1]-data[top_p];
top_p--;
break;
}
case '*':
{
data[top_p-1]=data[top_p-1]*data[top_p];
top_p--;
break;
}
case '/':
{
if(data[top_p]!=0)
data[top_p-1]=data[top_p-1]/data[top_p];
else
{
cout
exit(0);
}
top_p--;
break;
}
default:
{
d=0;//初始化数字
while(sh>='0'&&sh
{
d=10*d+sh-'0';
sh=postexp[k];
k++;
}
top_p++;
data[top_p]=d;
}
}
sh=postexp[k];
k++;
}
cout
return data[top_p];
}
/*********************************main函数的实现******************************/ int main()
{
seqStack a(10);
cout
cin.getline(b,100); a.trans(b); return 0;
}