program Notace;
{Prace s celociselnymi aritmetickymi vyrazy}
{Prevody mezi notacemi,
vyhodnoceni vyrazu zapsaneho v ruznych notacich}

type Uk = ^Uzel;
     Uzel = record      {uzel stromu reprezentujiciho vyraz}
              Hodnota: integer;              {cislo v listu}
              Znak: char;        {operator ve vnitrnim uzlu}
              L, P: Uk                          {naslednici}
            end;

var X: Uk;

function Prvek(var Hodnota:integer; var Znak:char): boolean;
  {pomocna funkce pro cteni vyrazu ze vstupu po prvcich}
  {cely vyraz musi byt na vstupu zapsan na jednom radku}
  {kazde cislo musi byt na vstupu nasledovano mezerou}
  {ukonceni vyrazu: eof}
  {funkcni hodnota - zda se jeste precetl dalsi prvek}
  {Hodnota, Znak - predani preceteneho prvku}
  {pokud se cetlo cislo, bude Znak = '$' (jako priznak)}
var Z: char;
    H: integer;
begin
if eof then
  Prvek := false
else
  begin
  Prvek := true;
  repeat
    read(Z)
  until Z <> ' ';
  if (Z >= '0') and (Z <= '9') then
    begin
    Znak := '$';   {na vstupu je cislo}
    H := 0;
    repeat
      H := H*10 + ord(Z) - ord('0');
      read(Z)
    until Z = ' ';
    Hodnota := H
    end
  else
    Znak := Z
  end
end;  {function Prvek}

procedure Error;
{Pomocne chybove hlaseni pri spatne zadanem vyrazu}
begin
writeln('Chybne zadany vyraz!')
end;

function PostfixVyhodnoceni: integer;
  {vyhodnoceni aritmet. vyrazu zapsaneho v postfixu}
  {vyuziva funkci Prvek pro vstup vyrazu po castech}
const Max = 100;             {max. pocet operandu ve vyrazu}
var Zas: array[1..Max] of integer;       {pracovni zasobnik}
    V: 0..Max;                        {vrchol zasobniku Zas}
    H, H1, H2: integer;                   {hodnoty operandu}
    Z: char;                            {znamenko na vstupu}
    Pokracovat: boolean;               {pokracovani vypoctu}
begin
V := 0;
Pokracovat := Prvek(H,Z);
while Pokracovat do
  begin
  if Z = '$'then                {na vstupu je cislo H}
    begin
    V:=V+1; Zas[V]:=H;          {operand dame na zasobnik}
    Pokracovat := Prvek(H,Z)
    end
  else if V < 2 then            {chybny vyraz!}
    begin
    Error;
    Pokracovat := false
    end
  else                          {na vstupu je znamenko Z}
    begin
    H2:=Zas[V]; V:=V-1;         {pravy operand ze zasobniku}
    H1:=Zas[V];                 {levy operand ze zasobniku}
    case Z of
      '+': H := H1 + H2;
      '-': H := H1 - H2;
      '*': H := H1 * H2;
      '/': H := H1 div H2;
    end;
    Zas[V] := H;                {vysledek na zasobnik}
    Pokracovat := Prvek(H,Z)
    end;
  end;
if V > 1 then
  Error
else
  PostfixVyhodnoceni := Zas[1]
end;  {function PostfixVyhodnoceni}

function PrefixVyhodnoceni: integer;
  {vyhodnoceni aritmet. vyrazu zapsaneho v prefixu}
  {vyuziva funkci Prvek pro vstup vyrazu po castech}
const Max = 100;                {max. pocet prvku ve vyrazu}
var Zas: array[1..Max] of                {pracovni zasobnik}
           record H:integer; Z:char end;
    V: 0..Max;                        {vrchol zasobniku Zas}
    H, H1, H2: integer;                   {hodnoty operandu}
    Z: char;                            {znamenko na vstupu}
    Pokracovat: boolean;               {pokracovani vypoctu}
begin
V := 0;
Pokracovat := Prvek(H,Z);
while Pokracovat do
  begin
  if Z <> '$'then               {na vstupu je operator Z}
    begin
    V:=V+1; Zas[V].Z:=Z;        {operator dame na zasobnik}
    Pokracovat := Prvek(H,Z)
    end
  else if V = 0 then            {na vstupu je cislo H}
    begin                       {zasobnik je prazdny}
    V:=1;
    Zas[1].Z:='$'; Zas[1].H:=H; {cislo H dame na zasobnik}
    Pokracovat := Prvek(H,Z)
    end
  else if Zas[V].Z <> '$' then  {na vstupu je cislo H}
    begin                       {na vrcholu Zas je znamenko}
    V:=V+1;
    Zas[V].Z:='$'; Zas[V].H:=H; {cislo H dame na zasobnik}
    Pokracovat := Prvek(H,Z)
    end
  else if V < 2 then            {chybny vyraz!}
    begin                       {na vstupu i na Zas je cislo}
    Error;
    Pokracovat := false
    end
  else                          {na vstupu i na Zas je cislo}
    begin
    H2 := H;                    {pravy operand ze vstupu}
    H1 := Zas[V].H; V:=V-1;     {levy operand ze zasobniku}
    Z := Zas[V].Z; V:=V-1;      {operator ze zasobniku}
    case Z of
      '+': H := H1 + H2;
      '-': H := H1 - H2;
      '*': H := H1 * H2;
      '/': H := H1 div H2;
    end;    {vysledek nechame v H do dalsiho pruchodu cyklu}
    Z := '$'              {priste budeme mit spoctene cislo}
    end;
  end;
if V > 1 then
  Error
else
  PrefixVyhodnoceni := Zas[1].H
end;  {function PrefixVyhodnoceni}


function Vyraz: integer;
  {funkce vyhodnocujici artitmeticky vyraz zapsany v infixu}
  {metoda - neprima rekurze funkci Vyraz, Clen, Faktor}
  {vyuziva funkci Prvek pro vstup vyrazu po castech}
  {predpoklada, ze vyraz na vstupu je syntakticky spravny}
var V: integer;       {hodnota vyrazu}
    H: integer;       {cislo na vstupu}
    Z: char;          {znamenko na vstupu}
    Pokracovat: boolean;
    NactenoZnamenko: boolean;     {pro signal z funkce Clen}

  function Faktor: integer;
    {pomocna funkce na vyhodnoceni jednoho faktoru}
    {faktorem je ciselna hodnota nebo vyraz v zavorkach}
  var H: integer;     {cislo na vstupu}
      Z: char;        {znamenko na vstupu}
  begin
  if Prvek(H,Z) then
    if Z = '$' then   {faktorem je primo ciselna konstanta}
      Faktor := H
    else              {Z='(', faktorem je vyraz v zavorkach}
      Faktor := Vyraz
  else
    Error
  end;  {function Faktor}

  function Clen: integer;
    {pomocna funkce na vyhodnoceni jednoho clenu}
    {clenem je jeden faktor nebo soucin/podil vice faktoru}
    {nekdy nechava v Z nactene dalsi znamenko + nebo -}
    { ... o tom signal v globalnim NactenoZnamenko}
  var H: integer;           {cislo na vstupu - nevyuziva se}
      C: integer;                            {hodnota clenu}
      Pokracovat: boolean;
  begin
  NactenoZnamenko := false;
  C := Faktor;
  Pokracovat := Prvek(H,Z);
  while Pokracovat do
    if Z = '*' then             {soucin faktoru}
      begin
      C := C * Faktor;
      Pokracovat := Prvek(H,Z)
      end
    else if Z = '/' then        {podil faktoru}
      begin
      C := C div Faktor;
      Pokracovat := Prvek(H,Z)
      end
    else                        {nutne Z='+', '-' nebo ')' }
      begin
      Pokracovat := false;      {konec clenu}
      NactenoZnamenko := true   {signal pro Vyraz}
      end;
  Clen := C
  end;  {function Clen}

begin  {function Vyraz}
V := Clen;
if NactenoZnamenko then
  Pokracovat := true
else
  Pokracovat := Prvek(H,Z);
while Pokracovat do
  if Z = '+' then               {soucet clenu}
    begin
    V := V + Clen;
    if not NactenoZnamenko then
      Pokracovat := Prvek(H,Z)
    end
  else if Z = '-' then          {rozdil clenu}
    begin
    V := V - Clen;
    if not NactenoZnamenko then
      Pokracovat := Prvek(H,Z)
    end
  else                          {nutne Z=')'}
    Pokracovat := false;        {konec vyrazu}
Vyraz := V
end;  {function Vyraz}


function PostfixStrom: Uk;
  {vytvoreni binarniho stromu pro aritmeticky vyraz}
  {  zapsany v postfixove notaci}
  {vyuziva funkci Prvek pro vstup vyrazu po castech}
const Max = 100;             {max. pocet operandu ve vyrazu}
var Zas: array[1..Max] of Uk;            {pracovni zasobnik}
    V: 0..Max;                        {vrchol zasobniku Zas}
    H: integer;                 {hodnota operandu na vstupu}
    Z: char;                            {znamenko na vstupu}
    Pokracovat: boolean;               {pokracovani vypoctu}
    U: Uk;
begin
V := 0;
Pokracovat := Prvek(H,Z);
while Pokracovat do
  begin
  new(U);                       {novy uzel pro novy prvek}
  if Z = '$'then                {na vstupu je cislo H}
    begin
    U^.Hodnota := H;
    U^.L:=nil; U^.P:=nil;       {bude to list}
    V:=V+1; Zas[V]:=U;          {operand na zasobnik}
    Pokracovat := Prvek(H,Z)
    end
  else if V < 2 then            {chybny vyraz!}
    begin
    Error;
    Pokracovat := false
    end
  else                          {na vstupu je znamenko Z}
    begin
    U^.Znak := Z;
    U^.P := Zas[V]; V:=V-1;     {pravy operand ze zasobniku}
    U^.L := Zas[V];             {levy opernad ze zasobniku}
    Zas[V] := U;                {vysledek na zasobnik}
    Pokracovat := Prvek(H,Z)
    end;
  end;
if V > 1 then
  Error
else
  PostfixStrom := Zas[1]
end;  {function PostfixStrom}

function Vyhodnoceni(K: Uk): integer;
  {vyhodnoceni aritmet. vyrazu reprezentovaneho stromem}
  {K - koren stromu}
begin
with K^ do
  begin
  if L = nil then
    Vyhodnoceni := Hodnota
  else
    case Znak of
    '+': Vyhodnoceni := Vyhodnoceni(L) + Vyhodnoceni(P);
    '-': Vyhodnoceni := Vyhodnoceni(L) - Vyhodnoceni(P);
    '*': Vyhodnoceni := Vyhodnoceni(L) * Vyhodnoceni(P);
    '/': Vyhodnoceni := Vyhodnoceni(L) div Vyhodnoceni(P);
    end
  end
end;  {function Vyhodnoceni}

procedure Prefix(K: Uk);
  {pruchod binarnim stromem s korenem K metodou preorder}
  {vypsani aritmetickeho vyrazu v prefixove notaci}
begin
if K^.L = nil then        {list}
  write(K^.Hodnota,' ')
else                      {vnitrni uzel}
  begin
  write(K^.Znak);
  Prefix(K^.L);
  Prefix(K^.P);
  end
end;

procedure Postfix(K: Uk);
  {pruchod binarnim stromem s korenem K metodou postorder}
  {vypsani aritmetickeho vyrazu v postfixove notaci}
begin
if K^.L = nil then        {list}
  write(K^.Hodnota,' ')
else                      {vnitrni uzel}
  begin
  Postfix(K^.L);
  Postfix(K^.P);
  write(K^.Znak);
  end
end;

procedure Infix(K: Uk);
  {pruchod binarnim stromem s korenem K metodou inorder}
  {vypsani aritmetickeho vyrazu v infixove notaci}
begin
if K^.L = nil then        {list}
  write(K^.Hodnota)
else                      {vnitrni uzel}
  begin
  write('(');
  Infix(K^.L);
  write(K^.Znak);
  Infix(K^.P);
  write(')');
  end
end;

procedure InfixNaPostfix;
  {prevod aritmet. vyrazu zapsaneho v infixu do postfixu}
  {vyuziva funkci Prvek pro vstup vyrazu po castech}
  {vysledny postfixovy zapis vyrazu primo vypisuje}
  {nekontroluje spravnost vstupniho infixoveho zapisu}
const Max = 100;            {max. pocet operatoru ve vyrazu}
var Znam: array[0..Max] of char;         {pracovni zasobnik}
    W: 0..Max;                       {vrchol zasobniku Znam}
    H: integer;                           {hodnoty operandu}
    Z: char;                            {znamenko na vstupu}
    Pokracovat: boolean;               {pokracovani vypoctu}
begin
W := 0;
Pokracovat := Prvek(H,Z);
while Pokracovat do
  begin
  case Z of
  '$': write(H, ' ');           {na vstupu je cislo H}
  '(': begin
       W:=W+1; Znam[W]:='('     {zavorku do zasobniku}
       end;
  ')': begin                    {ze zasobniku az k zavorce}
       while (W > 0) and (Znam[W] <> '(') do
         begin
         write(Znam[W]); W:=W-1
         end;
       if W = 0 then
         Error                  {chybny vyraz!}
       else
         W:=W-1                 {zrusit zavorku}
       end;
  '*', '/':          {operatory stejne priority ven ze Znam}
       begin
       while (W > 0) and (Znam[W] in ['*','/']) do
         begin
         write(Znam[W]); W:=W-1
         end;
       W:=W+1; Znam[W]:=Z       {ulozit Z na zasobnik}
       end;
  '+', '-':  {operatory stejne a vyssi priority ven ze Znam}
       begin
       while (W > 0) and (Znam[W] in ['+','-','*','/']) do
         begin
         write(Znam[W]); W:=W-1
         end;
       W:=W+1; Znam[W]:=Z       {ulozit Z na zasobnik}
       end;
  end; {case}
  Pokracovat := Prvek(H,Z)
  end;
while (W > 0) and (Znam[W] <> '(') do
  begin
  write(Znam[W]); W:=W-1        {jeste vyprazdnit zasobnik}
  end;
writeln;
if W > 0 then
  Error                         {chybny vyraz!}
end;  {procedure InfixNaPostfix}


function InfixVyhodnoceni: integer;
  {vyhodnoceni aritmet. vyrazu zapsaneho v infixu}
  {metoda zalozena na prevodu pres postfix}
  {vyuziva funkci Prvek pro vstup vyrazu po castech}
  {nekontroluje spravnost vstupniho infixoveho zapisu}
const Max = 100;                {max. pocet prvku ve vyrazu}
var Znam: array[0..Max] of char;      {zasobnik na znamenka}
    W: 0..Max;                       {vrchol zasobniku Znam}
    Zas: array[1..Max] of integer;       {zasobnik na cisla}
    V: 0..Max;                        {vrchol zasobniku Zas}
    H: integer;                          {operand na vstupu}
    Z: char;                            {znamenko na vstupu}
    Pokracovat: boolean;               {pokracovani vypoctu}

  procedure Proved(Z: char);
  {vykonani operace spojene s operatorem Z}
  var H, H1, H2: integer;       {hodnoty operandu}
  begin
  if V < 2 then                 {chybny vyraz!}
    Error
  else                          {na vstupu je znamenko Z}
    begin
    H2:=Zas[V]; V:=V-1;         {pravy operand ze zasobniku}
    H1:=Zas[V];                 {levy operand ze zasobniku}
    case Z of
      '+': H := H1 + H2;
      '-': H := H1 - H2;
      '*': H := H1 * H2;
      '/': H := H1 div H2;
    end;
    Zas[V] := H;                {vysledek na zasobnik}
    end;
  end;  {procedure Proved}

begin
W := 0;
V := 0;
Pokracovat := Prvek(H,Z);
while Pokracovat do
  begin
  case Z of
  '$': begin                    {na vstupu je cislo H}
       V:=V+1; Zas[V]:=H;       {operand dame na zasobnik}
       end;
  '(': begin                    {zavorku do zasobniku}
       W:=W+1; Znam[W]:='('
       end;
  ')': begin                    {ze zasobniku az k zavorce}
       while (W > 0) and (Znam[W] <> '(') do
         begin
         Proved(Znam[W]); W:=W-1
         end;
       if W = 0 then
         Error                  {chybny vyraz!}
       else
         W:=W-1                 {zrusit zavorku}
       end;
  '*', '/':          {operatory stejne priority ven ze Znam}
       begin
       while (W > 0) and (Znam[W] in ['*','/']) do
         begin
         Proved(Znam[W]); W:=W-1
         end;
       W:=W+1; Znam[W]:=Z       {ulozit Z na zasobnik}
       end;
  '+', '-':  {operatory stejne a vyssi priority ven ze Znam}
       begin
       while (W > 0) and (Znam[W] in ['+','-','*','/']) do
         begin
         Proved(Znam[W]); W:=W-1
         end;
       W:=W+1; Znam[W]:=Z       {ulozit Z na zasobnik}
       end;
  end; {case}
  Pokracovat := Prvek(H,Z)
  end;
while (W > 0) and (Znam[W] <> '(') do
  begin
  Proved(Znam[W]); W:=W-1       {jeste vyprazdnit zasobnik}
  end;
writeln;
if W > 0 then
  Error;                        {chybny vyraz!}
if V > 1 then
  Error
else
  InfixVyhodnoceni := Zas[1]
end;  {function InfixVyhodnoceni}


begin {testovaci hlavni program}

writeln('POZOR! Pri zapisu vyrazu se ridte temito pravidly:');
writeln('- vsechny konstanty ve vyrazu jsou celociselne');
writeln('- cely vyraz musi byt na vstupu zapsan na jednom radku');
writeln('- kazde cislo musi byt na vstupu nasledovano mezerou');
writeln('- vyraz musi byt ukoncn pomoci znaku eof (Ctrl-Z)');


{NUTNO ZKOUSET VOLAT RUZNE PROCEDURY A FUNKCE A JEJICH KOMBINACE}

writeln('Zadejte vyraz v postfixove notaci:');
X := PostfixStrom;
writeln;
writeln('Vypis ze stromu v postfixu:');
Postfix(X);
writeln;
writeln('Vypis ze stromu v prefixu:');
Prefix(X);
writeln;
writeln('Vypis ze stromu v infixu:');
Infix(X);
writeln;
writeln('Vyhodnoceni vyrazu ze stromu:  ', Vyhodnoceni(X));

{
writeln('Zadejte vyraz v postfixove notaci');
writeln('Vyhodnoceni z postfixu: ', PostfixVyhodnoceni);
}

{
writeln('Zadejte vyraz v prefixove notaci');
writeln('Vyhodnoceni z prefixu:  ', PrefixVyhodnoceni);
}

{
writeln('Zadejte vyraz v infixove notaci');
writeln('Prevod zapisu vyrazu z infixu do postfixu:');
InfixNaPostfix;
}

{
writeln('Zadejte vyraz v infixove notaci');
writeln('Vyhodnoceni z infixu prevodem pres postfix:  ', InfixVyhodnoceni);
}

{
writeln('Zadejte vyraz v infixove notaci');
writeln('Vyhodnoceni z infixu soustavou rekurz. funkci:  ', Vyraz);
}

end.