Data Structure (2130702)

Precedence Table

Algorithm : REVPOL

• Given an input string INFIX containing an infix expression which has been padded on the right with ‘)’ and whose symbol have precedence value given by above table.
• A vector S used as a stack and a NEXTCHAR which when invoked returns the next character of its argument.
• This algorithm converts INFIX into reverse polish and places the result in the string POLISH.
• The integer variable TOP denotes the top of the stack. Algorithm PUSH and POP are used for stack manipulation.
• The integer variable RANK accumulates the rank of expression. Finally the string variable TEMP is used for temporary storage purpose.

1. [Initialize stack]
     TOP <-- 1
     S[TOP] <-- ‘(‘
2. [Initialize output string and rank count]
     POLISH <-- ‘ ‘
     RANK <-- 0
3. [Get first input symbol]
     NEXT<--NEXTCHAR(INFIX)
4. [Translate the infix expression]
     Repeat thru step 7 while NEXT != ‘ ‘
5. [Remove symbols with greater precedence from stack]
     IF TOP < 1
     Then write (‘INVALID’)
        EXIT
     Repeat while G (S[TOP]) > F(NEXT)
      TEMP <-- POP (S, TOP)
      POLISH <-- POLISH O TEMP
      RANK <-- RANK + R(TEMP)
      IF RANK < 1
      Then write (‘INVALID’)
         EXIT
6. [Are there matching parentheses]
     IF G(S[TOP]) != F(NEXT)
       Then call PUSH (S,TOP, NEXT)
     Else POP (S,TOP)
7. [Get next symbol]
     NEXT <-- NEXTCHAR(INFIX)
8. [Is the expression valid]
     IF TOP != 0 OR RANK != 1
       Then write (‘INVALID ‘)
     Else write (‘VALID ’)