【问题描述】

从标准输入中读入一个整数算术运算表达式，如 (3+4)*(8-2)+9/3=，构建表达式树，输出表达式树的前序、中序、后序以及层次遍历结果，并根据表达式树计算表达式的值。

【要求】

1. 表达式运算符只有+、-、*、/，表达式末尾的=字符表示表达式输入结束，表达式中可能会出现空格；

2. 表达式中会出现圆括号，括号可能嵌套，不会出现错误的表达式；

3. 出现除号/时，以整数相除进行运算，结果仍为整数，例如：5/3结果应为1。

4. 要求采用表达式树来实现表达式计算。

例如表达：(3+4)*(8-2)+9/3：

则生成的表达式树为：

 

   

【输入形式】

从键盘输入一个以=结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。

【输出形式】

在屏幕上输出四种遍历结果（运算数后面加上#结束）以及计算结果（为整数，即在计算过程中除法为整除）。

【样例输入】

(3-9)/3+5-7*4=

【样例输出】

-+/-3#9#3#5#*7#4#

3#-9#/3#+5#-7#*4#

3#9#-3#/5#+7#4#*-

-+*/5#7#4#-3#3#9#

-25

现在我们逐段分析：

首先导入用到的库：

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#define _CRT_SECURE_NO_WARNINGS//不弹出警告
using namespace std;

堆栈是用来将中缀表达式转化为后缀表达式，同时用于先中后序遍历表达树。队列是用来实现层次遍历。

此时我们遇到一个麻烦，使用string字符串中的字符元素来判断数字，如果使用str[i]>='0'&&str[i]<='9'这种方法，只能判断小于10的数字，局限性太强。不广泛适用。

此时我们可以自定义一个数据类型同时包含数字和字符类型，用flag来区分是数字还是字符。flag=true，表示操作数。

class node
{
public:
    int num;
    char op;
    bool flag;
}

然后我们需要定义操作符栈，用于计算后缀表达式的整形元素的栈，后缀表达式队列，运算结果队列。

stack<node>s;//操作符栈
stack<int>st;//用于计算后缀表达式的栈
queue<node>q;//后缀表达式队列
queue<node>result;//运算结果队列

中缀转后缀代码：

void Infix2Sufix(string &str,queue<node>& tmp)//输入为字符串和结点队列指针
{
    node tem;
    //cout<<"中缀表达式为:"<<str<<endl;
    string::size_type i;//string::size_type是一个无符号整数，用于表示字符串大小，即字符串的长度
    for(i=0;i<str.length();i++)
    {
        //if(str[i]==' ')continue;
        if(str[i]=='(')//node可以只指定一部分变量
        {
            tem.flag=false;
            tem.op=str[i];
            s.push(tem);
        }
        else if(str[i]=='=')continue;
        else if(str[i]==')')
        {
            while(!s.empty() && s.top().op != '(')
            {
                q.push(s.top());//q表示后缀表达式队列
                s.pop();//s是操作符栈
            }
            s.pop();
        }
        else if(str[i]>='0'&&str[i]<='9')
        {
            tem.flag=true;
            tem.num = str[i] - '0';
            int j=i+1;
            if(str[j]>='0'&&str[j]<='9')
            {
                while(str[j]>='0'&&str[j]<='9')
                {
                    tem.num=tem.num*10+str[j]-'0';//将字符串转换为数字
                    j++;i++;
                }
            }
            q.push(tem);//q是一个既包含数据又包含运算符的结构的队列
        }
        else if(str[i]=='=')continue;
        else
        {
            tem.flag=false;//表示操作符
            while(!s.empty()&&p[str[i]]<=p[s.top().op])
            {
                q.push(s.top());
                s.pop();
            }
            tem.op=str[i];//操作符入栈
            s.push(tem);
        }
    }
    while(!s.empty())
    {
        q.push(s.top());
        s.pop();
    }
    //cout<<"后缀表达式为：";
    while(!q.empty())
    {
        tmp.push(q.front());
        result.push(q.front());
        q.pop();
    }
    while(!result.empty())
    {
        if(result.front().flag==true)
        {
            st.push(result.front().num);
            result.pop();
        }
        else if(result.front().flag==false)
        {
            if(result.front().op=='+')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a1+a2);
                result.pop();
            }
            else if(result.front().op=='-')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a2-a1);
                result.pop();
            }
            else if(result.front().op=='*')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a1*a2);
                result.pop();
            }
            else if(result.front().op=='/')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a2/a1);
                result.pop();
            }
        }
    }
    //return st.top();
}

 生成表达树代码：

首先我们要定义一个叶子结点：

包含整形，字符型，布尔型（用于判断是数字还是字符），指针类型，分别指向左子树和右子树。构造函数用于初始化。

代码如下：

struct myNode
{
    int num;//操作数
    char op;//操作符
    bool flag;//true表示操作数，false表示操作符
    myNode* lchild;
    myNode* rchild;
    myNode(int d):num(d),lchild(nullptr),rchild(nullptr){};
    myNode(char op):op(op),lchild(nullptr),rchild(nullptr){};
};

然后我们需要构造树：其实就是就两个作用，创造左子树和右子树，返回根节点。

代码如下：

class myTree
{
public:
    myNode* root;
    myTree():root(nullptr){};
    void createTree(queue<node>tmp);
};

创造树就要用到我们刚刚产生的后缀表达式了。

下面是由后缀表达式构造表达树的过程。

定义一个由指向叶子结点的指针构成的栈，定义一个叶子结点指针（指针便于克隆，new）。遍历后缀表达式，如果后缀表达式中的元素是数字，则将其放进堆栈。如果后缀表达式中的元素是字符，则在堆栈中取出两个叶子结点作为其左右子结点。最后返回该树的根节点（可根据根节点访问所有节点）。

代码实现如下：

void myTree::createTree(queue<node>tmp)
{
    stack<myNode*>s1; myNode*my_p;
    while(!tmp.empty())//tmp表示后缀表达式（逆波兰表达式），其中元素是node结构体
    {
        if(tmp.front().flag==true)
        {
            my_p = new myNode(tmp.front().num);
            my_p->flag = true;
            s1.push(my_p);//s1是树的根节点
            tmp.pop();
        }
        else if(tmp.front().flag==false)
        {
            my_p = new myNode(tmp.front().op);
            my_p->flag = false;
            my_p->rchild = s1.top();
            s1.pop();
            my_p->lchild = s1.top();
            s1.pop();
            s1.push(my_p);
            tmp.pop();
        }
    }
    root = s1.top();//构建一个树，返回该树的根节点即可
    if(!s1.empty())
    s1.pop();
}

还有一个小问题要解决，就是去除空格。

很显然，C++去除空格不如Python方便。以下是代码：

void removeSpace(string &str)
{
    std::string::size_type index = 0;
    if(!str.empty())
    {
        while((index=str.find(' ',index))!=string::npos)//使用str.find找出第一个空格位置，找到了，返回索引
        //string::npos表示无效或不存在的字符串位置
        {
            str.erase(index,1);//删除字符串中index位置开始的第一个字符
        }
    }
}

到了表达树的遍历阶段了：根据先序遍历是根左右，中序遍历是左根右，后序遍历是左右根。

但是每一种遍历都要有两行这样的代码：if(root==nullptr)return;

这是根节点：

if(root->flag==true)
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }

这是左子树节点：

 postOrder(root->lchild);

这是右子树节点：

postOrder(root->rchild);

那么这三种遍历的代码如下:

void preOrder(myNode* root)
{
    if(root==nullptr)return;
    if(root!=nullptr)//先输出根结点的值
    {
        if(root->flag==true)
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }
        preOrder(root->lchild);//再遍历左节点
        preOrder(root->rchild);//最后遍历右结点
    }
}

//中序遍历，左中右
void inOrder(myNode* root)
{
    if(root==nullptr)return;
    if(root!=nullptr)
    {
        inOrder(root->lchild);//先遍历左节点
        if(root->flag==true)//输出根节点的值
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }
        inOrder(root->rchild);//最后遍历右结点
    }
}

//后序遍历，左右根
void postOrder(myNode* root)
{
    if(root==nullptr)return;
    if(root!=nullptr)
    {
        postOrder(root->lchild);//先遍历左节点
        postOrder(root->rchild);//再遍历右结点
        if(root->flag==true)//最后输出根节点的值
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }
    }
}

 当然，层析遍历就有点不一样了，层次遍历是通过队列实现的，根节点进队，根节点出队，根节点的左右子结点进队，左子结点出队，左子节点的左右子结点进队，右子节点出队，右子节点的左右子结点进队...实现宽度优先搜索。

void levelOrder(myNode* root)
{
    queue<myNode*>qmp;
    qmp.push(root);
    while(!qmp.empty())//实现宽度优先搜索，根节点出队，左右节点进队
    {
        myNode* pil = qmp.front();
        qmp.pop();
        if(pil->flag==true)
        {
            cout<<pil->num<<"#";
        }
        else
        {
            cout<<pil->op;
        }
        if(pil->lchild!=nullptr)
            qmp.push(pil->lchild);
        if(pil->rchild!=nullptr)
            qmp.push(pil->rchild);
    }
}

最后一步实现输出，代码如下：

int main(void)
{
    //freopen("in.txt", "r", stdin);
    //freopen("abc.out", "w", stdout);
    string str;
    p['+'] = p['-'] = 1;
    p['*'] = p['/'] = 2;
    //cin>>str;
    getline(cin,str);
    removeSpace(str);
    int res=0;
    queue<node>q_tmp ;
    Infix2Sufix(str,q_tmp);
   
    myTree * tree = new myTree;
    tree->createTree(q_tmp);
    
    preOrder(tree->root);
    cout<<endl;
    inOrder(tree->root);
    cout<<endl;
    postOrder(tree->root);
    cout<<endl;
    levelOrder(tree->root);
    cout<<endl;
    cout<<st.top();

    return 0;
}

 总代码如下：

#define _CRT_SECURE_NO_WARNINGS//不弹出警告
#include<iostream>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<map>
#include<string>
#include<stdio.h>
//#include"infix2sufix.h"
using namespace std;
map<char,int> p;//一种关联容器，用于存储键值对，键是char字符，值是int整数
class node
{
public:
    int num;//操作数
    char op;//操作符
    bool flag;//true表示操作数，false表示操作符，flag用于判断是否是操作数
};
stack<node>s;//操作符栈
stack<int>st;//用于计算后缀表达式的栈
queue<node>q;//后缀表达式队列
queue<node>result;//运算结果队列
void Infix2Sufix(string &str,queue<node>& tmp)//输入为字符串和结点队列指针
{
    node tem;
    //cout<<"中缀表达式为:"<<str<<endl;
    string::size_type i;//string::size_type是一个无符号整数，用于表示字符串大小，即字符串的长度
    for(i=0;i<str.length();i++)
    {
        //if(str[i]==' ')continue;
        if(str[i]=='(')//node可以只指定一部分变量
        {
            tem.flag=false;
            tem.op=str[i];
            s.push(tem);
        }
        else if(str[i]=='=')continue;
        else if(str[i]==')')
        {
            while(!s.empty() && s.top().op != '(')
            {
                q.push(s.top());//q表示后缀表达式队列
                s.pop();//s是操作符栈
            }
            s.pop();
        }
        else if(str[i]>='0'&&str[i]<='9')
        {
            tem.flag=true;
            tem.num = str[i] - '0';
            int j=i+1;
            if(str[j]>='0'&&str[j]<='9')
            {
                while(str[j]>='0'&&str[j]<='9')
                {
                    tem.num=tem.num*10+str[j]-'0';//将字符串转换为数字
                    j++;i++;
                }
            }
            q.push(tem);//q是一个既包含数据又包含运算符的结构的队列
        }
        else if(str[i]=='=')continue;
        else
        {
            tem.flag=false;//表示操作符
            while(!s.empty()&&p[str[i]]<=p[s.top().op])
            {
                q.push(s.top());
                s.pop();
            }
            tem.op=str[i];//操作符入栈
            s.push(tem);
        }
    }
    while(!s.empty())
    {
        q.push(s.top());
        s.pop();
    }
    //cout<<"后缀表达式为：";
    while(!q.empty())
    {
        tmp.push(q.front());
        result.push(q.front());
        q.pop();
    }
    while(!result.empty())
    {
        if(result.front().flag==true)
        {
            st.push(result.front().num);
            result.pop();
        }
        else if(result.front().flag==false)
        {
            if(result.front().op=='+')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a1+a2);
                result.pop();
            }
            else if(result.front().op=='-')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a2-a1);
                result.pop();
            }
            else if(result.front().op=='*')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a1*a2);
                result.pop();
            }
            else if(result.front().op=='/')
            {
                int a1=st.top();
                st.pop();
                int a2=st.top();
                st.pop();
                st.push(a2/a1);
                result.pop();
            }
        }
    }
    //return st.top();
}
struct myNode
{
    int num;//操作数
    char op;//操作符
    bool flag;//true表示操作数，false表示操作符
    myNode* lchild;
    myNode* rchild;
    myNode(int d):num(d),lchild(nullptr),rchild(nullptr){};
    myNode(char op):op(op),lchild(nullptr),rchild(nullptr){};
};

class myTree
{
public:
    myNode* root;
    myTree():root(nullptr){};
    void createTree(queue<node>tmp);
};


void myTree::createTree(queue<node>tmp)
{
    stack<myNode*>s1; myNode*my_p;
    while(!tmp.empty())//tmp表示后缀表达式（逆波兰表达式），其中元素是node结构体
    {
        if(tmp.front().flag==true)
        {
            my_p = new myNode(tmp.front().num);
            my_p->flag = true;
            s1.push(my_p);//s1是树的根节点
            tmp.pop();
        }
        else if(tmp.front().flag==false)
        {
            my_p = new myNode(tmp.front().op);
            my_p->flag = false;
            my_p->rchild = s1.top();
            s1.pop();
            my_p->lchild = s1.top();
            s1.pop();
            s1.push(my_p);
            tmp.pop();
        }
    }
    root = s1.top();//构建一个树，返回该树的根节点即可
    if(!s1.empty())
    s1.pop();
}


//去除空格
void removeSpace(string &str)
{
    std::string::size_type index = 0;
    if(!str.empty())
    {
        while((index=str.find(' ',index))!=string::npos)//使用str.find找出第一个空格位置，找到了，返回索引
        //string::npos表示无效或不存在的字符串位置
        {
            str.erase(index,1);//删除字符串中index位置开始的第一个字符
        }
    }
}

//先序遍历，根左右
void preOrder(myNode* root)
{
    if(root==nullptr)return;
    if(root!=nullptr)//先输出根结点的值
    {
        if(root->flag==true)
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }
        preOrder(root->lchild);//再遍历左节点
        preOrder(root->rchild);//最后遍历右结点
    }
}

//中序遍历，左中右
void inOrder(myNode* root)
{
    if(root==nullptr)return;
    if(root!=nullptr)
    {
        inOrder(root->lchild);//先遍历左节点
        if(root->flag==true)//输出根节点的值
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }
        inOrder(root->rchild);//最后遍历右结点
    }
}

//后序遍历，左右根
void postOrder(myNode* root)
{
    if(root==nullptr)return;
    if(root!=nullptr)
    {
        postOrder(root->lchild);//先遍历左节点
        postOrder(root->rchild);//再遍历右结点
        if(root->flag==true)//最后输出根节点的值
        {
            cout<<root->num<<"#";
        }
        else
        {
            cout<<root->op;
        }
    }
}

//层次遍历
void levelOrder(myNode* root)
{
    queue<myNode*>qmp;
    qmp.push(root);
    while(!qmp.empty())//实现宽度优先搜索，根节点出队，左右节点进队
    {
        myNode* pil = qmp.front();
        qmp.pop();
        if(pil->flag==true)
        {
            cout<<pil->num<<"#";
        }
        else
        {
            cout<<pil->op;
        }
        if(pil->lchild!=nullptr)
            qmp.push(pil->lchild);
        if(pil->rchild!=nullptr)
            qmp.push(pil->rchild);
    }
}

int main(void)
{
    //freopen("in.txt", "r", stdin);
    //freopen("abc.out", "w", stdout);
    string str;
    p['+'] = p['-'] = 1;
    p['*'] = p['/'] = 2;
    //cin>>str;
    getline(cin,str);
    removeSpace(str);
    int res=0;
    queue<node>q_tmp ;
    Infix2Sufix(str,q_tmp);
   
    myTree * tree = new myTree;
    tree->createTree(q_tmp);
    
    preOrder(tree->root);
    cout<<endl;
    inOrder(tree->root);
    cout<<endl;
    postOrder(tree->root);
    cout<<endl;
    levelOrder(tree->root);
    cout<<endl;
    cout<<st.top();

    return 0;
}