Stack

Infix to Postfix

Pinterest LinkedIn Tumblr

Data structure Description

Infix and postfix are the notations to write the expressions. The infix notation put operators in between the operands. The postfix notation put operators after their operands. Write a program convert from infix notation to postfix notation.

Example
Infix (5 + 3) * 12 / 3
Postfix: 5 3 + 12 * 3 /

Algorithm Explanation

Read and scan the character from infix string.
If the scanned character is an operator. pop the element from stack top and compare with the operator. Repeatedly pops the element from the stack if stack top has same or higher precedence.
Push the character to stack. If the scanned character is operand, pops the element until left parenthesis found
If the scanned character is an operand, add it to the Postfix string.
If the stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
Return the postfix string.

Source Code

package com.dsacode.DataStructre.stack;
 
import java.util.Stack;
 
public class InfixToPostfix {
 
    private boolean isOperator(char c) {
        if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^')
            return true;
        return false;
    }
 
    private boolean checkPrecedence(char c1, char c2) {
        if ((c2 == '+' || c2 == '-') && (c1 == '+' || c1 == '-'))
            return true;
        else if ((c2 == '*' || c2 == '/')
                && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
            return true;
        else if ((c2 == '^')
                && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
            return true;
        else
            return false;
    }
 
    public String convert(String infix) {
        String postfix = "";
        Stack < Character > s = new Stack < Character >();
        s.push('*');
 
        for (int i = 0; i < infix.length(); i++) {
 
            char inputSymbol = infix.charAt(i);
 
            if (isOperator(inputSymbol)) {
 
                if (s.size() > 1) {
                    while (checkPrecedence(inputSymbol, s.peek()))
                        postfix += s.pop();
                }
 
                s.push(inputSymbol);
 
            } else if (inputSymbol == '(')
                s.push(inputSymbol);
            else if (inputSymbol == ')') {
 
                while (s.peek() != '(')
                    postfix += s.pop();
 
                s.pop();
            } else {
                postfix += inputSymbol;
            }
        }
 
        while (s.peek() != '*') {
            postfix += s.pop();
        }
 
        return postfix;
    }
 
    public static void main(String[] args) {
        InfixToPostfix obj = new InfixToPostfix();
        String infix="A+(B*C)";
        System.out.println("Infix : \t"+infix);
        System.out.println("Postfix : \t" + obj.convert(infix));
    }
} 

Output

Infix :     1+3*4/5
Postfix :   134*5/+
 

Source Explanation

Get the Infix string and convert infix to postfix using convert function.
Create a stack to hold symbols and Add marker * to end of stack marker.
Read each character from the string. Pop the element from stack if the top element has higher precedence. Return true if the charter has same or higher precedence. Otherwise, return false.
Push to the stack if the character is left parenthesis.
Pop the element from the stack and check the element until the left parenthesis is found.
Pops all elements of stack left.

Write A Comment