SDUTOJ-1646-Complicated Expressions-二叉树的建立

本文主要是介绍SDUTOJ-1646-Complicated Expressions-二叉树的建立，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

由题意，我们可以建立一个二叉树。

然后中序遍历二叉树，得到最终的结果。

在中序遍历二叉树的时候，我们判断当前子树的根节点与其子节点的符号之间的关系。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define LL long long
#define INF 1000000000
using namespace std;
struct list
{char x;int l;int r;int leap;
} node[5001];
char str[10001];
int vnum;
int dos(int x,int y)//把str字符串从x到y这一段转化成
{                  //一颗二叉树，并且返回这颗二叉树的根节点int i,j;if(x==y){node[vnum].l=-1;node[vnum].r=-1;node[vnum].x=str[x];node[vnum].leap=0;vnum++;return vnum-1;}int vis[1001];stack<int>st;while(!st.empty())st.pop();vector<int>vec;vec.clear();int ns,ss;for(i=x; i<=y; i++){if(str[i]=='('){int sts=1;for(j=i+1; j<=y; j++){if(str[j]=='(')sts++;if(str[j]==')')sts--;if(sts==0)break;}int pp=dos(i+1,j-1);vec.push_back(pp);node[pp].leap=0;i=j;}else{vec.push_back(vnum);node[vnum].l=-1;node[vnum].r=-1;node[vnum].leap=1;node[vnum].x=str[i];vnum++;}}int len=vec.size();int ks[1001];int knum;knum=0;for(i=0; i<len; i++){int pp=vec[i];if((node[pp].leap==1)&&(node[pp].x=='*'||node[pp].x=='/')){int xx=ks[knum-1];knum--;node[pp].l=xx;node[pp].r=vec[i+1];i++;}ks[knum++]=pp;}int pa;pa=ks[0];for(i=1; i<knum; i++){int pp=ks[i];node[pp].l=pa;node[pp].r=ks[i+1];pa=pp;i++;}return pa;
}
int need(int x,int y,int leap)//判断以x为根，以y为子节点，在中序遍历的时候是否需要加（）
{if(node[x].x=='/'&&leap==1){if(node[y].x=='+'||node[y].x=='-'||node[y].x=='*'||node[y].x=='/')return 1;}if(node[x].x=='*'||node[x].x=='/'){if(node[y].x=='+'||node[y].x=='-')return 1;}if(node[x].x=='-'&&leap==1){if(node[y].x=='+'||node[y].x=='-')return 1;}return 0;
}
void print(int x)//输出以x为根节点的中序遍历结果
{if(node[x].l!=-1){int ll=node[x].l;if(need(x,ll,0)){putchar('(');print(ll);putchar(')');}else{print(ll);}}putchar(node[x].x);if(node[x].r!=-1){int ll=node[x].r;if(need(x,ll,1)){putchar('(');print(ll);putchar(')');}else{print(ll);}}}
int main()
{int _,i,j;scanf("%d",&_);for(j=1; j<=_; j++){vnum=0;scanf("%s",str);int len=strlen(str);int st=dos(0,len-1);print(st);cout<<endl;}return 0;
}

这篇关于SDUTOJ-1646-Complicated Expressions-二叉树的建立的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---