ZeroJudge - d285: 00727 - Postfix Expression 解題心得

Multi tool use
Multi tool use
(function(w,d,s,l,i)w[l]=w[l])(window,document,'script','dataLayer','GTM-KDKMGT');
(function(d, s, id) var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/zh_TW/all.js#xfbml=1&appId=668497826514848"; fjs.parentNode.insertBefore(js, fjs); (document, 'script', 'facebook-jssdk'));






if(BAHAID)
BAHAID = BAHAID.replace(/&/g, "&")
.replace(/, "<")
.replace(/>/g, ">")
.replace(/"/g, """)
.replace(/'/g, "'");

BAHAIDlow = BAHAID.toLowerCase();

document.write('');

document.write('

');
document.write('');
document.write('');
document.write('');
document.write('

');

//document.write('
');
document.write('
');
document.write('
');
document.write('
');
document.write('
');
document.write('
');
document.write('
');
document.write('
');


else
document.write('
');
document.write('');
document.write('
    ');
    document.write('
  • 我要登入
  • ');
    document.write('
  • 註冊
  • ');
    document.write('
  • ');
    document.write('
');
document.write('
');


document.write('
');

document.write(' ');

(function()
var cx = 'partner-pub-9012069346306566:kd3hd85io9c';
var gcse = document.createElement('script');
gcse.type = 'text/javascript';
gcse.async = true;
gcse.src = 'https://cse.google.com/cse.js?cx=' + cx;
var s = document.getElementsByTagName('script')[0];
s.parentNode.insertBefore(gcse, s);
)();

service = new rsearch('rsearch');

if( BAHAID )
NOTIFY_getnum();
run30 = setInterval("NOTIFY_getnum()",60000);


function insideSecondaryfunc(frm, evt){
if( 0

















breadCrumbs(122, '', 'homeuid=inversion')








    breadCrumbs_listMenu(122, 0, 'homeuid=inversion')





    創作內容





    0 GP


    ZeroJudge - d285: 00727 - Postfix Expression 解題心得


    作者:Not In My Back Yard│2018-10-19 10:29:46│贊助:0│人氣:14

    題目連結:

    d285: 00727 - Postfix Expression





    題目大意:

    給定一個中序運算式,請轉成後序運算式,並輸出於一行。每筆輸出之間要空一行。



    對於每個中序運算式,保證為合法的運算式,並且會以每一行一個字元輸入進來。每一個運算式最多占50行,每個運算式之前必定有一個空行。



    運算元為一位數數字,且運算子都為二元運算子( + - * / )。運算子的優先順序為:先乘除,後加減,並由左至右運算,括號最先算。







    範例輸入:

    2

    (

    3

    +

    2

    )

    *

    5



    3

    +

    2





    範例輸出:

    32+5*



    32+





    解題思維:

    首先,先理解「中序運算式」「後序運算式」到底是什麼:




    「中序運算式」,即是我們一般會看見的運算式形式。例如:2+7 * 8,每個運算子都會被運算元所包圍(除非是一元運算子,或是括號)。




    「後序運算式」,則是電腦方便運算的運算式形式。例如,上面的2+7 * 8的後序運算式為278 * +。而在生成後序運算式時,各個運算子的運算順序已經被考慮進去(包含括號),因此在裡面不會再看到括號的存在。



    可是為何有中序、後序之差?這是因為,每個運算式都可化為一個樹,以上面的2+7 * 8為例,可化為:


    如上圖,是一個二元樹(每個節點最多兩個子樹)。



    我們常見的「中序運算式」便是這棵樹經由「中序探訪」的「路徑」。先走左子樹,接下來是自己,最後再走右子樹。



    相似地,「後序運算式」為這棵樹的「後序探訪」。先走左子樹、再右子樹,最後才走根節點。







    而中序轉後序不需要真的建一棵二元樹,再用後序探訪找路徑。只需要堆疊,在輸入的時候即可轉變成後序運算式。



    以5+7-8 /(6+2)* 2為例:


    先讀入5,一讀入數字即可把它放進後序運算式的結果之中。現結果為5,堆疊為空。




    讀入+,放進堆疊裡。現結果為5,堆疊裡有+。




    讀入7,結果為57,堆疊裡有+。




    讀入-,判斷堆疊的頂端元素的優先順序,是否大於等於現在讀入的運算子之優先度。如果是,就一直把堆疊的頂端元素拿出,直到堆疊為空或是不符合為止。最後再放入現有的運算子。現結果為57+,堆疊裡有-。




    讀入8,結果為57+8,堆疊裡有-。




    讀入 / ,結果為57+8,堆疊裡有- / 。




    讀入(,左括號很特別,要與右括號配對。結果為57+8,堆疊裡有- / (。




    讀入6,結果為57+86,堆疊裡有- / (。




    讀入+,結果為57+86,堆疊裡有- / (+。




    讀入2,結果為57+862,堆疊裡有- / (+。




    讀入),把堆疊的頂端元素拿出,直到遇見(。現結果為57+862+,堆疊裡有- / 。




    讀入 * ,結果為57+862+ / ,堆疊裡有- * 。




    讀入2,結果為57+862+ / 2,堆疊裡有- * 。



    最後把堆疊清空,最終結果即為57+862+ / 2 * -,即是題目所求。






    本人的程式碼(放在CodePile)



    此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。






    喜歡0
    收藏
    0
    引用
    0
    留言
    推上首頁



    檢舉








    引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4166529

    All rights reserved. 版權所有,保留一切權利





    相關創作

    同標籤作品搜尋:程式題目解題心得|堆疊





    ZeroJudge - d904: 換零錢 解題心得




    ZeroJudge - d584: 技能點數skill 解題心得




    ZeroJudge - d583: 幼稚的企鵝 解題心得




    ZeroJudge - d586: 哈密瓜美語 解題心得




    ZeroJudge - d681: BinaryCount 解題心得


    留言共 1 篇留言





    冰水果布丁:
    我覺得可以

    10-19 19:06






    Util.ChangeText('replys', Util.ChangeText.FLAG_LAZYLOAD|Util.ChangeText.FLAG_MAX_SIZE|Util.ChangeText.FLAG_BALA_PLAYER);

    我要留言提醒:您尚未登入,請先登入再留言


    0喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。



    前一篇:ZeroJudge - ...

    後一篇:ZeroJudge - ...








    egg('.MSG-list8C img').each(function(elem)
    elem.className = elem.className + ' lazyload';
    );

    egg('.gallery-image').imageGallery();

    function deleteCreation(vCode)
    var content = egg('.MSG-list8C').html();
    var pattern = /]*?>/i;
    var html = '
    確定要刪除嗎?';
    var width = '200px';
    if(content.match(pattern))
    html += '
    ';

    var boxConfig =
    'closeButton': false,
    'css':
    'width': width

    ;

    egg.mutbox(html, '訊息',
    '確定': function()
    if(egg('#chkDelTruthImage:checked').size())
    egg('[name=delTruthImage]').val('yes');


    egg.cookie.del('ckHOME_CREATION','home.gamer.com.tw','/');
    egg.cookie.set('ckHOME_CREATION',vCode,'home.gamer.com.tw','/');
    document.getElementById('frmDel').submit();
    egg.lightbox.close();
    ,
    '取消': function()
    egg.lightbox.close();

    ,boxConfig);

    var buttonOk = egg('.BH-popbtns :button:eq(0)');
    if(buttonOk.size())
    buttonOk.get(0).focus();



    resizeImage(627);

    egg('.btnGp').click(function()
    $.mutbox('請先登入才能進行此動作', '訊息', '確定':function()location.href='https://user.gamer.com.tw/login.php';);
    );







    訂閱私訊


    作品資料夾


    ZeroJudge (103)


    未分類 (0)


    rw506fr001有緣人
    眾多動漫都是異世界,快來看與眾不同的同人小說《龍武傳,起源之旅》,別再說異世界穿越都是那幾套啦!!看更多我要大聲說7小時前







    googletag.cmd.push(function() googletag.display('div-gpt-ad-1489070677458-0'); );



    (function(window, $)
    var $window = $(window);
    var $document = $(document);
    var $BH_slave = $("#BH-slave");
    var $BH_master = $("#BH-master");
    var $flySalve = $("#flySalve");
    var posY = $flySalve.position().top;
    var fad_style = document.getElementById("flySalve").style;
    var BH_wrapper_width = $('#BH-wrapper').width();
    var BH_topBar_height = $('.TOP-bh').height();
    $(window).on("scroll", function()
    posY = $BH_slave.height() - (fad_style.position === 'fixed' ? 0 : $flySalve.height());

    if ($document.scrollTop() > (posY + $BH_slave.offset().top - BH_topBar_height) && $BH_slave.height() < $BH_master.height())
    fad_style.position = 'fixed';
    fad_style.top = BH_topBar_height + 'px';
    if ($(window).width() < BH_wrapper_width)
    fad_style.left = (BH_wrapper_width - $BH_slave.width() - $document.scrollLeft())+'px';

    else
    fad_style.position = '';

    ).on("resize", function()
    fad_style.left = null;
    );
    )(window, jQuery);
















    face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】





    The name of the picture黑色沙漠手遊伺服器是巴雷諾斯公會缺人名稱是GO歡迎大家查詢到後加入

    This page is only for reference, If you need detailed information, please check here
    The name of the pictureThe name of the picture

    bclpLk,He
    Q b dlEmjvl5kFw,Pif2b t iZg9,VJLN,nv21bQv2UkofHWz zZvEIX Sn0,A,kdst1jl,zlRpp6qE3fQo6GfQaQPaMtk7bXkaymtcph9LK

    Popular posts from this blog

    【情報】本週珍珠商品重點:煉金時裝 + 艾港勞工宿舍!!

    【攻略】陳戈-謝勒汗智慧的古書 (完成)

    【問題】砍劈摔擊的問題