切換
舊版
前往
大廳
主題

ZeroJudge - a459: An Easy Language 解題心得

Not In My Back Yard | 2020-09-07 00:00:02 | 巴幣 2 | 人氣 115

題目連結:


題目大意:
輸入給定將本題之符號替換後的 Brainfuck 語言之語句,每個語句之間由多個空白或是換行字元隔開。

Brainfuck 參見維基頁面。其程式語言只由八種符號組成並各自等價 C 語言之語句:
「>」,等價 ++ptr;
「<」,等價 --ptr;
「+」,等價 ++(*ptr);
「-」,等價 --(*ptr);
「.」,等價 putchar(*ptr);
「,」,等價 *ptr = getchar();
「[」,等價 while (*ptr) {
「]」,等價 }
其中 ptr 之型態為 char * ;對於本題是指向一字元陣列 brain[240],並初始化為 ptr = brain (即指向陣列開頭,brain[] 的初始化皆為 0)。

而本題將上述的符號做了額外的替換,對照表如下為:
「>」,對應「(>OwO)>u~(/OwO)/nya~」
「<」,對應「(>OwO)>u~!!(/OwO)/nya~!!」
「+」,對應「(>OwO)>u~!(/OwO)/nya~!」
「-」,對應「(>OwO)>u~!!!(/OwO)/nya~!!!」
「.」,對應「Let's\(OwO)/nya~」
「,」,對應「cosmic!」
「[」,對應「CHAOS CHAOS!」
「]」,對應「I WANNA CHAOS!」

本題無「cosmic!」,也就是「,」,之語句。請輸出給定的輸入語句會輸出的內容。



範例輸入:
(>OwO)>u~(/OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! CHAOS CHAOS! (>OwO)>u~!!(/OwO)/nya~!!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~(/OwO)/nya~ (>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~!!(/OwO)/nya~!!
Let's\(OwO)/nya~ (>OwO)>u~(/OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! CHAOS CHAOS! (>OwO)>u~!!(/OwO)/nya~!! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~(/OwO)/nya~
(>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~!!(/OwO)/nya~!! (>OwO)>u~!(/OwO)/nya~!
Let's\(OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
Let's\(OwO)/nya~ Let's\(OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! Let's\(OwO)/nya~ CHAOS CHAOS! (>OwO)>u~!!!(/OwO)/nya~!!!
I WANNA CHAOS! (>OwO)>u~(/OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! CHAOS CHAOS! (>OwO)>u~!!(/OwO)/nya~!!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~(/OwO)/nya~ (>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~!!(/OwO)/nya~!!
Let's\(OwO)/nya~ (>OwO)>u~(/OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! CHAOS CHAOS! (>OwO)>u~!!(/OwO)/nya~!! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~(/OwO)/nya~ (>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~!!(/OwO)/nya~!!
Let's\(OwO)/nya~ (>OwO)>u~(/OwO)/nya~ (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! CHAOS CHAOS! (>OwO)>u~!!(/OwO)/nya~!!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~(/OwO)/nya~
(>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~!!(/OwO)/nya~!! Let's\(OwO)/nya~
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! Let's\(OwO)/nya~
(>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!!
(>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! Let's\(OwO)/nya~ (>OwO)>u~!!!(/OwO)/nya~!!!
(>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!!
(>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! (>OwO)>u~!!!(/OwO)/nya~!!! Let's\(OwO)/nya~
CHAOS CHAOS! (>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~(/OwO)/nya~
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
CHAOS CHAOS! (>OwO)>u~!!(/OwO)/nya~!! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~(/OwO)/nya~ (>OwO)>u~!!!(/OwO)/nya~!!!
I WANNA CHAOS! (>OwO)>u~!!(/OwO)/nya~!! (>OwO)>u~!(/OwO)/nya~! Let's\(OwO)/nya~
CHAOS CHAOS! (>OwO)>u~!!!(/OwO)/nya~!!! I WANNA CHAOS! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~! (>OwO)>u~!(/OwO)/nya~!
(>OwO)>u~!(/OwO)/nya~! Let's\(OwO)/nya~


範例輸出:
Hello World!


解題思維:
簡單來說,我們要使用一種程式語言去編譯另一種程式語言。



我們可以先分析輸入的語句,將其轉成簡單的符號表示(數字或是單一字元)。將其存成一個轉換後的陣列(轉換並非必要,但是存成陣列這件事是為了之後方便)。

接著就從第一個語句開始執行。那些等價於 ++ptr 、 --ptr 、 ++(*ptr) 、 --(*ptr) 、 putchar(*ptr) 之語句應該沒有什麼問題,就是直接執行其等價的 C 語言之動作。

而比較麻煩的是等價於迴圈的部分,假設現在執行的語句是第 i 個,而該迴圈結束的語句是第 j 個。因為可能有多層的迴圈,因此要找到 j 值需要類似括號匹配的演算法,例如這題。當配對完(堆疊為空)之後的語句位置,即是 j 。

而因為是等價 while(*ptr),所以我們要重複判斷 ptr 現在指向的陣列位置之內容是否 = 0 。如果非 0 ,就要繼續執行第 i + 1 ~ 第 j - 1 個語句,直到 *ptr 之值為 0 。而這部分使用遞迴是比較好處理的。




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

創作回應

更多創作