home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS - Coast to Coast / simteldosarchivecoasttocoast2.iso / calculat / doit.zip / DO_RPN.PAS < prev    next >
Pascal/Delphi Source File  |  1989-09-24  |  16KB  |  531 lines

  1. { $ DEFINE DEBUG}
  2.  
  3. Unit do_rpn;
  4.  
  5. (*
  6. ┌───────────────────────────────────────────────────────────────────────────┐
  7. │                          Unidad DO_RPN.PAS                                │
  8. ├───────────────────────────────────────────────────────────────────────────┤
  9. │   Versión             : 1.0                                               │
  10. │   Computadora         : IBM-PC o compatible                               │
  11. │   Lenguaje            : Turbo Pascal 5.5                                  │
  12. │   Autor               : Bernardo Zamora Etcharren                         │
  13. ├──────────────────┬────────────────────────────────────────────────────────┤
  14. │   Explanation :  │                                                        │
  15. ├──────────────────┘                                                        │
  16. │   Unit that converts a string (fun_string) to its equivalente in rpn...   │
  17. │   (rpn_string). It also uses the stack reserved for that purpose (s1),    │
  18. │    with its associated pointer P1.                                        │
  19. │                                                                           │
  20. │    First, in stack 1 it puts the numbers, in the second the operations    │
  21. │    and then it performs the conversion, leaving the result in stack 1.    │
  22. │    operacion!!!.                                                          │
  23. │                                                                           │
  24. │    We need to check operation 3(3), we need to notice that when we finish │
  25. │    and we check the stack!!                                               │
  26. │                                                                           │
  27. │   Also check user typing 'XX' as part of the function, the program        │
  28. │    takes it as a lone 'X'.                                                │
  29. │                                                                           │
  30. │  IMPORTANT : we should substitute all nodes 'U', and '-' (meaning the     │
  31. │  internal representation of unary minus [change-sign]) to the real        │
  32. │  representation of CHS, propably #241 = '±' !!! (what do you think!!)     │
  33. │                                                                           │
  34. │                                                                           │
  35. └───────────────────────────────────────────────────────────────────────────┘
  36. *)
  37.  
  38.  
  39. INTERFACE
  40.  
  41. Uses
  42.   do_type;
  43.  
  44. Procedure convierte_a_polaca (var rpn: rpn_type);
  45.  
  46.  
  47. IMPLEMENTATION
  48.  
  49. const
  50.   CHANGE_SIGN = '±';   { symbol for change-sign operation }
  51.  
  52. var
  53.   operaciones_simples : set of char; {*,+,-,/, son BINARIAS}
  54.   numeros,
  55.   operaciones,               { letters that make up the op_codes (unary)    }
  56.   variables,                 { variable chars accepted (x,p,e..)            }
  57.   parentesis    : set of char;
  58.  
  59.   auxstring,                 { auxiliary string for conversion              }
  60.   sig_arg       : string;    { next word belonging to the expression        }
  61.   valor         : real;      { value to evaluate                            }
  62.  
  63.   tipo_anterior : char;      { for the '-' unary                            }
  64.   nodo          : do_element;
  65.   s2            : do_stack;
  66.   p2            : integer;   { pointer to first element in each stack       }
  67.  
  68.  
  69.  
  70. Procedure convierte_a_polaca (var rpn : rpn_type);
  71.  
  72.  
  73. Procedure do_error(num:integer; s:string);
  74. begin
  75.   rpn.error := num;
  76.   rpn.message := s;
  77. end;
  78.  
  79.  
  80. Procedure Inicializa;
  81. var
  82.   i : integer;
  83. begin
  84.   do_error(0,'');
  85.   tipo_anterior := ' ';
  86.  
  87.   operaciones_simples := ['+','-','*','/','^'];
  88.   numeros := ['0','1'..'9','.'];
  89.   operaciones := ['A'..'Z']; { like Coseno, Seno... }
  90.   variables := ['X'];
  91.   parentesis := ['(','{','[',']','}',')'];
  92.  
  93.   rpn.p1:=0; p2:=0; { also contain the number of elements in stacks }
  94.   { the rpn.s1[0] and s2[0] are empty, only used to check the operations
  95.     made before more esily }
  96.   for i:=0 to MAXSTACK do begin
  97.     rpn.s1[i].tipo:=' ';
  98.     s2[i].tipo:=' ';
  99.   end;
  100. end;
  101.  
  102.  
  103. Procedure push(cual:integer); { cual = which stack (1 or 2) }
  104. { inserts the element NODO to the stack }
  105. begin
  106.   {$IFDEF DEBUG}
  107.     writeln('pushing ',nodo.tipo,' to ',cual);
  108.   {$ENDIF}
  109.   case cual of
  110.     1: begin
  111.          inc(rpn.p1);
  112.          rpn.s1[rpn.p1]:=nodo;
  113.        end;
  114.     2: begin
  115.          inc(p2);
  116.          s2[p2]:=nodo;
  117.        end;
  118.     else do_error(ERROR_PUSH,ERROR_PUSH_S);
  119.   end;
  120. end;
  121.  
  122.  
  123. procedure pop(cual:integer);
  124. { returns the element in stack CUAL to variable NODO }
  125. begin
  126.   case cual of
  127.   1: with rpn do begin
  128.          nodo:=s1[p1];
  129.          dec(p1);
  130.          if p1<0 then begin
  131.            p1:=0;
  132.            do_error(ERROR_PARENTESIS,ERROR_PARENTESIS_S);
  133.          end;
  134.        end;
  135.   2: begin
  136.          nodo:=s2[p2];
  137.          dec(p2);
  138.          if p2<0 then begin
  139.            p2:=0;
  140.            do_error(ERROR_PARENTESIS,ERROR_PARENTESIS_S);
  141.          end;
  142.        end;
  143.   else do_error(ERROR_POP,ERROR_POP_S);
  144.   end;
  145.   {$IFDEF DEBUG}
  146.   writeln('poping ',nodo.tipo,' from ',cual);
  147.   {$ENDIF}
  148. end;
  149.  
  150.  
  151. Procedure get_next_arg(var donde:integer);
  152. { gets next word }
  153. var
  154.   letra         : char;
  155.   encontre_primera_letra:boolean;
  156.   encontre_fin  : boolean;
  157.   aux           : string; { auxiliary string to create the string to be returned }
  158. begin
  159.   aux:='';
  160.   encontre_primera_letra:=false;
  161.   repeat
  162.     letra := auxstring[donde];
  163.     if (letra<>' ') or (donde>=length(AuxString)) then
  164.       encontre_primera_letra:=true;
  165.     inc(donde);
  166.   until encontre_primera_letra;
  167.   dec(donde);
  168.   { as it is over or we found a correct letter, we continue till finding
  169.     the end or finding an space }
  170.   encontre_fin:=false;
  171.   if donde>=length(AuxString) then { we reached the end }
  172.     encontre_fin:=true;
  173.   while not encontre_fin do begin
  174.     inc(donde);
  175.     aux:=aux+letra;
  176.     letra:=AuxString[donde];
  177.     if (letra=' ') or (donde>=length(AuxString)) then
  178.       encontre_fin:=true; { this can be optimized! }
  179.   end;
  180.   if letra<>' ' then aux:=aux+letra; { last letter }
  181.   sig_arg:=aux;
  182. end;
  183.  
  184.  
  185. procedure verifica_II; { second sintax filter }
  186. { verifies all nodes as they are being created... }
  187. var
  188.   i             : integer;
  189.   found_match   : boolean;
  190.   aux           : string;            { for error messages }
  191.   a,b           : string[MaxOpSize]; { auxiliar strings   }
  192. begin
  193.   { First : check if node is operation and it exists }
  194.   found_match:=false;
  195.   if nodo.tipo = 'U' then begin
  196.     for i:=1 to MaxOperaciones do
  197.       if nodo.operacion = arreglo[i] then
  198.         found_match:=true;
  199.     if not found_match then begin
  200.       do_error(ERROR_UNRECOGNIZE,ERROR_UNRECOGNIZE_S);
  201.       rpn.message := rpn.message + nodo.operacion;
  202.     end;
  203.   end;
  204.  
  205.   a:=nodo.operacion; {NUEVO NODO, b= NODO ANTERIOR}
  206.   { Second : check for empty parenthesis }
  207.   if nodo.tipo = 'P' then begin
  208.     if (s2[p2].tipo= 'P') and (p2>0) then begin { there is another parenthesis }
  209.       if ( b[1] in ['{','[','('] ) and
  210.          ( a[1] in ['}',']',')'] ) then
  211.         do_error(ERROR_PARENTESIS_VACIOS,ERROR_PARENTESIS_VACIOS_S);
  212.       {$IFDEF DEBUG}
  213.       writeln(' we made the comparision')
  214.       {$ENDIF}
  215.     end;
  216.   end; {parenthesis}
  217.   b:=nodo.operacion; { saved }
  218.  
  219.   { Third : for unary minus (-) check if the preceding node was a parenthesis
  220.     (opening) or was the first node }
  221.   if (nodo.tipo = 'O') and (nodo.operacion='-') then begin
  222.     if rpn.p1+p2 = 0 then { It is the first node  } { ++ }
  223.       nodo.tipo:='U'      { Now we know its unary }
  224.     else if b[1] in ['}',']',')'] then
  225.       nodo.tipo:='U';
  226.     { Node before was parenthesis and p1+p2>0 }
  227.   end;
  228. end;
  229.  
  230.  
  231.  
  232. Function es_constante(arg:char; VAR num:real):boolean;
  233. var
  234.   i : integer;
  235. begin
  236.   es_constante:=false;
  237.   for i:=1 to MaxConstantes do begin
  238.     if constantes[i].letra=arg then begin
  239.       es_constante:=true;
  240.       num:=constantes[i].valor;
  241.     end;
  242.   end;
  243. end;
  244.  
  245.  
  246.  
  247. procedure interpreta_arg;
  248. { checks to see if its Operation, Variable, Number and fills the node NODO }
  249. var
  250.   chistoso : integer; { returns error when converting number }
  251. begin
  252.   nodo.numero:=0;
  253.   nodo.operacion:='?';
  254.   {$IFDEF DEBUG}
  255.   write('The expression [',sig_arg:MaxOp,'] is : ');
  256.   {$ENDIF}
  257.   if sig_arg[1] in numeros then begin
  258.     nodo.tipo:='N';
  259.     val(sig_arg,nodo.numero,chistoso);
  260.     end
  261.   else if (sig_arg[1] in variables) and (length(sig_arg)=1) then begin
  262.     nodo.tipo:='V';
  263.     nodo.operacion:=sig_arg[1];
  264.     end
  265.   else if (es_constante(sig_arg[1],nodo.numero)) and (length(sig_arg)=1) then begin
  266.     nodo.tipo:='N';
  267.     { the function constant(arg,value) changed the value of the node }
  268.     end
  269.   else if sig_arg[1] in operaciones then begin { unary operations }
  270.     nodo.tipo:='U';
  271.     nodo.operacion:=sig_arg;
  272.     end
  273.   else if sig_arg[1] in operaciones_simples then { binary operations }
  274.     begin
  275.     nodo.tipo:='O';
  276.     nodo.operacion:=sig_arg[1];
  277.     if sig_arg[1]='-' then begin { can be a unary minus [-] }
  278.       if (rpn.p1=0 {no hay digitos antes}) or (tipo_anterior='O') then
  279.         nodo.tipo := 'U';
  280.     end;
  281.     end
  282.   else if sig_arg[1] in parentesis then begin
  283.     nodo.tipo:='P';
  284.     nodo.operacion:=sig_arg[1];
  285.     end
  286.   else begin
  287.     nodo.tipo:='X';
  288.     do_error(ERROR_UNRECOGNIZE,ERROR_UNRECOGNIZE_S);
  289.     rpn.message := rpn.message + sig_arg;
  290.   end;
  291.   {$IFDEF DEBUG}
  292.   with nodo do
  293.     writeln('TP = [',tipo:1,']  NU = [',
  294.     numero:7:2,']  OP = [',operacion:MaxOp,']');
  295.   {$ENDIF}
  296.   verifica_II; { checks the node }
  297.   Tipo_anterior := 'X';
  298.   { 'O'=ok, 'X'=no. Tells if next operation can be (-) unary }
  299.   if (sig_arg[1] in ['(','[','{']) then
  300.     Tipo_anterior :='O';
  301. end;
  302.  
  303.  
  304. procedure hace_la_operacion;
  305. { node contains the operation to insert in stack }
  306. var
  307.   aux,a2 : string[MaxOpSize]; { for operation inside parenthesis }
  308. begin
  309.   case nodo.tipo of
  310.   'P': begin
  311.          aux:=nodo.operacion;
  312.          if (aux[1] in ['{','[','('] ) then
  313.            push(2)
  314.          else begin { closing parenthesis }
  315.            if p2=0 then begin
  316.              do_error(ERROR_EXTRA_PARENTESIS,ERROR_EXTRA_PARENTESIS_S);
  317.              rpn.message := rpn.message + aux;
  318.            end;
  319.            a2:=s2[p2].operacion;
  320.            {$IFDEF DEBUG}
  321.            writeln('PG 12, compares ',a2,' with ',aux);
  322.            {$ENDIF}
  323.            if not ( ( (aux='}') and (a2='{') ) or
  324.               ( (aux=')') and (a2='(') ) or
  325.               ( (aux=']') and (a2='[') ) )
  326.            then
  327.              do_error(ERROR_WEIRD_PARENTESIS,ERROR_WEIRD_PARENTESIS_S);
  328.            pop(2); { we kill the other parenthesis }
  329.            if (p2<>0) and (s2[p2].tipo <> 'P')
  330.            then begin { it's not empty, there is an operation }
  331.              pop(2);   {QUITAMOS LA OPERACION Y LA PASAMOS AL 1,}
  332.              push(1);  {NO IMPORTA SI ERA UNARIA O BINARIA}
  333.              if (p2<>0) and  (s2[p2].tipo = 'O') then begin
  334.                pop(2);  {AHORA PUEDE QUEDAR UNA BINARIA SOLAMENTE }
  335.                push(1); {COMO : COS(x) "* SIN (" X)}
  336.              end;
  337.            end;
  338.          end;
  339.        end;
  340.   'O','U': push(2);
  341.   'N','V': begin
  342.          if s2[p2].tipo='O' then begin
  343.            push(1);
  344.            pop(2);
  345.            push(1);
  346.          end else if s2[p2].tipo='U' then begin { ++ }
  347.            push(1);
  348.            pop(2);
  349.            push(1)
  350.          end else
  351.            push(1)
  352.        end;
  353.   'X': begin
  354.        end;
  355.   end;
  356. end;
  357.  
  358.  
  359. procedure convierte_expresion_a_polaca;
  360. var
  361.   cont   : integer; { counter to see where we are inside the expression }
  362.   letra  : char;
  363.   aux    : string;
  364. begin
  365.   cont:=1;
  366.   repeat
  367.     get_next_arg(cont); { from here 'till hitting an space }
  368.     interpreta_arg;
  369.     hace_la_operacion;
  370.   until (cont >= length(AuxString));
  371.   { fix unary operations left floating around }
  372.   while (p2<>0) and (s2[p2].tipo='U') do begin
  373.     pop(2);
  374.     push(1);
  375.   end;
  376.   if (p2<>0) and (rpn.error=0) then begin { we have an extra operation !! }
  377.     do_error(ERROR_EXTRA_SYMBOL,ERROR_EXTRA_SYMBOL_S);
  378.     rpn.message := rpn.message + s2[p2].operacion;
  379.   end;
  380.   if (rpn.p1=0) and (rpn.error=0) then { there are NO operations!! }
  381.     do_error(ERROR_NO_OPERATION,ERROR_NO_OPERATION_S);
  382. end;
  383.  
  384.  
  385. Procedure Separa_expresion;
  386. var
  387.   aux        : string;
  388.   letra      : char;
  389.   tipo,
  390.   tipo_antes : char;    { Letters, Numbers(w/point) and Operations }
  391.   I          : integer;
  392. begin
  393.   {$IFDEF DEBUG}
  394.   writeln('Original Expression = ',rpn.fun_string);
  395.   {$ENDIF}
  396.   aux:='';
  397.   AuxString := ' ' + rpn.fun_string;
  398.   tipo_antes := 'X';
  399.   for i:=1 to length(AuxString) do begin
  400.     letra:=UpCase(AuxString[i]);
  401.     if letra in numeros then
  402.       tipo := 'A'
  403.     else if letra in operaciones_simples then
  404.       tipo := 'B'
  405.     else if letra in operaciones then
  406.       tipo := 'C'
  407.     else if letra in variables then
  408.       tipo := 'D'
  409.     else if letra in parentesis then begin
  410.       tipo := 'E';
  411.       aux := aux+' ';
  412.     end
  413.     else
  414.       tipo := 'X';
  415.     if tipo<>tipo_antes then
  416.       aux:=aux+' ';
  417.     aux:=aux+letra;
  418.     tipo_antes:=tipo;
  419.   end; { for all the expression }
  420.  
  421.   AuxString:=aux;
  422.   repeat
  423.     if AuxString[length(AuxString)]=' ' then
  424.       AuxString:=copy(AuxString,1,length(AuxString)-1);
  425.   until (AuxString[length(AuxString)]<>' ') ;
  426.   while pos('  ',AuxString)>0 do
  427.     Delete(AuxString,Pos('  ',AuxString),1);
  428.   {$IFDEF DEBUG}
  429.   writeln('New expression = ',AuxString);
  430.   writeln;
  431.   repeat until keypressed;
  432.   {$ENDIF}
  433. end;
  434.  
  435.  
  436. procedure verifica_expresion_I;
  437. var
  438.   i,L            : integer;
  439.   puros_espacios : boolean;
  440.   a              : char;
  441. begin
  442.   puros_espacios:=true;
  443.   L:=length(AuxString);
  444.   if L>0 then begin
  445.  
  446.     { checks if it is only spaces}
  447.     for i:=1 to length(AuxString) do
  448.       if AuxString[i]<>' ' then puros_espacios:=false;
  449.     if puros_espacios then
  450.       do_error(ERROR_NO_OPERATION,ERROR_NO_OPERATION_S);
  451.  
  452.     { now we check if all letters are understandable }
  453.     for i:=1 to length(AuxString) do begin
  454.       a:=UpCase(AuxString[i]);
  455.       if not ( (a in operaciones) or
  456.                (a in variables  ) or
  457.                (a in parentesis ) or
  458.                (a in numeros    ) or
  459.                (a = ' '         ) or
  460.                (a in operaciones_simples) ) then begin
  461.                    do_error(ERROR_UNRECOGNIZE,ERROR_UNRECOGNIZE_S);
  462.                    rpn.message := rpn.message + a;
  463.                  end;
  464.     end;
  465.   end
  466.   else
  467.     do_error(ERROR_NO_OPERATION,ERROR_NO_OPERATION_S);
  468. end;
  469.  
  470.  
  471. Procedure Crea_expresion;
  472. var
  473.   i : integer;
  474.  
  475. Function numero_correcto(x:real):string;
  476. var ss:string;
  477. begin
  478.   str(x:10:10,ss);
  479.   while (length(ss)>0) and (ss[1]=' ') do ss:=copy(ss,2,length(ss)-1);
  480.   if pos('.',ss)>0 then begin
  481.     while ss[length(ss)] in ['0','.'] do
  482.       ss := copy(ss,1,length(ss)-1);
  483.   end;
  484.   numero_correcto := ss;
  485. end;
  486.  
  487. begin
  488.   with rpn do begin
  489.     rpn_string := '';
  490.     {$IFDEF DEBUG}
  491.     writeln;
  492.     write('The expression is : ');
  493.     for i:=1 to p1 do begin
  494.       if s1[i].tipo = 'N' then
  495.         write('<',s1.[i].numero:7:2,'>==')
  496.       else
  497.         write('<',s1[i].operacion,'>==');
  498.     end;
  499.     {$ENDIF}
  500.     for i:=1 to p1 do begin
  501.       if s1[i].tipo ='N' then
  502.         rpn_string := rpn_string + numero_correcto(s1[i].numero) + ' '
  503.       else begin
  504.         if (s1[i].operacion='-') and (s1[i].tipo='U') then
  505.           rpn_string := rpn_string + CHANGE_SIGN
  506.         else
  507.           rpn_string := rpn_string + s1[i].operacion;
  508.         if i<>p1 then rpn_string := rpn_string + ' ';
  509.       end;
  510.     end; { for i := 1 to rpn.p1 do }
  511.   end; { with rpn do begin }
  512. end;
  513.  
  514.  
  515.  
  516. BEGIN
  517.   Inicializa;
  518.   Separa_expresion;
  519.   verifica_expresion_I; { Obvious mistakes }
  520.   if rpn.error=0 then begin
  521.       convierte_expresion_a_polaca; { here we also depurate_II and verify it }
  522.     if rpn.error=0 then
  523.       Crea_expresion; { fills rpn_string }
  524.   end;
  525.   {$IFDEF DEBUG}
  526.   repeat until keypressed;
  527.   {$ENDIF}
  528. end;
  529.  
  530. begin
  531. end.