Infix Postfix Prefix
Arithmetic expressions can be written in three notations: infix (operator between operands), postfix (operator after operands), and prefix (operator before operands). Stacks are used to convert between them and evaluate expressions.
Infix to Postfix Conversion (Shunting Yard Algorithm)
We'll show the algorithm for converting infix to postfix using a stack. The algorithm handles operators and parentheses.
Steps:
1. Iterate through each token.
2. If token is operand, output it.
3. If token is '(', push onto stack.
4. If token is ')', pop and output until '(' is encountered, then discard '('.
5. If token is operator, while stack not empty and top has higher or equal precedence, pop and output; then push current operator.
6. At end, pop all remaining operators.
Java implementation:
public static String infixToPostfix(String infix) {
StringBuilder postfix = new StringBuilder();
Stack stack = new Stack<>();
Map precedence = Map.of(
'+', 1, '-', 1, '*', 2, '/', 2, '^', 3);
for (char c : infix.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
postfix.append(c);
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
postfix.append(stack.pop());
}
stack.pop(); // discard '('
} else { // operator
while (!stack.isEmpty() && stack.peek() != '(' &&
precedence.getOrDefault(stack.peek(), 0) >= precedence.get(c)) {
postfix.append(stack.pop());
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
// Example: "a+b*c" → "abc*+"
Two Minute Drill
- Infix: operand operator operand (e.g., a+b).
- Postfix: operand operand operator (e.g., ab+).
- Prefix: operator operand operand (e.g., +ab).
- Stacks are used to convert infix to postfix (shunting yard).
- Evaluation of postfix also uses a stack.
- Understanding these helps in compiler design and expression evaluation.
Need more clarification?
Drop us an email at career@quipoinfotech.com