• <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

            題目要求重新寫出給出的后綴表達(dá)式,使原后綴表達(dá)式的棧方法和新表達(dá)式的隊(duì)列方法表示的表達(dá)式相同,也就是兩種表達(dá)式對應(yīng)的表達(dá)式樹相等。
            仔細(xì)想想表達(dá)式樹和隊(duì)列的結(jié)構(gòu),可以發(fā)現(xiàn),輸出為表達(dá)式樹按層次遍歷得到的序列的逆序。
            以下是我的代碼:

            #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) 評(píng)論(1)  編輯 收藏 引用 所屬分類: 題目分類:數(shù)據(jù)結(jié)構(gòu)

            FeedBack:
            # re: UVa 11234 Expressions
            2013-11-16 23:15 | ramboww
            father不需要尋找吧,stack里面最后剩下的肯定就是root了。  回復(fù)  更多評(píng)論
              
            2020久久精品国产免费| 亚洲国产成人久久精品动漫| 国产成人精品久久免费动漫| 久久久久久伊人高潮影院| 韩国三级大全久久网站| 久久丫精品国产亚洲av| 久久久噜噜噜久久熟女AA片| 99精品久久久久久久婷婷| 久久精品国产2020| 久久国产劲爆AV内射—百度| 久久国产免费直播| 欧美喷潮久久久XXXXx| 99国产欧美久久久精品蜜芽| 久久午夜无码鲁丝片| 久久精品亚洲日本波多野结衣| 国产V亚洲V天堂无码久久久| 亚洲国产成人久久综合一| 久久国产精品免费一区二区三区| 久久久精品波多野结衣| 狠狠色丁香久久婷婷综合蜜芽五月| 久久笫一福利免费导航 | 精品国产VA久久久久久久冰| 久久久无码精品亚洲日韩蜜臀浪潮 | 伊人久久大香线蕉精品不卡| 亚洲午夜无码久久久久| 2022年国产精品久久久久| 国产精品美女久久久久AV福利| 久久综合九色综合久99| 久久亚洲日韩精品一区二区三区 | 久久精品国产99久久香蕉| 久久99国产精品久久99小说| 精品国产乱码久久久久久郑州公司 | 99久久国产主播综合精品| 亚洲日本va午夜中文字幕久久| 国产美女久久精品香蕉69| 色悠久久久久久久综合网| 久久综合给久久狠狠97色| 久久综合色之久久综合| 99久久99久久| 麻豆精品久久久久久久99蜜桃| 久久亚洲国产精品一区二区|