tableaux de mise en œuvre à l'aide d'une pile

Question

Mon langage de programmation n'a pas des tableaux, pas de listes, pas de pointeurs, pas eval et aucune variable variable. Tout ce qu'il a:

• Les variables ordinaires comme vous les connaissez dans la plupart des langages de programmation: Ils ont tous un nom exact et une valeur.

• Une pile. Fonctions fournies sont: push (Ajouter un élément vers le haut), pop (retirer l'élément de haut, obtenir la valeur) et vide (vérifier si la pile est vide)

Ma langue est Turing-complet. (Arithmétique de base, sauts conditionnels, etc.) Cela signifie qu'il doit être possible d'implémenter une sorte de liste ou de tableau, n'est-ce pas?

Mais je ne sais pas comment ...

Ce que je veux atteindre: Créer une fonction qui peut récupérer et/ou modifier un élément x de la pile.

Je pourrais facilement ajouter cette fonction dans l'implémentation de mon langage, dans l'interpréteur, mais je veux le faire en mon langage de programmation.

• "Solution" une (accès à un élément x, en comptant à partir du haut de la pile)

créer une boucle. Éclatez l'élément du dessus de la pile x fois. Le dernier élément apparu est le numéro d'élément x. Je me retrouve avec une pile détruite.

• Solution deux:

Faites la même chose que ci-dessus, mais stocker toutes les valeurs dans un sauté hors seconde pile. Ensuite, vous pouvez déplacer tous les éléments après que vous avez terminé. Mais tu sais quoi? Je n'ai pas de deuxième pile!

Answer 1

Avez-vous des appels de procédure et récursion? Ensuite, vous avez une deuxième pile, la pile d'appel. Si non, êtes-vous sûr que c'est Turing complet, et pas seulement un PDA?

Answer 2

sonne comme une question de devoirs, comme fléchissant bits aléatoires de l'informatique ...

Je pense que vous voulez utiliser la récursivité pour le faire. Dire que j'ai quelque chose comme ça ..

Queue globalQueue = new Queue(); 

alors je pourrais avoir le code qui a obtenu l'élément X comme celui-ci

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

donc plus que probable que je fait un bug ... ont pas pensé à travers elle super bien. Surtout inquiet que je vais réorganiser la pile à cause de l'ordre de mes appels ..

Espérons que cela peut vous faire réfléchir dans la bonne direction pour obtenir une solution?

Answer 3

Si vous n'avez qu'une seule pile, cela équivaut à un automate à pile, qui peut reconnaître des langages sans contexte et qui n'est pas complet à Turing. Votre preuve de l'exhaustivité de Turing doit indiquer comment implémenter l'accès libre à la mémoire. En général, pour prouver Turing-complétude, vous devez être capable de montrer comment votre langage peut se déplacer de gauche à droite sur une bande (ou simuler indirectement ce processus), ce qui correspond à peu près à un seul tableau de niveau supérieur.