{"id":26813,"date":"2017-12-24T15:24:24","date_gmt":"2017-12-24T09:54:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26813"},"modified":"2017-12-24T15:24:24","modified_gmt":"2017-12-24T09:54:24","slug":"java-algorithm-infix-postfix-conversion-using-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-infix-postfix-conversion-using-stack\/","title":{"rendered":"Java Algorithm – Infix to Postfix Conversion using Stack"},"content":{"rendered":"

Infix expression:<\/strong>The expression of the form a op b. When an operator is in-between every pair of operands.<\/span><\/p>\n

Postfix expression:<\/strong>The expression of the form a b op. When an operator is followed for every pair of operands.<\/p>\n

Why postfix representation of the expression?<\/strong>
\nThe compiler scans the expression either from left to right or from right to left.<\/p>\n

Consider the below expression: a op1 b op2 c op3 d
\nIf op1 = +, op2 = *, op3 = +<\/p>\n

The compiler first scans the expression to evaluate the expression b * c, then again scan the expression to add a to it. The result is then added to d after another scan.<\/p>\n

The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix(or prefix) form before evaluation.<\/p>\n

The corresponding expression in postfix form is: abc*+d+. The postfix expressions can be evaluated easily using a stack. We will cover postfix expression evaluation in a separate post.<\/p>\n

Algorithm<\/strong>
\n1.<\/strong> Scan the infix expression from left to right.
\n2.<\/strong> If the scanned character is an operand, output it.
\n3. <\/strong>Else,
\n\u2026..3.1<\/strong> If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
\n\u2026..3.2<\/strong> Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
\n4.<\/strong> If the scanned character is an \u2018(\u2018, push it to the stack.
\n5.<\/strong> If the scanned character is an \u2018)\u2019, pop and output from the stack until an \u2018(\u2018 is encountered.
\n6.<\/strong> Repeat steps 2-6 until infix expression is scanned.
\n7. <\/strong>Pop and output from the stack until it is not empty.<\/p>\n[ad type=”banner”]\n

Following is C implementation of the above algorithm<\/p>\n

Java Programming:<\/strong><\/p>\n

<\/div> 
\/* Java implementation to convert infix expression to postfix*\/\/\/ Note that here we use Stack class for Stack operations import java.util.Stack; class Test{    \/\/ A utility function to return precedence of a given operator    \/\/ Higher returned value means higher precedence    static int Prec(char ch)    {        switch (ch)        {        case '+':        case '-':            return 1;              case '*':        case '\/':            return 2;              case '^':            return 3;        }        return -1;    }          \/\/ The main method that converts given infix expression    \/\/ to postfix expression.     static String infixToPostfix(String exp)    {        \/\/ initializing empty String for result        String result = new String("");                 \/\/ initializing empty stack        Stack<Character> stack = new Stack<>();                 for (int i = 0; i<exp.length(); ++i)        {            char c = exp.charAt(i);                          \/\/ If the scanned character is an operand, add it to output.            if (Character.isLetterOrDigit(c))                result += c;                          \/\/ If the scanned character is an '(', push it to the stack.            else if (c == '(')                stack.push(c);                         \/\/  If the scanned character is an ')', pop and output from the stack             \/\/ until an '(' is encountered.            else if (c == ')')            {                while (!stack.isEmpty() && stack.peek() != '(')                    result += stack.pop();                                 if (!stack.isEmpty() && stack.peek() != '(')                    return "Invalid Expression"; \/\/ invalid expression                                else                    stack.pop();            }            else \/\/ an operator is encountered            {                while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))                    result += stack.pop();                stack.push(c);            }              }              \/\/ pop all the operators from the stack        while (!stack.isEmpty())            result += stack.pop();              return result;    }       \/\/ Driver method     public static void main(String[] args)     {        String exp = "a+b*(c^d-e)^(f+g*h)-i";        System.out.println(infixToPostfix(exp));    }}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
abcd^e-fgh*+^*+i-<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Java Algorithm – Infix to Postfix Conversion using Stack – Data Structure – Infix expression:The expression of the form a op b.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,2139,79607],"tags":[79896,79892,79926,79895,79894,79927,79891,79893,79890],"class_list":["post-26813","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-java","category-stack","tag-algorithm-for-evaluation-of-postfix-expression","tag-algorithm-for-infix-to-postfix-conversion-using-stack-in-c","tag-algorithm-to-convert-infix-to-postfix-expression-in-data-structure","tag-infix-to-postfix-algorithm-geeksforgeeks","tag-infix-to-postfix-algorithm-java","tag-infix-to-postfix-algorithm-with-parentheses","tag-infix-to-postfix-conversion-using-stack-in-c","tag-infix-to-postfix-using-stack-c-code","tag-infix-to-prefix-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26813","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26813"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26813\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}