Infix to Postfix Conversion using Stack in Java

In this program, you'll learn to solve the Infix to Postfix Conversion using Stack. There is an algorithm to convert an infix expression into a postfix expression. It uses a stack; but in this case, the stack is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression :

The Postfix(Postorder) form of the above expression is "23*45/-".

Example : 

  • infix (1+2)*(3+4)
    • with parentheses: ((1+2)*(3+4))
    • in postfix: 12+34+*
    • in prefix: *+12+34
  • infix 1^2*3-4+5/6/(7+8)
    • paren.: ((((1^2)*3)-4)+((5/6)/(7+8)))
    • in postfix: 12^3*4-56/78+/+
    • in prefix: +-*^1234//56+78


Algorithm

  1. Scan the Infix string from left to right.
  2. Initialise an empty stack.
  3. If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character tostack.
  4. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack(topStack). If topStack has higher precedence over the scanned character Popthe stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
  5. (After all characters are scanned, we have to add any character that the stackmay have to the Postfix string.) If stack is not empty add topStack to Postfix stringand Pop the stack. Repeat this step as long as stack is not empty.
  6. Return the Postfix string.


Infix to Postfix Conversion :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+.
The algorithm for the conversion is as follows :
Repeat this step till all the characters are scanned.



When you run the program, the output will be:

Type in an expression like (1+2)*(3+4)/(12-5)
 with no monadic operators like in-5 or +5 followed by key
(1+2)*(3+4)
The Expression you have typed in infix form :
(1+2)*(3+4)
The Equivalent Postfix Expression is :
12+34++*


2 Comments

Thank you for vising

  1. i have execute this program. but i am getting one error
    that is
    ---------- javac ----------
    Infix2Postfix.java:4: cannot find symbol
    symbol: class character
    public class Infix2Postfix extends Stack {
    ^
    1 error

    Output completed (0 sec consumed) - Normal Termination

    ReplyDelete
  2. in this program you need to extends Stack;better you create stack general type class and extends that one to this program .good luck

    http://java90.blogspot.com/2012/01/stack-data-structure-in-java.html

    ReplyDelete

Post a Comment

Thank you for vising

Previous Post Next Post