Acerca del problema de la pila en pascal.
Absolutamente blasfemo.
También tengo folletos de clase PPT de Stack. Por favor envíeme un correo electrónico, gracias. Enviaré el archivo adjunto al correo electrónico.
1 Concepto y funcionamiento de pila
Definición de pila: Una pila es una tabla especial que solo realiza operaciones de inserción y eliminación en la cabecera de la tabla. Por lo tanto, el encabezado tiene un significado especial para la pila y se denomina parte superior de la pila. En consecuencia, el final de la mesa también se denomina parte inferior de la pila. Una pila que no contiene ningún elemento se llama pila vacía.
Estructura lógica de la pila: suponga que los elementos de la pila S son an, an-1,..., a1, entonces a1 se llama el elemento inferior de la pila y an se llama el elemento superior. elemento de la pila. Los elementos de la pila están dispuestos en el orden a1, a2,..., an-1, an. En cualquier momento dado, el elemento que sale de la pila es el elemento superior de la pila. En otras palabras, la pila se modifica según el principio de último en entrar, primero en salir, como se muestra en la Figura 1. Por lo tanto, la pila también se denomina tabla de último en entrar, primero en salir (LIFO), o tabla LIFO para abreviar. Por lo tanto, siempre que el problema satisfaga el principio de último en entrar, primero en salir, puede utilizar la pila.
Operaciones de pila: para tipos de datos abstractos, las operaciones de pila comúnmente utilizadas son:
Significado de la operación
inistack(S) convierte a S en una pila vacía.
getTop(S) Esta es una función cuyo valor es el elemento superior de la pila en S.
Pop(S) elimina el elemento superior de la pila S, lo que se denomina volcado.
Push(S,x) inserta el elemento x en la parte superior de la pila de S, lo que se denomina poner el elemento x en la pila.
Vacío(S) Esta es una función. Cuando S es una pila vacía, el valor de la función es verdadero; de lo contrario, el valor de la función es falso.
2 Almacenamiento e implementación de la pila
Implementación de la pila en matriz: dado que la pila es una tabla especial, podemos usar una matriz para implementar la pila. Teniendo en cuenta la particularidad de la operación de la pila, usamos los elementos de la matriz [1..maxlength] para representar la pila, fijamos la parte inferior de la pila a la parte inferior de la matriz, es decir, los elementos [1] son el primer elemento que ingresa la pila y deje que la pila se expanda hasta la matriz en la parte superior (en la dirección de subíndices crecientes). Al mismo tiempo, usamos el cursor superior para indicar la celda donde se encuentra el elemento superior de la pila actual. Cuando top = 0, la pila es una pila vacía. En general, la secuencia de elementos en elementos[arriba], elementos[arriba-1],..., elemento[1] forma una pila. Esta estructura se muestra en la Figura 2.
Figura 2
Usando la estructura anterior, podemos definir formalmente el tipo de pila TStack de la siguiente manera:
Tipo
TStack=Record
top:integer;
elemento:array[1...maxlength] de TElement;
Fin;
En esta notación , las cinco operaciones básicas de la pila se pueden implementar de la siguiente manera.
procedimiento inistack(Var S:TStack);
comenzar
S.top:=0;
fin;
función Vacío(var S:Stack):Booleano;
comenzar
retorno(S.top=0);
fin; p>
función Vacío(var S:TStack):TElemento;
comenzar
si Vacío(S) entonces Error('La pila está vacía. .')
else return(S.element[S.top]);
end;
procedimiento Pop(var S:TStack);
comenzar
si está vacío(S) y luego Error('La pila está vacía.')
Comenzar
si está vacío(S) y luego Error(' La pila está vacía.'
else dec(S.top); {S.top minus 1}
end;
procedure Push(var S: TStack; x :TElement;);
comenzar
si S.top= longitud máxima entonces Error('La pila está llena.')
si no comenzar
inc(S.top); {S.top incrementa en 1}
S.elementos[S.top]:=x;
end;
end;
end;
La complejidad de cada una de las operaciones anteriores es O(1)
En algunos problemas, puede ser necesario al mismo tiempo. Utilice varias pilas del mismo tipo para evitar que cada pila se desborde durante la ejecución del algoritmo, es necesario colocar un espacio de pila más grande encima de cada pila. Esto tiende a desperdiciar espacio durante la ejecución del algoritmo. La pila generalmente no está llena al mismo tiempo y es probable que algunas estén llenas y otras vacías. Por lo tanto, si varias pilas comparten la misma matriz y se transfieren dinámicamente entre sí, mejorará la utilización del espacio y reducirá la posibilidad de pila. overflow. Supongamos que dejamos que dos pilas en un programa compartan una matriz S[1..n]. Aprovechando la posición constante de la parte inferior de la pila, podemos colocar la parte inferior de las dos pilas en ambos extremos de la matriz. S. y luego estírese hacia el centro respectivamente, como se muestra en la Figura 3. Los valores iniciales en la parte superior de las dos pilas S son 0 y n + 1 respectivamente. El desbordamiento sólo puede ocurrir cuando las partes superiores de las dos pilas se encuentran. Dado que dos pilas pueden complementarse entre sí, el espacio máximo real disponible para cada pila suele ser mayor que n/2.
3 Aplicación de la pila
1. Evaluación de expresiones
Pregunta: ¿Puedes diseñar un algoritmo y escribir un programa que permita a la computadora escanear la siguiente expresión y imprime su valor.
# 3 * ( 4 + 8 ) / 2 -5 #
Nota: Establecer # en la expresión marca el principio y el final del escaneo.
Consejo de algoritmo: configure dos pilas, una es la pila de operandos, utilizada para almacenar operandos, como 3, 4, 8, etc.; la otra es la pila de operadores, utilizada para almacenar operadores.
Primero coloque la bandera "#" en la parte inferior de la pila de operadores.
Luego escanee la pila en secuencia de acuerdo con el principio de último en entrar, primero en salir:
(1) Los operandos encontrados se colocan en la pila de operandos
; p>
(2) cuando se encuentra un operador, la prioridad de este operador debe compararse con la prioridad del operador en la parte superior de la pila
Si un elemento es superior al superior. de la pila se empuja hacia la pila, continúe escaneando el siguiente símbolo.
De lo contrario, extraiga la pila de operadores del elemento superior de la pila para formar un código de operación Q y extraiga la pila de operandos de la parte superior. elemento de la pila dos veces para formar dos operandos a y b. Haga que la computadora complete una operación aritmética en los operandos y códigos de operación, aQb, y almacene el resultado en la pila de operandos….
Simular el proceso de procesamiento informático de expresiones aritméticas. Ingrese una cadena de expresión aritmética desde el teclado (que contenga solo los operadores +, -, ×, ÷, se permiten paréntesis) y genere el valor de la expresión aritmética. La cadena de expresión ingresada debe ser legal.
Programa fuente adjunto:
Programa exsj_1;
const
max=100;
var
p>número: matriz[0...max] de número entero;
símbolo: matriz[1...max] de carácter;
símbolo: matriz[ 2 .max] de char;
s,t:string;
i,p,j,code:integer;
empuje de procedimiento;{calculadora en la pila }
comenzar
inc(p);symbol[p]：=s[i];
end;
procedimiento emergente ;{ el elemento superior de la pila de operadores sale de la pila y saca el elemento de la pila de operandos para completar la operación correspondiente}
begin
dec(p);
p>símbolo de caso[p+1] de
'+': inc(número[p], número[p+1]);
'-' : dec(número[p],número[p+1]);
'*':número[p]:=número[p]*número[p+1];
'/':número[p]：=número[p] número div[p+1];
fin;
fin;
función can :boolean;{determinar la precedencia del operador, crear función de bandera}
comenzar
can：=true;
if (s[i] in ['+ ' , '-'] y (symbol)) '-']) y (symbol[p]<>'(') luego salen;
if (s[i] in ['*', ' /']) y (símbolo[p] en ['*','/']) luego salga;
can：=false;
end;
comenzar
escribir('Cadena: '); readln(s); s:='('+s+')';
mientras que i<=length(s) hago
comienzo
mientras que s[i]='(' hago {manejo del corchete izquierdo]
comienza
push; inc(i);
end;
j:=i;
Repetir {Introducir el número en el operando apilar }
inc(i);
hasta (s[i]<'0') o (s[i]& gt;'9');
t:=copia(s,j,i-j); val(t,número[p],código);
Repetir
si s[i]=') ' Luego {procesamiento del corchete derecho}
comenzar
mientras que el símbolo[p]&& lt;>'('' hace pop;
de
c(p); número[p]：=número[p+1];
end
else
comenzar {operador dentro o fuera dependiendo del valor de la función del símbolo}
while puede hacer pop;<
push;
end;
inc(i);
hasta (i>longitud(es)) o (s[i-1]<>')');
end;
escribir('Resultado =',number[0]) ;
readln;
end.
2. Problema con la mochila
Problema: supongamos que hay n artículos, sus masas se distribuyen como w1, w2,... ¿Se pueden seleccionar algunos artículos de estos n artículos y colocarlos en la mochila, de modo que la masa total de los artículos seleccionados sea exactamente igual a la masa máxima que puede soportar la mochila? mantener, es decir, wi1+ wi2+…. +wik=T. Si es así, entonces el problema de la mochila tiene solución, de lo contrario no tiene solución.
Idea de algoritmo: primero, seleccione n artículos en una fila en secuencia; si después de cargar un artículo, la masa total de los artículos en la mochila no excede la masa máxima de carga de la mochila, luego cargue ( poner en la pila); de lo contrario, deje de seleccionar este artículo y elija el siguiente artículo para probar hasta que el número total de artículos cargados sea exactamente la calidad de reproducción máxima de la mochila. En este punto decimos que la mochila está cargada.
Si la mochila no está llena y no hay otros artículos que se puedan seleccionar en la mochila, significa que hay artículos no calificados que se han cargado en la mochila, por lo que debemos retirar el último cargado. elemento de la mochila (sin apilar), luego seleccione los elementos descargados y repita el proceso hasta que la mochila esté llena (solución disponible) o no se pueda seleccionar ningún elemento (sin solución).
Implementación específica: Usemos los arrays peso[1,.N], pila[1,N] para almacenar el peso del artículo y el número de serie del artículo que se ha cargado en la mochila. (apilar), y use MaxW para indicar la capacidad de carga máxima de la mochila. Cada vez que se coloca un artículo en la pila, la masa del artículo se resta de MaxW y i se establece en el número de serie del artículo a seleccionar. Si MaxW-weight[i]>=0, el artículo se puede seleccionar. seleccionado; si MaxW -weight [i] <0, entonces el elemento no se puede seleccionar. Si i> n, debe regresar a la pila. Si la pila está vacía en este momento, significa que no hay solución.
Función de referencia implementada en Pascal:
Función knapstack(n,MaxW,weight);
begin
top:=0 ; i:=1; {i es el número de artículo a seleccionar}
mientras que (MaxW>0) y (i < = n)
comienzan
comenzar top:=top+1; stack[top]：=i; i] fin;
{i-ésimo artículo en la mochila}
si MaxW=0 entonces regresa(verdadero)
si no, comienza
si (i=n) y (top>0) entonces {artículo inadecuado en la mochila}
comience {tome el artículo superior de la pila, restaure el valor MaxW}
i:=stack[top]; top:=top-1;MaxW=MaxW+ peso[i];
si top>0 entonces comienza
i:= stack [arriba]; arriba:=arriba-1;MaxW=MaxW+ peso[i];
fin;
fin;
i：=i+ 1;
end;
end;
end;
end;
return(false) { El problema no se puede resolver}
fin;
Ejercicio: Problema completo de la mochila