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

(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('

');

else
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

題目大意：

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

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

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

範例輸入：

(

)

範例輸出：

32+5*

32+

解題思維：

首先，先理解「中序運算式」、「後序運算式」到底是什麼：

「中序運算式」，即是我們一般會看見的運算式形式。例如：２＋７ * ８，每個運算子都會被運算元所包圍（除非是一元運算子，或是括號）。

「後序運算式」，則是電腦方便運算的運算式形式。例如，上面的２＋７ * ８的後序運算式為２７８ * ＋。而在生成後序運算式時，各個運算子的運算順序已經被考慮進去（包含括號），因此在裡面不會再看到括號的存在。

可是為何有中序、後序之差？這是因為，每個運算式都可化為一個樹，以上面的２＋７ * ８為例，可化為：

如上圖，是一個二元樹（每個節點最多兩個子樹）。

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

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

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

以５＋７－８ /（６＋２）* ２為例：

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

讀入＋，放進堆疊裡。現結果為５，堆疊裡有＋。

讀入７，結果為５７，堆疊裡有＋。

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

讀入８，結果為５７＋８，堆疊裡有－。

讀入 / ，結果為５７＋８，堆疊裡有－ / 。

讀入（，左括號很特別，要與右括號配對。結果為５７＋８，堆疊裡有－ / （。

讀入６，結果為５７＋８６，堆疊裡有－ / （。

讀入＋，結果為５７＋８６，堆疊裡有－ / （＋。

讀入２，結果為５７＋８６２，堆疊裡有－ / （＋。

讀入），把堆疊的頂端元素拿出，直到遇見（。現結果為５７＋８６２＋，堆疊裡有－ / 。

讀入 * ，結果為５７＋８６２＋ / ，堆疊裡有－ * 。

讀入２，結果為５７＋８６２＋ / ２，堆疊裡有－ * 。

最後把堆疊清空，最終結果即為５７＋８６２＋ / ２ * －，即是題目所求。

本人的程式碼（放在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 += '
若文中有我上傳至巴哈的圖片也一併刪除';
width = '350px';

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);

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

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

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

搜尋此網誌

Dyjtyuk