C Program
#include <stdio.h>
#include <ctype.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
stack[++top] = c;
}
char pop() {
return stack[top--];
}
int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return -1;
}
void infixToPostfix(char* exp) {
for (int i = 0; exp[i] != '\0'; i++) {
char c = exp[i];
if (isalnum(c)) {
printf("%c", c);
}
else if (c == '(') {
push(c);
}
else if (c == ')') {
while (top != -1 && stack[top] != '(') {
printf("%c", pop());
}
pop();
}
else {
while (top != -1 && precedence(stack[top]) >= precedence(c)) {
printf("%c", pop());
}
push(c);
}
}
while (top != -1) {
printf("%c", pop());
}
}
int main() {
char exp[] = "A+(B*C)";
infixToPostfix(exp);
return 0;
}C Output
ABC*+
C++ Program
#include <iostream>
#include <stack>
using namespace std;
int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return -1;
}
void infixToPostfix(string s) {
stack<char> st;
for (char c : s) {
if (isalnum(c)) {
cout << c;
}
else if (c == '(') {
st.push(c);
}
else if (c == ')') {
while (!st.empty() && st.top() != '(') {
cout << st.top();
st.pop();
}
st.pop();
}
else {
while (!st.empty() && precedence(st.top()) >= precedence(c)) {
cout << st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty()) {
cout << st.top();
st.pop();
}
}
int main() {
string exp = "A+(B*C)";
infixToPostfix(exp);
}C++ Output
ABC*+
JAVA Program
import java.util.*;
public class Main {
static int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return -1;
}
static void infixToPostfix(String s) {
Stack<Character> st = new Stack<>();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
System.out.print(c);
} else if (c == '(') {
st.push(c);
} else if (c == ')') {
while (!st.isEmpty() && st.peek() != '(') {
System.out.print(st.pop());
}
st.pop();
} else {
while (!st.isEmpty() && precedence(st.peek()) >= precedence(c)) {
System.out.print(st.pop());
}
st.push(c);
}
}
while (!st.isEmpty()) {
System.out.print(st.pop());
}
}
public static void main(String[] args) {
String exp = "A+(B*C)";
infixToPostfix(exp);
}
}JAVA Output
ABC*+
Python Program
def precedence(c):
if c == '^':
return 3
if c in ('*', '/'):
return 2
if c in ('+', '-'):
return 1
return -1
def infix_to_postfix(expression):
stack = []
for c in expression:
if c.isalnum():
print(c, end="")
elif c == '(':
stack.append(c)
elif c == ')':
while stack and stack[-1] != '(':
print(stack.pop(), end="")
stack.pop()
else:
while stack and precedence(stack[-1]) >= precedence(c):
print(stack.pop(), end="")
stack.append(c)
while stack:
print(stack.pop(), end="")
expr = "A+(B*C)"
infix_to_postfix(expr)Python Output
ABC*+
Detailed Explanation
Example
Consider the infix expression A+(B*C). In infix notation, the operators are placed between the operands, which is the way people typically write mathematics. But computers compute more effectively when the operators occur following the operands, which is referred to as postfix notation. The postfix expression for A+(B*C) is ABC*+.
Real-Life Analogy
Imagine infix notation as saying to someone, "Add A to the product of B and C." The person must first determine what they multiply, then add, so they unconsciously rearrange the steps. Postfix notation is similar to issuing clear-cut orders in the order of execution: "Take B, take C, multiply them, then take A, and add." No guessing, no parentheses, no confusion.
Why It Matters
Infix expressions need parsing rules such as precedence and associativity to identify the proper order of evaluation. This is complicated for computers. Postfix dispenses with parentheses and expresses the order of operation explicitly, so evaluating it is easy using a stack. This is the reason most compilers and calculators internally translate infix to postfix before execution.
Step-by-Step Logic
The algorithm employs a stack to hold operators temporarily until they can be properly inserted in the postfix output.
Scan the expression from left to right.
If the character is an operand (A-Z, 0-9), print it immediately.
If it's (, push it on the stack.
If it's ), pop from the stack until ( is encountered.
If it's an operator, pop operators from the stack of higher or equal precedence and then push the new operator.
After scanning the entire expression, pop remaining operators from the stack.
Common Beginner Mistakes
One mistake is not considering operator precedence. For instance, without precedence resolution, A+B*C would end up wrongfully as AB+C* rather than ABC*+. Another error is missing to deal with parentheses correctly, which disrupts grouping semantics.
Complexity and Optimization
The conversion is O(n) time because each character is pushed and popped at most once. Space complexity is O(n) worst case for the stack.
Real-World Applications
This algorithm has a broad application in expression parsing for compilers, interpreters, and calculators. While constructing a special scripting language or math evaluator, infix to postfix conversion is a key preprocessing operation prior to evaluation.
Interview Insights
Interviewers tend to ask this question to test the knowledge of stacks, operator precedence, and expression parsing. An extra point is noting postfix evaluation is simpler and faster since it precludes precedence checks at execution time.
Learning Insights
This exercise educates you in handling temporary storage via stacks and appreciating the distinction between parsing (notation conversion) and evaluation (result computation). It demonstrates as well why postfix abstraction exists — not for human convenience, but for machine efficiency.
Infix-to-postfix conversion with a stack is an elementary algorithm in data structures that is essential to compilers, calculators, and expression evaluators. By manipulating operator precedence and parentheses, it converts readable infix notation into machine-convenient postfix form, which can be evaluated more quickly and reliably. Proficiency in the algorithm establishes solid grounding in stack operations, parsing logic, and compiler design, which makes it a must-know skill in coding interviews and programming projects in practice.
Social Plugin