Infix,prefix and postfix expressions in data structures

INFIX, PREFIX, AND POSTFIX EXPRESSIONS and THEIR COMPILATION:

We are primarily concerned with the mechanical evaluation or computation of infix expressions. We shall find it to be more efficient to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value.

The translation of infix expressions to Polish notation is examined in detail and represents one of the classical applications of a stack.

Consider the sum of A and B. We think of applying the operator “+” to the operands A and B and write the sum as A+B. This particular representation is called infix. There are two alternate notations for expressing the sum of A and B using the symbols A,B, and +.

These are


               + A B     prefix (or Polish)
               A B +     postfix (or Suffix or Reverse Polish)

The prefixes “pre-“, “post-“, and “in-” refer to the relative position of the operator with respect to the two operands. In prefix notation the operator precedes the two operands, in postfix notation the operator follows the two operands, and in infix notation the operator is between the two operands.

Let us consider, initially, the mechanical evaluation of un-parenthesized arithmetic expressions consisting of single-letter variables, nonnegative integers and the four operators +,-,* and /. The precedence of the operators * and / is considered to be equal and of higher value than that of + and -. An example of such an un-parenthesized arithmetic expression is

a + b * c + d * e

For the evaluation of this expression, we must scan from left to right repeatedly.


postfix:
     step 1:   a + bc*  + de*
     step 2:   abc*+ + de*
     step 3:   abc*+de*+ (result)

prefix:
     step 1:   a + *bc  + *de
     step 2:   +a*bc + *de
     step 3:   ++a*bc*de     (result)

A fully parenthesized infix expression can be directly translated to suffix notation by beginning with the conversion of the inner parenthesized sub-expression and then proceeding towards the outside of the expression. In the case of the fully parenthesized expression (a + ((b * c) * d)) the innermost parenthesized sub-expression is (b*c) and is converted to bc* i.e. (a + (bc* * d)) therefore , the sub-expression bc* * d is converted to the suffix equivalent of bc*d*, so the expression is (a + bc*d*) and finally the term a + bc*d* is converted to the final suffix form of abc*d*+

Example:

A trace of the stack contents and the Polish string (reverse polish) for the infix expression


    ((a + b ^ c ^ d) * (e + f / d))

Consider the following precedence:

symbol input precedence stack precedence
+,- 1 2
*,/ 3 4
^ 6 5
variables 7 8
( 9 0
) 0


Translation of infix string to Reverse-Polish expression 

Character scanned Postfix string opstk
( (
( ((
a a ((
+ a ((+
b ab ((+
^ ab ((+^
c abc ((+^
^ abc ((+^^
d abcd ((+^^
) abcd^^+ (
* abcd^^+ (*
( abcd^^+ (*(
e abcd^^+e (*(
+ abcd^^+e (*(+
f abcd^^+ef (*(+
/ abcd^^+ef (*(+/
d abcd^^+efd (*(+/
) abcd^^+efd/+ (*
) abcd^^+efd/+*


The postfix string is : abcd^^+efd/+*

Convert the following infix expressions to other expressions

  1. A + B * C
  2. A + B * C ^ D / E * F + G – H
  3. ((A – ( B + C)) ^ E + F)
  4. ((A + B) * C – ( D – E )) ^ ( F + G)
  5. A – B / (C * D ^ E)
  6. ((A – (B + C)) * D) ^ ( E + F)

Algorithm For Evaluation Of A Postfix Expression:


1. opndstk = the empty stack;
2. [ scan the input string reading one element at a time into symb]
     while (not end of input)
       begin
          symb = next input character;
          if (symb  is an operand) then
               push(opndstk, symb)
          else             [symb is an operator]
               begin
                    opnd2 = pop(opndstk)
                    opnd1 = pop(opndstk)
                    value = result of applying symb to opnd1 and opnd2
                    push(opndstk, value)
               end
          endif
     end while
3.   return (pop(opndstk))

for example, to evaluate the following postfix expression
6 2 3 + – 3 8 2 / + * 2 ^ 3 +

symb opnd1 opnd2 value opndstk
6       6
2       6,2
3       6,2,3
+ 2 3 5 6,5
6 5 1 1
3 6 5 1 1,3
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
^ 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52

Conversion of an infix expression to postfix expression:


1. opstk = the empty stack
2. while (not end of input)
    begin
          symb = next input character
          if(symb is an operand) then
               add symb to the postfix string
          else
               begin
                    while( not empty(opstr) and pred(stacktop(opstk),symb))
                       begin
                          topsymb = pop(opstk);
  add topsymb to the postfix string;
                       end while
                    push(opstk, symb);
               end
          endif
    end while
3. [ output any remaining operators ]
     while ( not empty(opstk))
       begin
             topsymb = pop(opstk);
             add topsymb to the postfix string;
       end while
4. return

In the above algorithm, precedence plays such an important role in transforming infix to postfix, let us assume the existence of a function pred(op1,op2), where op1 and op2 are characters representing operators. This function returns TRUE if op1 has precedence over op2 when op1 appears to the left of op2 in an infix expression without parenthesis, pred(op1,op2) returns FALSE otherwise. for example, pred(‘*’,’+’) and Pred(‘+’,’+’) are TRUE, whereas pred(‘+’,’*’) is FALSE.

Conversion of an infix expression to postfix expression( using with parenthesis):


1. opstk = the empty stack
2. while (not end of input)
    begin
          symb = next input character
          if(symb is an operand) then
               add symb to the postfix string
          else
               begin
                    while( not empty(opstr) and pred(stacktop(opstk),symb))
                       begin
   topsymb = pop(opstk);
                          add topsymb to the postfix string;
                       end while
                    if(empty(opstk) or symb not = ')') then
                         push(opstk, symb);
                    else
                         topsymb= pop(opstk)
                    endif
               end
          endif
    end while
3. [ output any remaining operators ]
     while ( not empty(opstk))
       begin
             topsymb = pop(opstk);
             add topsymb to the postfix string;
       end while
4. return

STACK APPLICATION BY USING LINKED LISTS IN C++:

If T is the name of a type, then the expression, new T, creates a new object of type T and returns a pointer to the newly created object. If T is a class with a constructor with no parameters, then the object created is also automatically initialized. If T is a class with a constructor with n parameters, then the expression, new T(p1,p2,…,pn.), creates an object of type T, initializes it using the constructor with parameters p1 through pn, and returns a pointer to it. If p points to an object created via use of the ‘new’ operator, then the statement ‘delete p;’ de-allocates the object to which p was pointing. If the type has a destructor, the destructor in invoked prior to the deallocation.

If a particular operation is desired on the list, it must be included in the public interface of the list class.

For example, the following might be the class definition for a linked list of integers, with the following operations:

  1. Initialize a list to the empty list. This is a constructor, automatically invoked when a list is defined or created.
  2. Free the nodes of a list. This is a destructor, automatically invoked when a list is freed or the block in which it is declared is exited.
  3. Determine whether a list is empty.
  4. Add a node with a given value into the list following the first node with another given value.
  5. Add a node with a given value to the front of the list. This is the push operator.
  6. Delete the first node with a given value from the list.
  7. Delete the first node from the list. This is the pop operator.

The class definition follows:


class List
    {
      protected:
          struct node
               {
                    int info;
                    struct node *next;
               };
          typedef struct node *NODEPTR;
          NODEPTR listptv;    // the pointer to the first node of the list
     public:
          List();
          ~List();
          int emptylist();
          void insertafter(int oldvalue, int newvalue);
          void push(int newvalue);
          void delete(int oldvalue);
          int pop();
     };

List is a constructor that initializes a newly created list to the empty list.


          List::List()
               {
                    listprt = 0;
               }

~List is the destructor that traverses the nodes of a list, freeing them one by one.


          List::~List()
               {
                    NODEPTR p,q;
                    if(emptylist())
                         return 0;

        for (p=listptr, q = p->next; p!=0; p=q, q=p->next)
                         delete p;
               }

emptylist determines if a list is empty.


          int List::emptylist()
               {
                    return (listptr == 0);
               }

insertafter(oldvalue, newvalue) searches for the first occurrence of the value oldvalue in the list and inserts a new node with value newvalue following the node containing oldvalue.


          List::insertafter(int oldvalue, int newvalue)
               {
                    NODEPTR p,q;
                    for(p=listptr; p!=0 && p->info != oldvalue; p=p->next);
                    if(p==0)
                         error("ERROR: value sought is not on the list.");
                    q = new node;
                    q->info = newvalue;
                    q->next = p->next;
                    p->next = q;
               }


push(newvalue) adds a new node with a given value to the front of the list.


          List::push(int newvalue)
               {
                    NODEPTR p;
                    p = new node;
                    p->info = newvalue;
                    p->next = listptr;
                    listptr = p;
               }

delete(oldvalue) deletes the first node containing the value oldvalue from the list.


          List:: delete(int oldvalue)
               {
                  NODEPTR  p,q;
                  for(q=0,p=listptr; p!=0 && p->info!=oldvalue;q=p,p=p->next);
                  if(p==0)
                     error("ERROR: value sought is not on the list");
                  if(q==0)
                    listptr = p->next;
                  else
                    q->next = p->next;
                  delete p;
               }

Finally, pop deletes the first node on the list and returns its contents.


          int List::pop()
               {
                  NODEPTR p;
                  int x;
                  if(emptylist())
                         error("ERROR: the list is empty");
                  p = listptr;
                  listptr = p->next;
                  x = p->info;

      delete p;
                  return x;
               }

Note that the List class does not permit the user to manipulate the nodes of the list; everything must be done via a method of List on the entire list.

Recursion:

Recursion is a fundamental concept in mathematics and computer science. The simple definition is that a recursive program is one that calls itself (and a recursive function is one that is defined in terms of itself). Yet a recursive program can’t call itself always, or it would never stop; another essential ingredient is that there must be a termination condition when the program can cease to call itself.

Recursive definitions of functions are quite common in mathematics – the simplest type, involving integer arguments are called recurrence relations.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s