Prefix to Postfix conversion using stack

Write a program to Prefix to Postfix conversion using stack

Example: 1 

Input: prefix="+A+*BC*/EF^GH"
Output: postfix = "ABC*+EF/GH^*+"

Approach:

Java

import java.util.HashMap;
import java.util.Stack;

public class PrefixToPostfix {
    static HashMap<CharacterIntegerprecedence =
         new HashMap<CharacterInteger>();

    public static void main(String[] args) {
        // prefix
        String prefix = "+A+*BC*/EF^GH";
        // precedence initialization
        operatorPrecedence();
        // prefix to infix
        String infix = prefixToInfix(prefix);
        // infix to postfix
        String postFIx = infixToPostfix(infix);
        System.out.println("Postfix is " + postFIx);
    }

    private static String prefixToInfix(String prefix) {
        String infix = "";
        // stack for hold operator
        Stack<Stringstack = new Stack<>();
        // Iterate till given infix length
        for (int i = prefix.length() - 1; i >= 0; i--) {
            // hold char from postFIx
            char c = prefix.charAt(i);
            // If letter then add into stack
            if (Character.isLetter(c)) {
                stack.add(String.valueOf(c));
            } else {
                // rule = first+operator+second
                String a = stack.pop();
                String b = stack.pop();
                stack.add(a + "" + c + "" + b);
            }

        }
        // iterate till stack is empty
        while (!stack.isEmpty()) {
            infix += stack.pop();
        }
        return infix;
    }

    private static String infixToPostfix(String infix) {
        String postFix = "";
        // stack for hold operator
        Stack<Characterstack = new Stack<>();
        // Iterate till given infix length
        for (int i = 0; i < infix.length(); i++) {
            // hold char from infix
            char c = infix.charAt(i);
            // If letter then add into postfix
            if (Character.isLetter(c)) {
                postFix += infix.charAt(i);
            } else if (c == '(') {
                stack.add(c);
            } else if (c == '^') {
                stack.add(c);
            } else if (c == ')') { // if closing ) then
                // iterate till ( and add into postfix
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postFix += stack.pop();
                }
                // if last char is '(' into stack then pop
                if (!stack.isEmpty() && stack.peek() == '(')
                    stack.pop();
            } else {
                // if precedence of c is greater then
                // top stack then add
                if (stack.isEmpty() || precedence.get(c) > 
                    precedence.getOrDefault(stack.peek(), 0)) {
                    stack.add(c);
                } else {
                    // iterate till precedence is less then equal and add
                    while (!stack.isEmpty() && precedence.get(c) 
                        <= precedence.get(stack.peek())) {
                        postFix += stack.pop();
                    }
                    // add coming char
                    stack.add(c);
                }
            }

        }
        // iterate till stack is empty
        while (!stack.isEmpty()) {
            postFix += stack.pop();
        }
        return postFix;
    }

    private static HashMap<CharacterIntegeroperatorPrecedence() {
        precedence.put('^'10);
        precedence.put('*'9);
        precedence.put('/'9);
        precedence.put('-'8);
        precedence.put('+'8);
        return precedence;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
map<char,intprecedence;
map<char,intoperatorPrecedence() 
{
        precedence['^']=10;
        precedence['*']=9;
        precedence['/']=9;
        precedence['-']=8;
        precedence['+']=8;
        return precedence;
}


//function to convert from
//prefix to infix
string prefixToInfix(string prefix
{
    string infix = "";
    // stack for hold operator
    stack<stringstack;
    // Iterate till given prefix length
    for (int i = prefix.length() - 1i >= 0i--) 
    {
        // hold char from postFIx
        char c = prefix[i];
        // If letter then add into stack
        if (isalpha(c))
           {
               //convert character 
               //to string 
               string strc(1,c);
               stack.push(strc);
           } 
        else 
         {
                // rule = first+operator+second
                string a = stack.top();
                stack.pop();

                string b = stack.top();
                stack.pop();
                //convert from character
                //to string
                string strc(1,c);
                stack.push(a + "" + strc + "" + b);
            }

        }
        // iterate till stack is empty
        while (!stack.empty()) {
            {
                infix += stack.top();
                stack.pop();
            }
        }
        return infix;
}
string infixToPostfix(string infix)
{      
     string postFix = "";
    // stack for hold operator
    stack<charstack;
    // Iterate till given infix length
    for (int i = 0i < infix.size(); i++)
     {
        // hold char from infix
        char c = infix[i];
        // If letter then add into postfix
         if (isalpha(c)) {
                postFix += c;
            } 
        else if (c == '('
        {
                stack.push(c);
        } 
        else if (c == '^')
          {
                stack.push(c);
         } 
        else if (c == ')')
              { // if closing ) then
                // iterate till ( and add into postfix
                while (!stack.empty() && stack.top() != '(') {
                    {
                        postFix += stack.top();
                        stack.pop();
                    }
                }
                // if last char is '(' into stack then pop
                if (!stack.empty() && stack.top() == '(')
                    stack.pop();
            } else {
                // if precedence of c is greater then 
                //top stack then add
                if (stack.empty() || precedence[c] >
                     precedence[stack.top()]) {
                    stack.push(c);
                } else {
                    // iterate till precedence is less then equal and add
                    while (!stack.empty() && precedence[c] 
                            <= precedence[stack.top()]) {
                        {
                            postFix += stack.top();
                            stack.pop();
                        }
                    }
                    // add coming char
                    stack.push(c);
                }
            }

        }
        // iterate till stack is empty
        while (!stack.empty()) {
           {
                postFix += stack.top();
                stack.pop();
           }
        }
        return postFix;
}
int main()
{
   // prefix
   string prefix = "+A+*BC*/EF^GH";
   // precedence initialization
   operatorPrecedence();
   // prefix to infix

   string infix=prefixToInfix(prefix);

   //infix to postfix
   string postFIx = infixToPostfix(infix);
   cout<<"Postfix is ";
   cout<<postFIx<<"\n";
   return 0;
}


No comments:

Post a Comment