哈哈哈，活了，寒假好好刷题，过来参加了个前端培训，教了一天ps？？？？？？明天不听了，上课刷题。还有，紫书上的表达式树的板子好像有问题
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <string> #include <map> using namespace std; const int maxn=50000+100; int dd[maxn]; int k,t,cnt,p; string ss; struct note { string cc; int aa,left,right; bool operator < (const note &p) const//map要有序 { if(aa!=p.aa) return aa<p.aa; if(left!=p.left) return left<p.left; return right<p.right; } }s[maxn]; map<note,int> mmp; int solved() { int id=cnt++; note &nn=s[id]; nn.aa=0; nn.left=nn.right=-1; nn.cc=""; while(isalpha(ss[p]))//存个节点 { nn.aa=nn.aa*27+ss[p]-'a'+1; nn.cc.push_back(ss[p]); p++; } if(ss[p]=='(')//二叉树，只要所有左括号，必有逗号和右括号 { p++; nn.left=solved(); p++;//逗号 nn.right=solved(); p++;//右括号 } if(mmp[nn])//已经存在，跳过 { cnt--; return mmp[nn]; } return mmp[nn]=id; } void print(int v) { if(dd[v]==k) printf("%d",v+1);//dd[v]就是个标记的作用，拿每层的k标记，就不用清零了 else { dd[v]=k; cout << s[v].cc; if(s[v].left!=-1)//同上二叉树性质 { putchar('('); print(s[v].left); putchar(','); print(s[v].right); putchar(')'); } } } int main() { scanf("%d",&t); for(k=1;k<=t;k++) { mmp.clear(); p=cnt=0; cin >> ss; print(solved()); printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8325487.html
相关资源：数据结构—成绩单生成器