Thread: Infix to prefix conversion

Greetings to all,

I am trying to implement task from subject via stack. It does not work for a reason unknown to me, so if anyone could space a moment and take a look.

Program should convert infix to prefix, meaning:

A|B&(C^E|D) --> |A&B|^CED

&=AND, |=OR, ^=XOR, -=NOT

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 20

typedef struct _kucica
{
        char varijabla;
        struct _kucica *next;
} kucica;

typedef kucica *stog;

int EMPTY (stog s)
{
    if (s == NULL)
    return 1;
    else
    return 0;
}

void PUSH (char x, stog *s)
{
     kucica *pom;
     pom = malloc (sizeof (kucica));
     pom->varijabla = x;
     pom->next = *s;
     *s = pom;
}

void POP (stog *s)
{
     kucica *pom;
     if (EMPTY (*s))
     printf ("Stog je prazan.\n");
     else
     {
         pom = *s;
         *s = (*s)->next;
         free (pom);
     }
}

char TOP (stog s)
{
     if (EMPTY (s))
     printf ("Stog je prazan.\n");
     else
     return (s->varijabla);
}

int PRIORITET (char x)
{
    if (x == '&')
    return 4;
    if (x == '^')
    return 3;
    if (x == '|')
    return 2;
    if (x == '-')
    return 1;
}

int SLOVO (char x)
{
    if ((x == '&') || (x == '|') || (x == '^') || (x == '-'))
    return 0;
    else
    return 1;
}

void OBRNI_STRING (char string [], int duljina)
{
      char obrnuti [duljina+1];
      int i, j=0;
      for (i=duljina-1; i>=0; i--)
      {
          obrnuti [j] = string [i];
          j++;
      }
      obrnuti [j] = '\0';
      for (i=0; obrnuti [i] != '\0'; i++)
      string [i] = obrnuti [i];
}

void prefix (char i_string [])
{
     char o_string [MAXLEN];
     stog *s;
     int i, j=0, duljina_i, duljina_o;
     duljina_i = strlen (i_string);
     OBRNI_STRING (i_string, duljina_i);
     puts (i_string);
     for (i=0; i_string [i] != '\0'; i++)
     {
         printf ("&#37;d\n", i);
         if (i_string [i] == ')')
         {
               PUSH (i_string [i], s);
         }
         if (SLOVO (i_string [i]) == 1)
         {
                   o_string [j] = i_string [i];
                   j++;
         }
         if (SLOVO (i_string [i]) == 0)
         {
                   if ((EMPTY (*s) == 0) && (PRIORITET (TOP (*s)) >= PRIORITET (i_string [i])))
                   {
                              o_string [j] = TOP (*s);
                              j++;
                              POP (s);
                   }
                   PUSH (i_string [i], s);
         }
         if (i_string [i] == '(')
         {
                      while (TOP (*s) != ')')
                      {
                            o_string [j] = TOP (*s);
                            j++;
                            POP (s);
                      }
                      POP (s);
         }
     }
     if (EMPTY (*s) == 0)
     {
               while (EMPTY (*s) != 1)
               {
                     o_string [j] = TOP (*s);
                     j++;
                     POP (s);
               }
     }
     o_string [j] = '\0';
     duljina_o = strlen (o_string);
     OBRNI_STRING (o_string, duljina_o);
     for (i=0; o_string [i] != '\0'; i++)
     i_string [i] = o_string [i];
}

int main (void)
{
    char string [MAXLEN];
    printf ("Unesite string u infiksu:\n");
    gets (string);
    prefix (string);
    printf ("String u prefiksu je:\n");
    puts (string);
    return 0;
}

As far as I could tell, program crashes in PUSH function in the last line, *s = pom;. Why, well, if I knew, I wouldn't post here.

TIA!