Postfix to Prefix Conversion
Description
You are given a string that represents a valid mathematical expression in postfix form (also known as Reverse Polish Notation). Convert it to its equivalent prefix form (also known as Polish Notation).
Postfix Notation: Operators are placed after their operands. For example, the infix expression A + B is written as AB+ in postfix.
Prefix Notation: Operators are placed before their operands. For example, the infix expression A + B is written as +AB in prefix.
Both notations eliminate the need for parentheses because the order of operations is unambiguous from the position of operators relative to operands.
Your task is to convert a given postfix expression into its equivalent prefix expression, preserving the same evaluation order.
Examples
Example 1
Input: post_exp = "ABC/-AK/L-*"
Output: "*-A/BC-/AKL"
Explanation: The postfix expression ABC/-AK/L-* represents the infix expression (A - B/C) * (A/K - L). In prefix form, each operator goes before its operands: * operates on (-A/BC) and (-/AKL), giving *-A/BC-/AKL.
Example 2
Input: post_exp = "ab+"
Output: "+ab"
Explanation: The postfix ab+ means a + b. In prefix, the operator + goes before operands a and b, giving +ab.
Example 3
Input: post_exp = "AB+CD-*"
Output: "*+AB-CD"
Explanation: AB+ → A + B, CD- → C - D, then * multiplies these two results. In prefix: * before +AB and -CD gives *+AB-CD. This represents (A + B) * (C - D).
Example 4
Input: post_exp = "abc-+"
Output: "+a-bc"
Explanation: bc- → b - c, then + adds a and (b - c). Prefix: + before a and -bc gives +a-bc. This represents a + (b - c).
Constraints
- 3 ≤ post_exp.length() ≤ 16000
- The input is a valid postfix expression
- Operands are single characters (letters)
- Operators are one of:
+,-,*,/,^
Editorial
Brute Force
Intuition
The most conceptually clear approach is to first build an expression tree from the postfix expression, and then perform a pre-order traversal of that tree to obtain the prefix expression.
Why does this work? A postfix expression can be naturally converted into a binary tree where:
- Each operand is a leaf node
- Each operator is an internal node with exactly two children (left = first operand, right = second operand)
Once the tree is built, different traversal orders give different notations:
- Pre-order (Root → Left → Right) → Prefix notation
- In-order (Left → Root → Right) → Infix notation
- Post-order (Left → Right → Root) → Postfix notation
So the strategy is: parse the postfix expression into a tree (using a stack of tree nodes), then walk the tree in pre-order to produce the prefix string.
Think of it like translating a sentence through an intermediate language. Instead of converting directly from postfix to prefix, we first build a universal representation (the tree), and then extract the prefix form from it.
Step-by-Step Explanation
Let's trace through with the input ab*c+:
Phase 1 — Build the Expression Tree (scan left to right):
Step 1: Read a. It's an operand → create a leaf node Node(a) and push it onto the node stack.
Step 2: Read b. Operand → create Node(b) and push.
Step 3: Read *. It's an operator → pop two nodes from the stack: first pop = Node(b) (right child), second pop = Node(a) (left child). Create Node(*) with left=a and right=b. Push Node(*) onto the stack.
Step 4: Read c. Operand → create Node(c) and push.
Step 5: Read +. Operator → pop Node(c) (right child) and Node(*) (left child). Create Node(+) with left=* and right=c. Push Node(+). The stack now has one element — the root of our expression tree.
Phase 2 — Pre-order Traversal:
Starting at the root +:
- Visit
+→ output+ - Go left to
*→ output* - Go left to
a→ outputa - Go right to
b→ outputb - Back to
+, go right toc→ outputc
Result: +*abc ✓
Verification: ab*c+ in infix is (a*b)+c, and +*abc in prefix is +(*(a,b), c) = (a*b)+c. ✓
Building Expression Tree from Postfix and Pre-order Traversal — Watch how we construct a binary expression tree from the postfix expression 'ab*c+' using a stack, then traverse it in pre-order to obtain the prefix expression.
Algorithm
Phase 1 — Build Expression Tree:
- Initialize an empty stack of tree nodes
- Scan the postfix expression from left to right:
a. If the character is an operand: create a leaf node and push it onto the stack
b. If the character is an operator:- Pop the top node → this becomes the right child
- Pop the next node → this becomes the left child
- Create a new operator node with these children
- Push the new node onto the stack
- The single remaining node on the stack is the root of the expression tree
Phase 2 — Pre-order Traversal:
4. Perform pre-order traversal (Root → Left → Right) on the tree
5. Concatenate node values in traversal order to get the prefix expression
Code
#include <string>
#include <stack>
using namespace std;
struct TreeNode {
char data;
TreeNode* left;
TreeNode* right;
TreeNode(char c) : data(c), left(nullptr), right(nullptr) {}
};
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
string preOrder(TreeNode* root) {
if (!root) return "";
return string(1, root->data) + preOrder(root->left) + preOrder(root->right);
}
string postToPre(string post_exp) {
stack<TreeNode*> st;
for (char c : post_exp) {
if (isOperator(c)) {
TreeNode* node = new TreeNode(c);
node->right = st.top(); st.pop();
node->left = st.top(); st.pop();
st.push(node);
} else {
st.push(new TreeNode(c));
}
}
return preOrder(st.top());
}class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def is_operator(c):
return c in "+-*/^"
def pre_order(root):
if not root:
return ""
return root.data + pre_order(root.left) + pre_order(root.right)
def postToPre(post_exp):
stack = []
for c in post_exp:
if is_operator(c):
node = TreeNode(c)
node.right = stack.pop()
node.left = stack.pop()
stack.append(node)
else:
stack.append(TreeNode(c))
return pre_order(stack[-1])import java.util.Stack;
class Solution {
static class TreeNode {
char data;
TreeNode left, right;
TreeNode(char c) { data = c; left = right = null; }
}
static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
static String preOrder(TreeNode root) {
if (root == null) return "";
return root.data + preOrder(root.left) + preOrder(root.right);
}
static String postToPre(String post_exp) {
Stack<TreeNode> st = new Stack<>();
for (char c : post_exp.toCharArray()) {
if (isOperator(c)) {
TreeNode node = new TreeNode(c);
node.right = st.pop();
node.left = st.pop();
st.push(node);
} else {
st.push(new TreeNode(c));
}
}
return preOrder(st.peek());
}
}Complexity Analysis
Time Complexity: O(N²)
Building the tree takes O(N) — one pass through the expression with O(1) work per character. However, the pre-order traversal involves string concatenation at each node. In languages where strings are immutable (Java, Python), each concatenation creates a new string. At the root level, the concatenation produces a string of length N, which takes O(N) time to copy. The total string concatenation work across all nodes sums to O(N²) in the worst case for a skewed tree.
Space Complexity: O(N)
We create N tree nodes (one per character in the expression), each using constant space. The node stack holds at most O(N/2) nodes at any time. The recursive pre-order traversal uses O(H) call stack space, where H is the height of the tree (O(N) in the worst case for a skewed tree, O(log N) for a balanced tree). Additionally, the intermediate strings during traversal concatenation use O(N) space. Overall: O(N).
Why This Approach Is Not Efficient
The expression tree approach works correctly but introduces unnecessary overhead:
1. Extra Memory Allocation: We create N tree node objects, each containing a character, two pointers, and object metadata. For a 16,000-character expression, that's 16,000 dynamically allocated objects — significant memory overhead compared to just storing strings.
2. Two-Pass Process: We scan the expression once to build the tree, then traverse the entire tree to produce output. The tree is merely an intermediate representation that we build just to immediately disassemble.
3. Recursive Traversal Overhead: Pre-order traversal is naturally recursive, which means O(H) call stack frames where H is the tree height. For highly unbalanced expressions (like abcde++++), the tree becomes a skewed chain and H = N, risking stack overflow for large inputs.
4. String Concatenation Cost: During pre-order traversal, we concatenate strings at every node. Since strings are immutable in most languages, this repeatedly copies characters, leading to O(N²) time in the worst case.
Key Insight: We don't actually need the tree at all! The postfix expression already encodes the structure implicitly. Instead of building a tree and traversing it, we can directly construct the prefix string in a single pass using a stack of strings. This eliminates tree node creation, avoids recursion, and simplifies the code dramatically.
Optimal Approach - Direct Stack-Based String Manipulation
Intuition
Instead of building a tree, we can convert postfix to prefix directly using a stack of strings.
The insight is elegant: in the tree approach, we pushed nodes onto the stack and later extracted strings via traversal. But we can skip the tree entirely — just push strings onto the stack and construct prefix sub-expressions on the fly.
Here's the core idea:
- When we see an operand, push it as a single-character string
- When we see an operator, pop two strings from the stack, form the prefix expression
operator + second_popped + first_popped, and push the result back
Why operator + second_popped + first_popped? Because in a stack, the first element popped was pushed later (it's the right operand in the original expression), and the second element popped was pushed earlier (it's the left operand). In prefix notation, the operator comes first, followed by the left operand, then the right operand.
This single-pass approach does exactly what the tree approach does — but without the tree. Each "push of a prefix sub-expression" is equivalent to building a subtree and later traversing it. We just do it all in one step.
Think of it as a factory assembly line: instead of building a car frame (tree), painting it, then installing parts — we build, paint, and install each section as it passes by.
Step-by-Step Explanation
Let's trace through with AB+CD-*:
Step 1: Read A. Operand → push "A". Stack: ["A"]
Step 2: Read B. Operand → push "B". Stack: ["A", "B"]
Step 3: Read +. Operator → pop "B" (op1), pop "A" (op2). Form prefix: "+" + "A" + "B" = "+AB". Push "+AB". Stack: ["+AB"]
Step 4: Read C. Operand → push "C". Stack: ["+AB", "C"]
Step 5: Read D. Operand → push "D". Stack: ["+AB", "C", "D"]
Step 6: Read -. Operator → pop "D" (op1), pop "C" (op2). Form prefix: "-" + "C" + "D" = "-CD". Push "-CD". Stack: ["+AB", "-CD"]
Step 7: Read *. Operator → pop "-CD" (op1), pop "+AB" (op2). Form prefix: "*" + "+AB" + "-CD" = "*+AB-CD". Push. Stack: ["*+AB-CD"]
Result: The single string on the stack is "*+AB-CD" — our prefix expression. ✓
Notice how each operator immediately combines two sub-expressions without needing any tree or recursion. The stack naturally maintains the correct operand grouping.
Direct Stack Conversion — Postfix to Prefix in One Pass — Watch how we convert 'AB+CD-*' to prefix '*+AB-CD' using a single stack of strings. Operands are pushed directly, and each operator pops two strings and pushes the combined prefix expression.
Algorithm
- Initialize an empty stack of strings
- Scan the postfix expression from left to right, for each character
c:
a. Ifcis an operand (not an operator):- Push
cas a single-character string onto the stack
b. Ifcis an operator (+,-,*,/,^): - Pop the top element → call it
op1(this was the right operand) - Pop the next element → call it
op2(this was the left operand) - Form the prefix string:
c + op2 + op1 - Push this combined string onto the stack
- Push
- After processing all characters, the stack contains exactly one element
- Return that element — it is the prefix expression
Code
#include <string>
#include <stack>
using namespace std;
bool isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
string postToPre(string post_exp) {
stack<string> st;
for (char c : post_exp) {
if (isOperator(c)) {
string op1 = st.top(); st.pop();
string op2 = st.top(); st.pop();
string result = string(1, c) + op2 + op1;
st.push(result);
} else {
st.push(string(1, c));
}
}
return st.top();
}def postToPre(post_exp: str) -> str:
operators = set("+-*/^")
stack = []
for c in post_exp:
if c in operators:
op1 = stack.pop()
op2 = stack.pop()
stack.append(c + op2 + op1)
else:
stack.append(c)
return stack[-1]import java.util.Stack;
class Solution {
static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
static String postToPre(String post_exp) {
Stack<String> st = new Stack<>();
for (char c : post_exp.toCharArray()) {
if (isOperator(c)) {
String op1 = st.pop();
String op2 = st.pop();
st.push(c + op2 + op1);
} else {
st.push(String.valueOf(c));
}
}
return st.peek();
}
}Complexity Analysis
Time Complexity: O(N²)
We make a single pass through the expression of length N. Each character involves one push or one pop-pop-push operation, both O(1) for stack operations. However, string concatenation (c + op2 + op1) creates a new string whose length can be up to O(N) in the worst case. Across all operator steps, the total concatenation work sums to O(N²) in the worst case. In practice, for typical expressions with balanced operator/operand distribution, the average concatenation length is much smaller.
Note: Using a StringBuilder (Java) or building the result with a list and joining (Python) can help reduce the constant factor, but the theoretical worst case remains O(N²) due to the nature of string building.
Space Complexity: O(N)
The stack stores at most O(N) strings at any point (when all characters so far are operands). The total length of all strings on the stack at any moment is O(N) since each original character appears in exactly one string on the stack. No additional data structures are needed beyond the stack itself.