Infix to prefix conversion

This is a discussion on Infix to prefix conversion within the C Programming forums, part of the General Programming Boards category; Greetings to all, I am trying to implement task from subject via stack. It does not work for a reason ...

  1. #1
    Registered User bbanelli's Avatar
    Join Date
    Nov 2007
    Location
    Croatia, Zagreb
    Posts
    5

    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!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    A little ugly perhaps, but couldn't SLOVO and PRIORITET be the same if you change PRIORITET to return 0 for everything else?

    Code:
         if (EMPTY (*s) == 0)
         {
                   while (EMPTY (*s) != 1)
                   {
                         o_string [j] = TOP (*s);
                         j++;
                         POP (s);
                   }
         }
    The outer if does the same job as the while-condition - so why do you need both?

    The reason your code doesn't work is that you don't initialize your stack - so it is pointing at some randomg thing.

    Also, using all uppercase names, such EMPTY is usually indicating that EMPTY is a macro rather than a function, you shouldn't use all uppercase names for functions.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 03:39 PM
  2. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM
  3. Header File Question(s)
    By AQWst in forum C++ Programming
    Replies: 10
    Last Post: 12-23-2004, 11:31 PM
  4. Creation of Menu problem
    By AQWst in forum C Programming
    Replies: 8
    Last Post: 11-24-2004, 09:44 PM
  5. infix to prefix.....damn my eyes are fried
    By misplaced in forum C++ Programming
    Replies: 10
    Last Post: 10-04-2004, 02:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21