• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0

            題目要求重新寫出給出的后綴表達式,使原后綴表達式的棧方法和新表達式的隊列方法表示的表達式相同,也就是兩種表達式對應的表達式樹相等。
            仔細想想表達式樹和隊列的結構,可以發現,輸出為表達式樹按層次遍歷得到的序列的逆序。
            以下是我的代碼:

            #include<stack>
            #include
            <queue>
            #include
            <cstdio>
            #include
            <cstring>
            using namespace std;
            const int kMaxl(10007);

            struct Node
            {
                
            int father,left,right;
            };

            char r[kMaxl];
            Node tree[kMaxl];
            int ans[kMaxl];

            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */

                
            int T;
                scanf(
            "%d",&T);
                
            while(T--)
                {
                    scanf(
            "%s",r);

                    
            int n(strlen(r));
                    stack
            <int> s;
                    memset(tree,
            -1,kMaxl*sizeof(Node));
                    
            for(int i=0;i<n;i++)
                    {
                        
            if(r[i]>='a' && r[i]<='z')
                            s.push(i);
                        
            else
                        {
                            
            int x,y;
                            y
            =s.top();
                            s.pop();
                            x
            =s.top();
                            s.pop();
                            tree[i].left
            =x;
                            tree[i].right
            =y;
                            tree[x].father
            =tree[y].father=i;
                            s.push(i);
                        }
                    }

                    
            /*
                    for(int i=0;i<n;i++)
                        printf("%d %d %d\n",tree[i].father,tree[i].left,tree[i].right);
                    //
            */

                    
            int root;
                    
            for(int i=0;i<n;i++)
                        
            if(tree[i].father==-1)
                        {
                            root
            =i;
                            
            break;
                        }
                    queue
            <int> q;
                    
            int len=0;
                    memset(ans,
            0,kMaxl*sizeof(int));
                    q.push(root);
                    
            while(!q.empty())
                    {
                        
            int t(q.front());
                        q.pop();
                        ans[len
            ++]=t;
                        
            if(tree[t].left!=-1)
                            q.push(tree[t].left);
                        
            if(tree[t].right!=-1)
                            q.push(tree[t].right);
                    }
                    
            for(int i=len-1;i>=0;i--)
                        printf(
            "%c",r[ans[i]]);
                    printf(
            "\n");
                }

                
            return 0;
            }
            posted on 2011-04-13 12:06 lee1r 閱讀(611) 評論(1)  編輯 收藏 引用 所屬分類: 題目分類:數據結構

            FeedBack:
            # re: UVa 11234 Expressions
            2013-11-16 23:15 | ramboww
            father不需要尋找吧,stack里面最后剩下的肯定就是root了。  回復  更多評論
              
            青青热久久国产久精品 | 久久丝袜精品中文字幕| 97久久香蕉国产线看观看| 久久免费的精品国产V∧| 亚洲国产精品无码久久一区二区 | 久久福利青草精品资源站免费| 亚洲精品乱码久久久久久中文字幕| 2021国内精品久久久久久影院| 亚洲国产成人精品91久久久 | www亚洲欲色成人久久精品| 久久综合九色综合97_久久久| 91精品观看91久久久久久| 99久久国产综合精品网成人影院| 国产福利电影一区二区三区久久久久成人精品综合 | 天天爽天天狠久久久综合麻豆| 亚洲精品乱码久久久久久| 欧美丰满熟妇BBB久久久| 丁香五月网久久综合| 久久夜色撩人精品国产| 中文字幕无码免费久久| 久久精品亚洲中文字幕无码麻豆| 久久精品国产一区| 中文字幕亚洲综合久久菠萝蜜| 一本一本久久a久久综合精品蜜桃| 久久精品国产亚洲AV香蕉| 久久se这里只有精品| 中文字幕日本人妻久久久免费| 久久久久免费精品国产| 亚洲一区精品伊人久久伊人 | 亚洲午夜久久久精品影院| 久久男人AV资源网站| 日韩人妻无码一区二区三区久久 | 久久―日本道色综合久久| 日韩欧美亚洲国产精品字幕久久久| 日日噜噜夜夜狠狠久久丁香五月| 国产日韩久久免费影院| 久久精品无码一区二区无码 | 久久精品国产亚洲AV不卡| 99久久www免费人成精品| 精品无码久久久久国产动漫3d| 中文精品久久久久国产网址|