Data Structure (2130702)

• When value to TOP pointer variable is greater than or equal to size of stack (Stack is Full) at that time Insertion operation cannot be performed on Stack.
• When value to TOP pointer variable is less than or equal to zero (Stack is Empty) at that time Deletion operation cannot be performed on Stack.

• In given strings, portions after and before character C are exactly in reverse order. The nature of Stack is LIFO (Last In First Out) so we can use Stack to recognize given strings.

Algorithm : RECOGNIZE

• Given an input string named STRING on the alphabet {a, b, c} which contains a blank in its rightmost character position.
• Function NEXTCHAR returns the next symbol in STRING.
• This algorithm determines whether the contents of STRING belong to the above language.
• The vector S represents the stack and TOP is a pointer to the top element of the stack.

1. [Initialize stack by placing a letter ‘c’ on the top]
   TOP<--1
   S[TOP]<--‘c’
   
2. [Get and stack symbols until either ‘c’ or blank is encountered]
   NEXT<--NEXTCHAR(STRING)
   Repeat while NEXT != ‘c’
   If NEXT=‘ ‘
   Then Write (‘Invalid String’)
       EXIT
   Else Call PUSH (S, TOP, NEXT)
       NEXT<--NEXTCHAR (STRING)
   
3. [Scan characters following ‘c’; Compare them to the characters on stack]
   Repeat While S[TOP] != ‘c’
     NEXT<--NEXTCHAR (STRING)
     X<--POP (S, TOP)
     If NEXT != X
     Then Write (‘INVALID STRING’)
        Exit
   
4. [Next symbol must be blank]
   NEXT <-- NEXTCHAR (STRING)
   If NEXT != ‘ ‘
   Then Write (‘VALID STRING’)
   Else Write (‘INVALID STRING’)
   
5. [Finished]
   EXIT