In mathematics expressions, there are infix, prefix and postfix notations. Infix notation is characterized by the placement of operators between operands. For example, the plus sign in 2 + 2. Prefix notation is a notation in which operators precede their operands, such as + 3 4. Postfix notation is a notation in which operators follow their operands, for example 3 4 +. This post introduces how to convert an expression from prefix to postfix. There are two methods, stack and recursion. We use letters as operands in the expression.
How to convert prefix to postfix using a stack?
A common method for converting a prefix expression to postfix is by using a stack. Starting from the end of the prefix expression, we scan each character one by one. If the character is an operand (e.g., a letter), we push it onto the stack. If it’s an operator (such as +, –, , or /), we pop the top two operands from the stack, combine them with the operator in postfix order (operand1 operand2 operator), and push the resulting sub-expression back onto the stack. Once the scan is complete, the top of the stack holds the final postfix expression.
How to convert prefix to postfix using recursion?
An alternative approach is to use recursion. In this method, we process the prefix expression from the beginning. Since a prefix expression starts with an operator, we first remove the first character and store it in a variable, op. Then, we recursively call the function twice to obtain the next two operands, stored as op1 and op2. After that, we create a list to build a postfix sub-expression by appending op1, op2, and then op in that order. When the recursion unwinds, the final list contains the complete postfix expression.
Google Interview Question
convert Prefix_to_Postfix using recursion
+ * A B / C D -> A B * C D / +
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | import java.util.*; public class PrefixToPostfix { //Solution 1: Use stack, Time O(n), Space O(m), //n is expression length, m is operator number in expression public static String preToPostStack(char[] exp) { Stack<String> s = new Stack<>(); int length = exp.length; for (int i = length - 1; i >= 0; i--) { if (!isOp(exp[i])) { s.push(Character.toString(exp[i])); } else { String op1 = s.pop(); String op2 = s.pop(); String temp = op1 + op2 + exp[i]; s.push(temp); } } return s.peek(); } //Solution 2: Use recursion, Time O(n), Space O(n+m), public static ArrayList<String> preToPostRec(ArrayList<String> exp) { String op = exp.remove(0); List<String> op1 = isOp(exp.get(0).charAt(0)) ? preToPostRec(exp) : Arrays.asList(exp.remove(0)); List<String> op2 = isOp(exp.get(0).charAt(0)) ? preToPostRec(exp) : Arrays.asList(exp.remove(0)); ArrayList<String> res = new ArrayList<>(exp.size()); res.addAll(op1); res.addAll(op2); res.add(op); return res; } //Check whether the char is operator, Time O(1), Space O(1) private static boolean isOp(char Op) { if (Op == '+' || Op == '-' || Op == '*' || Op == '/') { return true; } else { return false; } } //Utility method, convert list to string, Time O(n), Space O(n), n is list length private static String convert(ArrayList<String> s) { String res = ""; for (String i: s) { res += i; } return res; } public static void main(String[] args) { String s ="+*AB/CD"; //A*B + C/D System.out.println("postfix(stack): " + preToPostStack(s.toCharArray())); ArrayList<String> input = new ArrayList<>(Arrays.asList(s.split(""))); ArrayList<String> output = preToPostRec(input); System.out.println("postfix(recursion): " + convert(output)); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | //Solution 1: Use stack, Time O(n), Space O(m), //n is expression length, m is operator number in expression function preToPostStack(exp) { var s = []; var length = exp.length; for (let i = length - 1; i >= 0; i--) { if (!isOp(exp[i])) { s.push(exp[i]); } else { let op1 = s.pop(); let op2 = s.pop(); let temp = op1 + op2 + exp[i]; s.push(temp); } } return s[s.length - 1]; } //Solution 2: Use recursion, Time O(n), Space O(n+m) function preToPostRec(exp) { var op = exp.shift(0); var op1 = isOp(exp[0].charAt(0)) ? preToPostRec(exp) : exp.shift(); var op2 = isOp(exp[0].charAt(0)) ? preToPostRec(exp) : exp.shift(); var res = new Array(); res.push(op1); res.push(op2); res.push(op); return res; } //Check whether the char is operator, Time O(1), Space O(1) function isOp(op) { if (op == '+' || op == '-' || op == '*' || op == '/') { return true; } else { return false; } } //utility functioin, convert list to string, Time O(n), Space O(n), n is list length function convert(res) { let r = "" for (let i of res) { if (Array.isArray(i)) r += convert(i); else r += i; } return r; } let s ="+*AB/CD"; //A*B + C/D console.log("postfix(stack): " + preToPostStack(s)); let res = preToPostRec(Array.from(s)) r = convert(res); console.log("postfix(rec): " + r); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #Solution 1: Use stack, Time O(n), Space O(m), # n is expression length, m is operator number in expression def preToPostStack(exp) : s = [] length = len(exp) for i in range(length-1, -1, -1) : if isOp(exp[i])==False : s.append(exp[i]) else : op1 = s.pop() op2 = s.pop() temp = op1 + op2 + exp[i] s.append(temp) return s[len(s) - 1] #Solution 2: Use recursion, Time O(n), Space O(n+m) def preToPostRec(exp) : op = exp.pop(0); op1 = preToPostRec(exp) if isOp(exp[0][0]) else exp.pop(0) op2 = preToPostRec(exp) if isOp(exp[0][0]) else exp.pop(0) res = [] res.append(op1) res.append(op2) res.append(op) return res #Check whether the char is operator, Time O(1), Space O(1) def isOp(op): if op == '+' or op == '-' or op == '*' or op == '/' : return True else : return False #Utility function, convert list to string, Time O(n), Space O(n), n is list length def convert(res): r = "" for i in res: if isinstance(i, list): r += convert(i) else: r += i return r s = "+*AB/CD"; #A*B + C/D print("postfix(stack): " + preToPostStack(s)) res = preToPostRec(list(s)) r = convert(res) print("postfix(rec): " + r) |
Output:
prefix: +*AB/CD
postfix(stack): AB*CD/+
postfix(recursion): AB*CD/+
O Notation:
Time complexity: O(n)
Space complexity: O(n)
Download PrefixToPostfix.java
Download PrefixToPostfix.js
Download PrefixToPostfix.py
Covert prefix to postfix using stack or recursion (YouTube)
Java Coding Interview Pocket Book
