Convert Infix to Postfix using Stack in Python
Convert Infix to Postfix using Stack
In the realm of computer science and programming, efficiency is paramount. Converting infix expressions to postfix is a fundamental operation that can significantly impact the efficiency of your code.
In this page, we will discuss about the intricacies of infix to postfix expression conversion, providing you with a deep understanding of the process, its applications, and how to implement it effectively.
Introduction to Infix and Postfix Expressions
Infix expressions are the familiar mathematical notations that we use in everyday life. For instance, “3 + 5” or “((2 * 6) – 1).” These expressions follow operator precedence rules and can contain parentheses to indicate the order of operations.
Postfix expressions, also known as Reverse Polish Notation (RPN), are a different way of representing mathematical expressions. In postfix notation, operators come after their operands, making it easier for computers to evaluate without the need for operator precedence rules or parentheses.
Why Convert Infix to Postfix?
- Converting infix expressions to postfix has several advantages.
- It simplifies expression evaluation, eliminates the need for parentheses to indicate precedence, and allows for straightforward implementation in programming languages.
- Postfix expressions are also easily processed by computers, making them ideal for calculators and parsers.
Infix Expression Syntax:
Infix expressions are the familiar mathematical notations used in everyday mathematics. They follow the operator precedence rules, and parentheses are often used to indicate the order of operations.
operand1 operator operand2
Where:
- ‘operand1’ and ‘operand2′ are numeric values or variables.
- operator is a mathematical operator such as ‘+’ (addition), ‘-‘ (subtraction), ‘*’ (multiplication), ‘/’ (division), etc.
- Parentheses ‘(‘ and ‘)’ are used to group operations and explicitly define the order of evaluation.
(5 + 3) * 2
Postfix Expression Syntax:
Postfix expressions, also known as Reverse Polish Notation (RPN), have a different syntax. In postfix notation, operators come after their operands, and there is no need for operator precedence rules or parentheses.
operand1 operand2 operator
Where:
- ‘operand1’ and ‘operand2′ are numeric values or variables.
- operator is a mathematical operator such as ‘+’ (addition), ‘-‘ (subtraction), ‘*’ (multiplication), ‘/’ (division), etc.
| Infix Expression | Postfix Expression |
|---|---|
| A + B | A B + |
| A + B * C | A B C * + |
| (A + B) * C | A B + C * |
| A * (B + C) | A B C + * |
| A + (B * C) – D | A B C * + D – |
| A * B + C / D | A B * C D / + |
| (A + B) * (C – D) | A B + C D – * |
| A + B + C | A B + C + |
| A * B * C | A B * C * |
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Implementation of Infix to Postfix
Using Stack
The implementation of infix to postfix conversion using a stack involves processing the expression by handling operator precedence and parentheses efficiently. A stack is used to temporarily hold operators, ensuring the final postfix expression follows the correct evaluation order without needing brackets.
# Define the Stack class
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
# Returns precedence of operators
def precedence(char):
if char == '^':
return 3
elif char in '*/':
return 2
elif char in '+-':
return 1
return 0
# Check whether a character is an operand
def is_operand(char):
return char.isalnum() # Accepts a-z, A-Z, 0-9
# Function to convert infix expression to postfix
def infix_to_postfix(expression, stack):
postfix = []
for char in expression:
if char == ' ':
continue # Ignore spaces in the expression
if is_operand(char):
postfix.append(char)
elif char == '(':
stack.push(char)
elif char == ')':
while not stack.is_empty() and stack.peek() != '(':
postfix.append(stack.pop())
stack.pop() # Pop the '('
else:
while (not stack.is_empty()) and (precedence(char) <= precedence(stack.peek())):
postfix.append(stack.pop())
stack.push(char)
while not stack.is_empty():
postfix.append(stack.pop())
return ' '.join(postfix)
# Example usage
infix_expression = "a + b * (c - d) / e"
stack = Stack()
postfix_expression = infix_to_postfix(infix_expression, stack)
print("Postfix Expression:", postfix_expression)
Output:
a b c d - e / * +
Explanation:
- Operands (like a, b, c) are directly added to the postfix expression as they appear.
- Operators (+, *, /, -) are pushed to the stack, but only after popping higher or equal precedence operators already in the stack.
- Parentheses control precedence:
- ( is pushed directly.
- On encountering ), operators are popped until matching ( is found.
- Operator precedence is crucial:
- * and / have higher precedence than + and -,
- ^ (if present) has the highest.
- At the end of the expression, all remaining operators in the stack are popped and added to the postfix result.
- The final postfix output is constructed as a space-separated string for readability.
Time and Space Complexity:
| Aspect | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Time Complexity | O(n) | O(n) | O(n) |
| Space Complexity | O(n) | O(n) | O(n) |
Using Shunting Yard algorithm
The Shunting Yard algorithm, developed by Edsger Dijkstra, is used to convert infix expressions to postfix by managing operators and parentheses with a stack. It ensures correct operator precedence and associativity, making it efficient for expression parsing in compilers.
def infix_to_postfix(expression):
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
output = []
operator_stack = []
for token in expression:
if token.isalnum():
output.append(token)
elif token == '(':
operator_stack.append(token)
elif token == ')':
while operator_stack and operator_stack[-1] != '(':
output.append(operator_stack.pop())
operator_stack.pop()
else:
while (operator_stack and operator_stack[-1] != '(' and
(precedence[token] < precedence[operator_stack[-1]] or
(precedence[token] == precedence[operator_stack[-1]] and token != '^'))):
output.append(operator_stack.pop())
operator_stack.append(token)
while operator_stack:
output.append(operator_stack.pop())
return ' '.join(output)
Output:
a b c d ^ e - f g h * + ^ * + i -
Explanation:
- Operands (like a, b, c) are added directly to the output list.
- ‘(’ is pushed onto the operator stack.
- ‘)’ causes popping from the stack to output until ‘(’ is found.
- Operators are pushed to the stack after popping higher or equal precedence operators (except for ‘^’, which is right-associative).
- Operator precedence is handled using a dictionary: {‘+’ :1, ‘-‘ :1, ‘*’ :2, ‘/’ :2, ‘^’ :3}.
- At the end, any remaining operators in the stack are popped to the output.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Scanning the entire expression | O(n) | O(1) |
| Pushing/Popping from Stack | O(1) per operation | O(n) |
| Handling Operators & Parentheses | O(n) | O(n) |
| Building Postfix Expression | O(n) | O(n) |
| Overall | O(n) | O(n) |
Applications of Infix to Postfix Conversion
Infix to postfix conversion finds applications in various fields, including:
- Calculator software
- Compiler design
- Expression parsing in
- programming languages
- Mathematical software
- Spreadsheet calculations
Final Thoughts:
Mastering the conversion of infix expressions to postfix is a valuable skill for any programmer. It not only simplifies mathematical expression evaluation but also improves the efficiency of your code. With a deep understanding of the stacks and its implementation, you are well-equipped to optimize your programming endeavors.
FAQs
The stack helps manage operator precedence and parentheses by temporarily storing operators until they are needed in the output. This ensures correct postfix expression formation without relying on parentheses.
Postfix eliminates the need for parentheses and precedence rules during evaluation, making it easier and faster to compute using a simple stack-based algorithm.
The stack is used to compare the precedence of incoming operators with those on top, popping higher or equal precedence ones first. Associativity (like left-to-right for +, -) also guides when to pop or push.
An infix expression like A+B*C is taken as input, and the output would be a postfix expression like ABC*+, suitable for evaluation by machines.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment