Реализация массивов с использованием стека - PullRequest
Новая
       14

Реализация массивов с использованием стека

2 голосов
/ 02 мая 2010

Мой язык программирования не имеет массивов, списков, указателей, eval и переменных переменных. Все это имеет:

  • Обычные переменные, подобные тем, которые вы знаете по большинству языков программирования: все они имеют точное имя и значение.

  • Один стек. Предоставляются следующие функции: push (добавить элемент в начало), pop (удалить элемент из top, получить значение) и empty (проверить, пуст ли стек)

Мой язык завершен. (Реализована базовая арифметика, условные переходы и т. Д.) Это означает, что должна быть возможность реализовать какой-то список или массив, верно?

Но я понятия не имею, как ...

Чего я хочу добиться: создать функцию, которая может извлекать и / или изменять элемент x стека.

Я мог бы легко добавить эту функцию в реализацию моего языка, в интерпретатор, но я хочу сделать это на моем языке программирования.

  • «Решение» один (Доступ к элементу x, считая с вершины стека)

Создать цикл. Снимите элемент с вершины стека x раз. Последний извлеченный элемент - это номер элемента x. Я получаю разрушенный стек.

  • Решение второе:

Сделайте то же самое, что и выше, но сохраните все извлеченные значения в стеке секунд . Затем вы можете переместить все элементы обратно после того, как вы закончите. Но вы знаете, что? У меня нет второго стека!

Ответы [ 3 ]

3 голосов
/ 02 мая 2010

Звучит как домашнее задание, так как оно изгибает случайные кусочки информатики ...

Думаю, вы захотите использовать рекурсию для этого. Скажем, у меня есть что-то вроде этого .. 

Queue globalQueue = new Queue();

Тогда у меня мог бы быть код, который получил элемент X вот так 

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

Так что скорее всего я сделал какую-то ошибку ... не очень хорошо продумал ее. Особенно волнуюсь, что я буду переупорядочивать стек из-за порядка моих звонков ..

Надеюсь, это поможет вам правильно подумать, чтобы найти решение?

2 голосов
/ 02 мая 2010

Если у вас есть только один стек, это эквивалентно автомату раскрытия, который может распознавать языки без контекста, и не является полным по Тьюрингу. Ваше доказательство полноты по Тьюрингу должно содержать информацию о том, как можно реализовать доступ к памяти произвольной формы.

В общем, чтобы доказать полноту по Тьюрингу, вы должны показать, как ваш язык может перемещаться по ленте по ленте (или косвенно моделировать этот процесс), что примерно соответствует одному массиву более высокого уровня.

2 голосов
/ 02 мая 2010

У вас есть вызовы процедур и рекурсия? Тогда у вас есть второй стек, стек вызовов. Если нет, то уверены ли вы, что это полный Тьюринг, а не просто КПК?

...