program pilas; const l = 0; r = 1; max = 29; { tama¤o expresi¢n} max_num_proc = 32; { k = 4; { log de 16, altura de arbol}} decmax = 15 {max - 1}; dosmax = 30 {2*decmax}; type expresiones = array [0..max] of integer; nodos_paren = record left, right :integer end; arboles_paren = array [0 .. dosmax] of nodos_paren; nodo_pila = record pos : integer; tipo: integer end; tipo_pila = array [0..10] of nodo_pila; tipo_first_end = array[0 ..max_num_proc] of integer; tipo_matched = array[0..max] of integer; var exp : expresiones; arb_paren : arboles_paren; nivel : integer; {contador del nivel del arbol} k : integer ; { log2 max} ini, fin : integer; i : integer ; {recorre expresion} firstleft, endright : tipo_first_end; num_proc : integer; {numero de procesadores} matched : tipo_matched; procedure log2(numero: integer; var result: integer); begin if numero <= 0 then write('Error al calcular log2 de ',numero) else begin result := 0; while &result < numero do result := result + 1; end; end; task ini_pila(pila:tipo_pila; var top: integer); {apunta al £ltimo ocupado} begin top := -1 end; task ins_pila(pila:tipo_pila; i, x: integer; var top: integer); var nodo : nodo_pila; begin nodo.pos := i; nodo.tipo := x; top := top + 1; pila[top] := nodo; end; task ext_pila(pila:tipo_pila;var nodo: nodo_pila; var top:integer); begin nodo := pila[top]; top := top - 1; end; task ini_arbol_paren(i, x: integer); { Convierte un elemento de expresi¢n en un nodo del  rbol de par‚ntesis. Si se encuentra un n£mero lo pone como )0,(0. i es la posici¢n y x el tipo: ),( o n£mero. } begin if x = l then {si es un "("} begin arb_paren[(&k -1) + i].left := 1; arb_paren[(&k -1) + i].right := 0 end else if x = r then { si es un ")"} begin arb_paren[(&k -1) + i].left := 0; arb_paren[(&k -1) + i].right := 1 end else {es un operanmdo o un operador} begin arb_paren[(&k -1) + i].left := 0; arb_paren[(&k -1) + i].right := 0 end end; begin exp[ 0] := l; exp[ 1] :=l; exp[ 2] :=l; exp[ 3] :=7; exp[ 4] :=r; exp[ 5] := 3; exp[ 6] := l; exp[ 7] :=7; exp[ 8] :=r; exp[ 9] :=3; exp[10] :=l; exp[11] := 7; exp[12] := r; exp[13] :=r; exp[14] :=4; exp[15] :=l; exp[16]:= l; exp[17] := 7; exp[18] := r; exp[19] :=5; exp[20] :=l; exp[21] :=7; exp[22]:= r; exp[23] := r; exp[24] := 4; exp[25] :=l; exp[26] :=7; exp[27] :=r; exp[28]:= r; log2(max, k); num_proc := max div k; if max mod k <> 0 then num_proc := num_proc + 1; writeln('max:', max,' k:',k , 'num_proc:', num_proc);{ (**************) } for i := 0 to num_proc - 1 do begin firstleft[i] := -1; endright[i] := -1; end; for i := 0 to max - 1 do matched[i] := -1; writeln('++++++++++empieza parallel++++++++++++++++'); parallel 0..(num_proc - 1) do var lim_inf, lim_sup : integer; {rango de expresion que trata name} i : integer; top : integer; {cima de pila} sim : integer; {elemento de la expresion} pila : tipo_pila; cima : nodo_pila; begin lim_inf := name * k; lim_sup := (name + 1) * k; if name = num_proc - 1 then {el ultimo procesador} begin lim_inf := name * k; lim_sup := max; end; i := lim_inf; ini_pila(pila, top); while i <= lim_sup do begin sim := exp[i]; ini_arbol_paren(i, sim); {lo introduce en arbol_paren} if sim = l then {si es un "("} begin if firstleft[name] = -1 then {el primero que aparece} firstleft[name] := i; ins_pila(pila, i, l, top); end else if sim = r then {parent cerrar} begin if top <> -1 then {pila no vacia} begin cima := pila[top]; if cima.tipo = l then { situacion "()" :simplificar} begin ext_pila(pila, cima,top); matched[cima.pos] := i; {ya conozco el cierre de ellos} matched[i] := cima.pos; if cima.pos = firstleft[name] then {era el primer "("} firstleft[name] := -1; {ya no lo es} end else {en la cima hay un ")" } endright[name] := i; {es el ultimo ")"} end else { la pila esta vacia} endright[name] := i ; {no hace falta meterlo en pila} end else {es un operando o un operador} begin end; i := i + 1; end; end; for i := 0 to max - 1 do write(arb_paren[(&k - 1) +i].left, arb_paren[(&k - 1) +i].right,' '); writeln(''); for i := 0 to num_proc - 1 do write(firstleft[i], endright[i],' '); writeln(''); for i := 0 to max - 1 do write(matched[i],' '); end.