type PtreeNode = ^TtreeNode;
     TtreeNode = record
       value:char;
       parent,left,right:PtreeNode;
     end;


var root:TtreeNode;
    curNode:PtreeNode;

    variables:array[0..255] of boolean;
    variableUsed:array[0..255] of boolean;
    numVariables:integer;


procedure initNode(node:PtreeNode);
begin;
  node^.Left:=nil;
  node^.Right:=nil;
  node^.Parent:=nil;
  node^.value:='-';
end;


function newLeftNode(node:PtreeNode):PtreeNode;
begin;
  new(node^.Left);
  initNode(node^.Left);
  node^.Left^.parent:=node;
  newLeftNode:=node^.Left;
end;


function newRightNode(node:PtreeNode):PtreeNode;
begin;
  new(node^.Right);
  initNode(node^.Right);
  node^.Right^.parent:=node;
  newRightNode:=node^.Right;
end;

procedure getExpression;
var s:string;
    pos:integer;
begin;
  numVariables:=0;
  fillchar(variables,sizeof(variables),false);
  fillchar(variableUsed,sizeof(variableused),false);

  curNode:=addr(root);
  write('Enter the expression:');
  readln(s);

  for pos:=1 to length(s) do begin;

    case s[pos] of
      '(':begin;
        curNode:=newLeftNode(curNode);
      end;
      '*','+','@':begin;
        curNode^.value:=s[pos];
        curNode:=newRightNode(curNode);
      end;
      ')':begin;
        curNode:=curNode^.parent;
      end;
      else begin;
       curNode^.value:=upcase(s[pos]);

       if not variableUsed[ord(curNode^.value)] then begin;
         inc(numVariables);
         variableUsed[ord(curNode^.value)]:=true;
       end;

       curNode:=curNode^.parent;
      end;
    end; { case }
  end; { for loop }
end; { getExpression }


procedure rPrintTraverseTree(node:PtreeNode);
begin;
 if node = NIL then exit;

 write('(');
 rPrintTraverseTree(node^.left);

 write(node^.value);

 rPrintTraverseTree(node^.right);
 write(')');
end;


function rEvalTraverseTree(node:PtreeNode):boolean;
var val1, val2:boolean;
begin;

 if node^.Left = nil then begin;
  rEvalTraverseTree:=variables[ord(node^.value)];
  exit;
 end;

 val1:=rEvalTraverseTree(node^.Left);
 val2:=rEvalTraverseTree(node^.Right);

 case node^.value of
  '*':rEvalTraverseTree:=val1 AND val2;
  '+':rEvalTraverseTree:=val1 OR val2;
  '@':rEvalTraverseTree:=NOT(val1 AND val2);
 end;

end;

function power2(numTimes:integer):word;
begin;
 if numTimes = 0 then begin;
  power2:=1;
  exit;
 end;
 power2:=2*power2(numTimes-1);
end;


function getNextVariable(cur:byte):byte;
var c:byte;
begin;
 c:=cur;

 repeat
  inc(c);
 until variableUsed[c];

 getNextVariable:=c;
end;

procedure buildTruthTable;
var cnt,varNum,curVar:word;
begin;

 write('|');
 curVar:=255;
 for varNum:=1 to numVariables do begin;
  curVar:=getNextVariable(curVar);
  write(' ',chr(curVar),' |');
 end;
 writeln(' X |');

 for cnt:=0 to power2(numVariables)-1 do begin;

  if ((cnt+1) mod 24) = 0 then begin;
   write('More -- press enter:');
   readln;
  end;

  write('|');
  curVar:=255;
  for varNum:=numVariables-1 downto 0 do begin; { find canonical values }
   curVar:=getNextVariable(curVar);
   variables[curVar]:=((cnt AND power2(varNum)) <> 0);
   if variables[curVar] then write(' 1 |') else write(' 0 |');
  end;
  if rEvalTraverseTree(@root) then writeln(' 1 |') else writeln(' 0 |');


 end;

end;

begin;
 initNode(addr(root));
 getExpression;
 writeln;
 buildTruthTable;
end.