Infix to Postfix Conversion and Execution

Infix to Postfix Conversion and Execution

In every compiler there is a calculation statement (+, -, *, /). In depth this calculation is done by two steps. Firstly a given infix expression is converted to postfix expression. Secondly this expression is used to calculate real value.

Turbo Pascal Source Code

{
  This program converts an infix expression to postfix. Then real calculation is done.
}
uses crt;
var
  okunan:string[50];
  ifade,yeni:array[1..30] of string;
  temp,uzunluk,i,j,i4,top,code,n,ptr,sayi1,sayi2,carp,ii:integer;
  token:string;
  sayilar:set of 0..9;
  a1,stack_elemani,tut:char;
  stack:array[1..10] of char;
  sayi_stack:array[1..20] of integer;
{
  PUSH process
}
Procedure push(oprtr:char);
begin
  ptr:=ptr+1;
  stack[ptr]:=oprtr;
end;
{
  POP process
}
Function pop:char;
begin
  if ptr=0  then
   begin
   pop:=' ';
   end
  else
    begin
        pop:=stack[ptr];
        ptr:=ptr-1;
    end;
end;

BEGIN
  clrscr;
  write('Input the infix expression: ');
  read(okunan);
  uzunluk:=length(okunan);
  okunan[0]:=chr(uzunluk);
  j:=0;i:=1;
  while(i<=uzunluk) do
   begin
     a1:=okunan[i];
     val(a1,i4,code);
     top:=0;
     if code=0 then
      begin
        while (code=0) and (i<=uzunluk)do
          begin
            top:=top*10+i4;
            i:=i+1;
            a1:=okunan[i];
            val(a1,i4,code);
          end;
        j:=j+1;
        str(top,ifade[j]);
      end;
     if i<=uzunluk then
      begin
        j:=j+1;
        ifade[j]:=okunan[i];
        i:=i+1;
      end;
   end;
   n:=j;
{
Conversion to Postfix
}
  ptr:=0;
  i:=1; j:=0;
  while(i<=(uzunluk)) do
   begin
     token:=ifade[i];
     val(token,i4,code);
     if code = 0 then
      begin
        j:=j+1;
        yeni[j]:=token;
      end
     else
      begin
        tut:=token[1];
        case tut of
           '(','^': push(tut);
           ')': begin
                  stack_elemani:=pop;
                  while stack_elemani <> '(' do
                    begin
                      j:=j+1;
                      yeni[j]:=stack_elemani;
                      stack_elemani:=pop;
                    end;
                end;
           '+','-': begin
                      stack_elemani:=pop;
                      while (stack_elemani <> '(') and
                             (stack_elemani <> ' ') do
                        begin
                          j:=j+1;
                          yeni[j]:=stack_elemani;
                          stack_elemani:=pop;
                        end;
                        if stack_elemani ='(' then
                           push('(');
                        push(tut);
                    end;
           '*','/','^':begin
                         stack_elemani:=pop;
                         while(stack_elemani='*') or (stack_elemani='/')
                               or (stack_elemani='^')  do
                           begin
                             j:=j+1;
                             yeni[j]:=stack_elemani;
                             stack_elemani:=pop;
                           end;
                         if stack_elemani <> ' ' then
                           push(stack_elemani);
                         push(tut);
                       end;
           end;{ case }
     end;{ else }
    i:=i+1;
   end; { while }
  stack_elemani:=pop;
  while(stack_elemani <> ' ') do
    begin
       j:=j+1;
       yeni[j]:=stack_elemani;
       stack_elemani:=pop;
    end;

  writeln; write('Postfix Notation:');
  n:=j;
  for i:=1 to n do
     write(yeni[i],' ');
  readln;
{
Calculating the result using Postfix
}
  i:=1;
  ptr:=0;
  while(i<=n) do
    begin
      token:=yeni[i];
      val(token,i4,code);
      while(code=0) do
        begin
          ptr:=ptr+1;
          sayi_stack[ptr]:=i4;
          i:=i+1;
          token:=yeni[i];
          val(token,i4,code);
        end;
      tut:=token[1];
      sayi1:=sayi_stack[ptr];
      ptr:=ptr-1;
      sayi2:=sayi_stack[ptr];
      case tut of
        '+':sayi_stack[ptr]:=sayi1+sayi2;

        '-': sayi_stack[ptr]:=sayi2-sayi1;

        '*': sayi_stack[ptr]:=sayi2*sayi1;

        '/': sayi_stack[ptr]:=sayi2 div sayi1;

        '^':begin
              carp:=1;
              for ii:=1 to sayi1 do
                carp:=carp*sayi2;
              sayi_stack[ptr]:=carp;
            end;
        end; { case }
      i:=i+1;
    end;
  write('Result: ');writeln(sayi_stack[1]);
  repeat until keypressed;
END.

Sample Execution

'Input the infix expression: 10+(2+4)/2

Postfix Notation: 10 2 4 + 2 / +

Result: 13

'Input the infix expression: (4*7)-8/2

Postfix Notation: 4 7 * 8 2 / -

Result: 24