Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. class InToPost // infix to postfix conversion
  2. {
  3.     private Stack theStack;
  4.     private String input;
  5.     private Queue queue;
  6.     //--------------------------------------------------------------
  7.     public InToPost(String in) // constructor
  8.     {
  9.         input = in;
  10.         int stackSize = input.length();
  11.         int queueSize = input.length();
  12.         queue = new Queue(queueSize);
  13.         theStack = new Stack(stackSize);
  14.     }
  15.     //--------------------------------------------------------------
  16.     public String doTrans() // do translation to postfix
  17.     {
  18.         for(int j=0; j<input.length(); j++)
  19.         {
  20.             char ch = input.charAt(j);
  21.             switch(ch)
  22.             {
  23.                 case '+': // it’s + or -
  24.                 case '-':
  25.                 gotOper(ch, 1); // go pop operators
  26.                 break; // (precedence 1)
  27.                 case '*': // it’s * or /
  28.                 case '/':
  29.                 gotOper(ch, 2); // go pop operators
  30.                 break; // (precedence 2)
  31.                 case '(': // it’s a left paren
  32.                 theStack.push(ch); // push it
  33.                 break;
  34.                 case ')': // it’s a right paren
  35.                 gotParen(ch); // go pop operators
  36.                 break;
  37.                 default: // must be an operand
  38.                 queue.enqueue(ch); // write it to output
  39.                 break;
  40.             } // end switch
  41.         } // end for
  42.         while( !theStack.isEmpty() ) // pop remaining opers
  43.         {
  44.             queue.enqueue(theStack.pop()); // write to output
  45.         }
  46.         return queue.getString(); // return postfix
  47.     } // end doTrans()
  48.     //--------------------------------------------------------------
  49.     public void gotOper(char opThis, int prec1)
  50.     { // got operator from input
  51.         while( !theStack.isEmpty() )
  52.         {
  53.             char opTop = theStack.pop();
  54.             if( opTop == '(' ) // if it’s a ‘(‘
  55.             {
  56.                 theStack.push(opTop); // restore ‘(‘
  57.                 break;
  58.             }
  59.             else // it’s an operator
  60.             {
  61.                 int prec2; // precedence of new op
  62.                 if(opTop=='+' || opTop=='-') // find new op prec
  63.                     prec2 = 1;
  64.                 else
  65.                     prec2 = 2;
  66.                 if(prec2 < prec1) // if prec of new op less
  67.                 { // than prec of old
  68.                     theStack.push(opTop); // save newly-popped op
  69.                     break;
  70.                 }
  71.                 else // prec of new not less
  72.                     queue.enqueue(opTop); // than prec of old
  73.             } // end else (it’s an operator)
  74.         } // end while
  75.         theStack.push(opThis); // push new operator
  76.     } // end gotOp()
  77.     //--------------------------------------------------------------
  78.     public void gotParen(char ch)
  79.     { // got right paren from input
  80.         while( !theStack.isEmpty() )
  81.         {
  82.             char chx = theStack.pop();
  83.             if( chx == '(' ) // if popped ‘(‘
  84.                 break; // we’re done
  85.             else // if popped operator
  86.                 queue.enqueue(chx); // output it
  87.         } // end while
  88.     } // end popOps()
  89.     //--------------------------------------------------------------
  90. } // end class InToPost