Infix to Postfix — Solution in Python, Java & C++
Infix to Postfix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and stack.
Infix to Postfix is a medium coding problem on strings and stack, asked in Amazon, Microsoft, TCS and Samsung interviews.
- Difficulty: Medium
- Topics: Strings, Stack
- Asked at: Amazon, Microsoft, TCS, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Convert the infix expression s to postfix (reverse Polish) notation, where every operator follows its two operands.
Operands are single characters — a letter or a digit. The operators are +, -, *, / and ^, and parentheses group sub-expressions. Precedence, from highest: ^, then * and /, then + and -. Operators of equal precedence group left to right, except ^, which groups right to left (a^b^c means a^(b^c)).
Return the postfix expression as a string with no spaces; parentheses never appear in it.
Example 1
Input: s = "a+b*c"
Output: "abc*+"
Example 2
Input: s = "(A-B)/C+D^E^F"
Output: "AB-C/DEF^^+"
Explanation: `^` is right-associative, so `D^E^F` becomes `DEF^^`.
Example 3
Input: s = "x-y-z"
Output: "xy-z-"
Explanation: `-` is left-associative: `(x-y)-z`.
Constraints
1 <= s.length <= 10^5s is a valid infix expression of single-character operands (letters or digits), the operators + - * / ^ and parenthesess contains no spaces
Hints for Infix to Postfix
Hint 1
Operands go straight to the output in the order they appear; only the operators need reordering.
Hint 2
Hold operators on a stack. Before pushing a new operator, which operators already on the stack must be emitted first?
Hint 3
Pop operators with higher precedence, and those with equal precedence when the new operator is left-associative (not
^); stop at(. A)pops until its(.
How to solve Infix to Postfix
The shunting-yard algorithm: operands stream to the output, operators wait on a stack until an operator of lower precedence (or a closing parenthesis) proves they must be applied first.
Approach
- Scan
s. An operand is appended to the output. (is pushed.)pops operators to the output until the matching(, which is discarded.- For an operator
o, pop to the output while the top is an operator with higher precedence thano, or equal precedence andois left-associative. Then pusho. - At the end, pop every remaining operator to the output.
Why it works
An operator on the stack is emitted exactly when its right operand is complete: a following operator of lower precedence (or equal, for left-associative ones) cannot bind tighter, so the stacked operator's sub-expression ends there. For ^, an equal-precedence ^ binds tighter (right-associativity), so the stacked one must wait. Parentheses act as a fence that makes the inner expression complete at ).
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Treating
^as left-associative turnsa^b^cintoab^c^. - Never pop past a
(when handling an operator. - Remember to flush the stack at the end of the input.
Reference solution
Python
def infixToPostfix(s: str) -> str:
prec = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
out = []
st = []
for c in s:
if c.isalnum():
out.append(c)
elif c == '(':
st.append(c)
elif c == ')':
while st[-1] != '(':
out.append(st.pop())
st.pop()
else:
while st and st[-1] != '(' and (prec[st[-1]] > prec[c] or (prec[st[-1]] == prec[c] and c != '^')):
out.append(st.pop())
st.append(c)
while st:
out.append(st.pop())
return ''.join(out)Java
private static int precOf(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return 0;
}
public static String infixToPostfix(String s) {
StringBuilder out = new StringBuilder();
char[] st = new char[s.length() + 1];
int top = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
out.append(c);
} else if (c == '(') {
st[top++] = c;
} else if (c == ')') {
while (st[top - 1] != '(') out.append(st[--top]);
top--;
} else {
while (top > 0 && st[top - 1] != '(' && (precOf(st[top - 1]) > precOf(c) || (precOf(st[top - 1]) == precOf(c) && c != '^'))) {
out.append(st[--top]);
}
st[top++] = c;
}
}
while (top > 0) out.append(st[--top]);
return out.toString();
}C++
int precOf(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return 0;
}
string infixToPostfix(string s) {
string out;
vector<char> st;
for (char c : s) {
if (isalnum((unsigned char)c)) {
out += c;
} else if (c == '(') {
st.push_back(c);
} else if (c == ')') {
while (st.back() != '(') { out += st.back(); st.pop_back(); }
st.pop_back();
} else {
while (!st.empty() && st.back() != '(' && (precOf(st.back()) > precOf(c) || (precOf(st.back()) == precOf(c) && c != '^'))) {
out += st.back();
st.pop_back();
}
st.push_back(c);
}
}
while (!st.empty()) { out += st.back(); st.pop_back(); }
return out;
}JavaScript
var infixToPostfix = function(s) {
var prec = { "+": 1, "-": 1, "*": 2, "/": 2, "^": 3 };
var out = [], st = [];
for (var i = 0; i < s.length; i++) {
var c = s[i];
if (/[A-Za-z0-9]/.test(c)) {
out.push(c);
} else if (c === "(") {
st.push(c);
} else if (c === ")") {
while (st[st.length - 1] !== "(") out.push(st.pop());
st.pop();
} else {
while (st.length > 0 && st[st.length - 1] !== "(") {
var top = st[st.length - 1];
if (prec[top] > prec[c] || (prec[top] === prec[c] && c !== "^")) out.push(st.pop());
else break;
}
st.push(c);
}
}
while (st.length > 0) out.push(st.pop());
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure