使用堆棧實現數組

我的編程語言沒有數組，沒有列表，沒有指針，沒有eval也沒有變量變量。它所具有：使用堆棧實現數組

像你這樣的普通變量從大多數編程語言中瞭解他們：他們都有一個確切的名稱和值。
一個堆棧。提供的功能有：推（添加元素頂部），流行（從上刪除元素，得到的值）和空（檢查堆棧是空的）

我的語言是圖靈完備。（基本算術，條件跳轉等）這意味着，它必須有可能實現某種列表或數組，對嗎？

但我不知道我該怎麼...

想實現什麼：創建可檢索和/或改變一個元素x棧的功能。

我可以很容易地在執行我的語言時添加這個函數，在解釋器中，但是我想用來編寫我的編程語言。

「解決方案」一（訪問的元素x，從堆棧頂部算起）

創建一個循環。彈出堆棧頂部的元素x次。彈出的最後一個元素是元素號x。我結束了一個破壞的堆棧。

解決方法二：

執行與上述相同的，但存儲在第二堆棧中的所有彈出值。然後，您可以在完成後將所有元素移回。但你知道嗎？我沒有第二個堆棧！

來源

2010-05-02 Zack

聽起來像'Forth'：http://en.wikipedia.org/wiki/Forth_(programming_language） – 2010-05-02 15:53:22

雖然Forth有指針和分配（它給了它數組）和第二個堆棧。 – 2010-05-02 16:01:23

你有過程調用和遞歸嗎？然後你有第二個堆棧，即調用堆棧。如果不是，你確定它是圖靈完整的，而不僅僅是一個PDA？

來源

2010-05-02 16:00:20

我有一個調用堆棧，是的 - 但它不能從內部語言訪問。它是口譯員的內部組成部分。 – Zack 2010-05-02 16:03:52

不需要直接訪問。如果您的過程可以具有局部變量並支持遞歸，則可以使用它們來恢復堆棧。 – 2010-05-02 16:05:28

當然，只是在你迴歸時緩衝和推動堆棧彈出。但是，在你的問題中表明你只有一個堆棧有點誤導。 – WhirlWind 2010-05-02 16:09:20

聽起來像是一門功課的問題，因爲它彎曲計算機科學的隨機位...

我想你可能需要使用遞歸來做到這一點。說我有這樣的事情..

Queue globalQueue = new Queue();

然後，我可以有一個有這樣

public Object findElement(stepsToTake s) { 

    if (queue.empty()) { 
     throw new EmptyQueueYouFailException(); 
    } 

    Object o = queue.pop(); 


    if (s == 0) { 
     queue.push(o); 
     return o; 
    } 

    Object actualResult = findElement(s - 1); 
    //restore this element to the stack 
    queue.push(o); 
    //return actual result 
    return actualResult; 
}

所以較有可能我做了一些錯誤的元素X代碼......沒有經過它認爲超級好。尤其是擔心我會重新排序，因爲我調用的順序堆..

希望這可以讓你沿着正確的思路思考得到一個解決方案嗎？

來源

2010-05-02 16:01:35 bwawok

那麼你如何存儲o？ – WhirlWind 2010-05-02 16:03:50

那麼我抓住o頂部..然後無論是基地案件或遞歸案件，o得到恢復。我不認爲我用算法丟失了任何o，但是我沒有想過通過什麼順序最終在 – bwawok 2010-05-02 16:05:34

之前和之後感謝你的代碼示例，我想我現在有一些想法。順便說一句：你爲什麼認爲這是作業？我的意思是......我沒有提到特定的編程語言，也沒有要求代碼！但是，您的代碼示例不適用於我的語言：它沒有範圍，因此變量o將被下一個函數調用覆蓋。 – Zack 2010-05-02 16:07:13

如果你只有一個堆棧，這相當於一個下推自動機，它可以識別上下文無關的語言，而不是圖靈完成的。你對圖靈完備性的證明應該告訴你如何實現自由形式的內存訪問。

通常，要證明圖靈完備性，您必須能夠顯示語言如何從磁帶上左右移動（或間接模擬此過程），它大致對應於單個更高級別的數組。

來源

2010-05-02 16:02:38 WhirlWind

奇怪：http://stackoverflow.com/questions/1389981/can-a-language-be-turing-complete-without-any-support-for-arrays – Zack 2010-05-02 16:18:29

這是一個理解什麼「對陣列的任何支持」手段。 lambda演算中沒有數組作爲原語，但是你可以創建數組（無論如何，數組通常被理解爲暗示關於實現的某些事情，並最終關於硬件的某些事情）從它提供給你的原語中創建。 – 2010-05-02 16:24:22

@Zack然而，您可以通過將函數鏈接在一起來模擬像列表這樣的線性數據結構。「 - 從那個問題。如果你對一個堆棧的聲明是真的，你會如何用這種語言做到這一點？ – WhirlWind 2010-05-02 16:25:09

使用堆棧實現數組

回答

相關問題