Write a program that translates arithmetic expressions writt

Write a program that translates arithmetic expressions written used the standard infix notation, into RPN (Reserve Polish Notation). Your program should use a Java class Stack. You can choose to implement the Stack either using an array or using a linked list. Test your program by using inputs of different lengths and with different types of nested parentheses.

Implement a Java class Queue using circular arrays. Test your implementation and make sure all the methods work. Then use your class Queue to implement Ceasar’s Cypher with a repeating key.

Solution

Algorithm infix2postfix(infix exp<b></b>ression string, postfix exp<b></b>ression string)

{

   char *i,*p;

i = first element in infix exp<b></b>ression

   p = first element in postfix exp<b></b>ression

   while i is not null

   {

      while i is a space or tab

      {

         increment i to next character in infix exp<b></b>ression;

      }

      if( i is an operand )

      {

         p = i;

         increment i to next character in infix exp<b></b>ression;

         increment p to next character in postfix exp<b></b>ression;

      }

      if( i is \'(\' )

      {

         stack_push(i);

         increment i to next character in infix exp<b></b>ression;

      }

      if( i is \')\' )

      {

         while( element at top of stack != \'(\' )

         {

            p = element at top of stack;

            increment p to next character in postfix exp<b></b>ression;

         }

         increment i to next character in infix exp<b></b>ression;

      }

      if( i is an operator )

      {

         if( stack is empty )

             stack_push(i);

         else

         {

            while priority(element at top of stack) >= priority(i)

            {

              p = element at top of stack;

               increment p to next character in postfix exp<b></b>ression;

            }

            stack_push(i);

         }

         increment i to next character in infix exp<b></b>ression;

      }

   }

   while stack is not empty

   {

      p = stack_pop()

      increment p to next character in postfix exp<b></b>ression;

   }

   p = \'\\0\';

}