Infix2Postfix

Infix to Postfix Translation with Parentheses

Algorithm for Method processOperator to Include Parentheses

if the operator stack is empty OR the current operator is '('
   Push the current operator onto the stack
else
   Peek the stack and let topOp be the top operator.
   while the stack is non-empty AND
        precedence of the current operator is less than or equal to the topOp
      Pop the stack (and discard)
      if topOp is '(' [matching ')' as current op]
         break [effectively discarding the '(']
      end if
      if topOp is not ')'
        append topOp to the postfix expression
      end if
      if stack is not empty
         Peek the stack and let topOp be the top operator
      end if
   end while
   if current op is not ')'
      Push the current operator onto the stack
   end if
end if/else
Operator:   +  -  *  /  ^  (  )
Input prec: 1  1  2  2  4 -1 -1
Stack prec: 1  1  2  2  3 -1 -1


Postfix Evaluation :


+Scan the Postfix string from left to right.
+Initialise an empty stack.

+If the scanned character is an operand, add it to the stack.

+if the scanned character is an operator, there will be at least two operands in the stack.
 we store the top most element of the stack(topStack) in a variable temp.
 Pop the stack. Now evaluate topStack(Operator)temp.
 Let the result of this operation be retVal. Pop the stack and Push retVal into the stack.

Repeat this step till all the characters are scanned.

After all characters are scanned, we will have only one element in the stack. Return topStack.