Practice › Stack & Queue
Infix to Postfix
Medium · Stack & Queue · Asked at Amazon, Microsoft, Samsung, TCS, Infosys
Convert the infix expression to postfix (reverse Polish) notation. Operands are single lowercase letters. Operators are + - (lowest), * /, and ^ (highest). ^ is right-associative; the others are left-associative. Parentheses may appear.
Input
A single line: the expression (no spaces).
Output
The postfix expression (no spaces).
Constraints
- 1 ≤ length ≤ 10^5
- The expression is valid
Shunting-yard: output operands directly; push "("; on ")" pop until "("; on an operator, pop operators with higher precedence (or equal precedence if the new one is left-associative) first.
Example 1
Input
a+b*(c^d-e)^(f+g*h)-i
Output
abcd^e-fgh*+^*+i-
Example 2
Input
a^b^c
Output
abc^^
Hints
- Operands go straight to the output. Operators wait on a stack.
- Before pushing an operator, pop operators with higher precedence — and with equal precedence too, unless the new operator is the right-associative ^.
Approach
Shunting-yard. Letters → output. "(" → push. ")" → pop to output until "(", then discard it. Operator o: while the top is an operator t with prec(t) > prec(o), or prec(t) == prec(o) and o is left-associative, pop t to output; then push o. At the end pop everything. Right associativity of ^ is exactly why "a^b^c" becomes "abc^^".
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int prec(char c) {
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
return 3;
}
int main() {
string s, out;
cin >> s;
string ops;
for (char c : s) {
if (isalpha((unsigned char)c)) out += c;
else if (c == '(') ops += c;
else if (c == ')') {
while (ops.back() != '(') out += ops.back(), ops.pop_back();
ops.pop_back();
} else {
while (!ops.empty() && ops.back() != '(' &&
(prec(ops.back()) > prec(c) || (prec(ops.back()) == prec(c) && c != '^'))) {
out += ops.back();
ops.pop_back();
}
ops += c;
}
}
while (!ops.empty()) out += ops.back(), ops.pop_back();
cout << out << "\n";
return 0;
}Python solution
s = input().strip()
prec = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
out, ops = [], []
for c in s:
if c.isalpha():
out.append(c)
elif c == "(":
ops.append(c)
elif c == ")":
while ops[-1] != "(":
out.append(ops.pop())
ops.pop()
else:
while ops and ops[-1] != "(" and (prec[ops[-1]] > prec[c] or (prec[ops[-1]] == prec[c] and c != "^")):
out.append(ops.pop())
ops.append(c)
while ops:
out.append(ops.pop())
print("".join(out))Java solution
import java.util.*;
public class Main {
static int prec(char c) {
if (c == '+' || c == '-') return 1;
if (c == '*' || c == '/') return 2;
return 3;
}
public static void main(String[] args) {
String s = new Scanner(System.in).next();
StringBuilder out = new StringBuilder();
Deque<Character> ops = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (Character.isLetter(c)) out.append(c);
else if (c == '(') ops.push(c);
else if (c == ')') {
while (ops.peek() != '(') out.append(ops.pop());
ops.pop();
} else {
while (!ops.isEmpty() && ops.peek() != '(' &&
(prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^'))) out.append(ops.pop());
ops.push(c);
}
}
while (!ops.isEmpty()) out.append(ops.pop());
System.out.println(out);
}
}